{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T12:40:55Z","timestamp":1693053655645},"reference-count":44,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T00:00:00Z","timestamp":1632441600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2022,3]]},"abstract":"Abstract<\/jats:title>An even (respectively, odd) hole in a graph is an induced cycle with even (respectively, odd) length that is at least four. Bienstock proved that detecting an even (respectively, odd) hole containing a given vertex is NP\u2010complete. Conforti, Cornu\u00e9jols, Kapoor, and Vu\u0161kovi\u0107 gave the first known polynomial\u2010time algorithm to determine whether a graph contains even holes. Chudnovsky, Kawarabayashi, and Seymour estimated that Conforti et al.'s algorithm runs in time on an \u2010vertex graph and reduced the required time to . Subsequently, da Silva and Vu\u0161kovi\u0107, Chang and Lu, and Lai, Lu, and Thorup\u00a0improved the time to , , and , respectively. The tractability of determining whether a graph contains odd holes has been open for decades until the algorithm of Chudnovsky, Scott, Seymour, and Spirkl that runs in time, which Lai et al. also reduced to . By extending Chudnovsky et al.'s techniques for detecting odd holes, Chudnovsky, Scott, and Seymour\u00a0(respectively) ensured the tractability of finding a long (respectively, shortest) odd hole. They also ensured the NP\u2010hardness of finding a longest odd hole, whose reduction also works for finding a longest even hole. Recently, Cook and Seymour ensured the tractability of finding a long even hole. An intriguing missing piece is the tractability of finding a shortest even hole, left open for 16\u2009years by, for example, Chudnovsky et al. and Johnson. We resolve this open problem by augmenting Chudnovsky et al.'s even\u2010hole detection algorithm into the first known polynomial\u2010time algorithm, running in time, for finding a shortest even hole in an \u2010vertex graph that contains even holes.<\/jats:p>","DOI":"10.1002\/jgt.22748","type":"journal-article","created":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T22:57:16Z","timestamp":1632524236000},"page":"425-434","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Finding a shortest even hole in polynomial time"],"prefix":"10.1002","volume":"99","author":[{"given":"Hou\u2010Teng","family":"Cheong","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering National Taiwan University Taipei Taiwan"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-5755-2338","authenticated-orcid":false,"given":"Hsueh\u2010I","family":"Lu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering National Taiwan University Taipei Taiwan"}]}],"member":"311","published-online":{"date-parts":[[2021,9,24]]},"reference":[{"key":"e_1_2_5_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.12.006"},{"key":"e_1_2_5_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.02.001"},{"key":"e_1_2_5_4_1","first-page":"123","article-title":"Les probl\u00e8mes de coloration en th\u00e9orie des graphes","volume":"9","author":"Berge C.","year":"1960","journal-title":"Publ. Inst. Statist. Univ. Paris"},{"key":"e_1_2_5_5_1","first-page":"114","article-title":"F\u00e4rbung von Graphen, deren s\u00e4mtliche bzw. deren ungerade Kreise starr sind (Zusammenfassung)","volume":"10","author":"Berge C.","year":"1961","journal-title":"Wiss. Z. Martin Luther Univ. Halle\u2010Wittenberg, Math.\u2010Naturwiss. Reihe"},{"key":"e_1_2_5_6_1","unstructured":"C. Berge 1985 North\u2010Holland Amsterdam New York"},{"key":"e_1_2_5_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90098-M"},{"key":"e_1_2_5_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90357-L"},{"key":"e_1_2_5_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.02.001"},{"key":"e_1_2_5_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0012-8"},{"key":"e_1_2_5_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/060672613"},{"key":"e_1_2_5_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20040"},{"key":"e_1_2_5_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.07.004"},{"key":"e_1_2_5_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.01.003"},{"key":"e_1_2_5_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1249473"},{"key":"e_1_2_5_16_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2006.164.51"},{"key":"e_1_2_5_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-020-4301-z"},{"key":"e_1_2_5_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447869"},{"key":"e_1_2_5_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375720"},{"key":"e_1_2_5_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.05.001"},{"key":"e_1_2_5_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-010-2334-4"},{"key":"e_1_2_5_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646136"},{"key":"e_1_2_5_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200007)34:33.0.CO;2-P"},{"key":"e_1_2_5_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10006"},{"key":"e_1_2_5_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10045"},{"key":"e_1_2_5_26_1","unstructured":"L.Cook\u00a0andP.Seymour Detecting a long even hole Comput. Res. Repos.\u00a0(2020) \u00a0 vol.2009.05691 1\u201332.https:\/\/arxiv.org\/abs\/2009.05691"},{"key":"e_1_2_5_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.07.027"},{"key":"e_1_2_5_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.10.001"},{"key":"e_1_2_5_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316329"},{"key":"e_1_2_5_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.12.004"},{"key":"e_1_2_5_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-018-1925-5"},{"key":"e_1_2_5_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-75242-2_11"},{"key":"e_1_2_5_33_1","first-page":"21:1","volume-title":"Proceedings of the 14th International Symposium on Parameterized and Exact Computation","author":"Husic E.","year":"2019"},{"key":"e_1_2_5_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077464.1077476"},{"key":"e_1_2_5_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.55"},{"key":"e_1_2_5_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.10.004"},{"key":"e_1_2_5_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.12.005"},{"key":"e_1_2_5_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0118(200101)36:13.0.CO;2-N"},{"key":"e_1_2_5_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-4086-0"},{"key":"e_1_2_5_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384235"},{"key":"e_1_2_5_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22374"},{"key":"e_1_2_5_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104442522"},{"key":"e_1_2_5_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.07.010"},{"key":"e_1_2_5_44_1","doi-asserted-by":"publisher","DOI":"10.2298\/AADM100812027V"},{"key":"e_1_2_5_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2018.11.005"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22748","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/jgt.22748","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22748","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,26]],"date-time":"2023-08-26T00:02:39Z","timestamp":1693008159000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22748"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,24]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["10.1002\/jgt.22748"],"URL":"https:\/\/doi.org\/10.1002\/jgt.22748","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,24]]},"assertion":[{"value":"2021-07-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-08","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}