{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:57Z","timestamp":1750309497833,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T00:00:00Z","timestamp":1736121600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,4,30]]},"abstract":"\n An\n independent set<\/jats:italic>\n in a graph\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is a set of pairwise non-adjacent vertices. A graph\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is\n bipartite<\/jats:italic>\n if its vertex set can be partitioned into two independent sets. In the\n Odd Cycle Transversal<\/jats:sc>\n problem, the input is a graph\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n along with a weight function\n w<\/jats:monospace>\n associating a rational weight with each vertex, and the task is to find a minimum weight vertex subset\n \n \\(S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that\n \n \\(G-S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is bipartite; the weight of\n \n \\(S\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n \\(\\text{w}(S)=\\sum_{v\\in S}\\text{w}(v)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We show that\n Odd Cycle Transversal<\/jats:sc>\n is polynomial-time solvable on graphs excluding\n \n \\(P_{5}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n (a path on five vertices) as an induced subgraph. The problem was previously known to be polynomial-time solvable on\n \n \\(P_{4}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free graphs and\n NP<\/jats:monospace>\n -hard on\n \n \\(P_{6}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free graphs [Dabrowski, Feghali, Johnson, Paesani, Paulusma and Rz\u0105\u017cewski, Algorithmica 2020]. Bonamy, Dabrowski, Feghali, Johnson and Paulusma [Algorithmica 2019] posed the existence of a polynomial-time algorithm on\n \n \\(P_{5}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -free graphs as an open problem. This was later re-stated by Rz\u0105\u017cewski [Dagstuhl Reports, 9(6): 2019], by Chudnovsky, King, Pilipczuk, Rz\u0105\u017cewski, and Spirkl [SIDMA 2021] who gave an algorithm with running time\n \n \\(n^{O(\\sqrt{n})}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for the problem, and by Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024] who gave a quasi-polynomial time algorithm.\n <\/jats:p>","DOI":"10.1145\/3708544","type":"journal-article","created":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T12:26:51Z","timestamp":1734092811000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Odd Cycle Transversal on\n P<\/i>\n 5<\/sub>\n -free Graphs in Polynomial Time"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0656-7572","authenticated-orcid":false,"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9304-4536","authenticated-orcid":false,"given":"Paloma T.","family":"Lima","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3166-9212","authenticated-orcid":false,"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"UCSB, Santa Barbara, CA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7696-3848","authenticated-orcid":false,"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[{"name":"Warsaw University of Technology Faculty of Mathematics and Information Science, Warszawa, Poland and University of Warsaw Institute of Informatics, Warszawa, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7847-6402","authenticated-orcid":false,"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Theoretical Computer Science Group, The Institute of Mathematical Sciences, Chennai, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2212-1359","authenticated-orcid":false,"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}]}],"member":"320","published-online":{"date-parts":[[2025,1,6]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.189"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.023"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1515\/dma.2007.030"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02352694"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0474-x"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028791"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.IPL.2021.106168"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.01.009"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.09.033"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1367660"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/DagRep.9.6.125"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-013-9777-0"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00706-6"},{"key":"e_1_3_2_16_2","unstructured":"H. N. De Ridder. 2016. Information System on Graph Classes and Their Inclusions. Retrieved from https:\/\/www.graphclasses.org"},{"key":"e_1_3_2_17_2","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"Diestel Reinhard","year":"2012","unstructured":"Reinhard Diestel. 2012. Graph Theory (4th ed.). Graduate Texts in Mathematics, Vol. 173. Springer.","edition":"4"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0063-7"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/140964801"},{"key":"e_1_3_2_20_2","first-page":"1","article-title":"Transitiv orientierbare graphen","volume":"18","author":"Gallai Tibor","year":"1967","unstructured":"Tibor Gallai. 1967. Transitiv orientierbare graphen. Acta Mathematica Hungarica 18, 1\u20132 (1967), 25\u201366.","journal-title":"Acta Mathematica Hungarica"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00063"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451034"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009810"},{"key":"e_1_3_2_24_2","unstructured":"Cicely Henderson Evelyne Smith-Roberge Sophie Spirkl and Rebecca Whitman. 2024. Maximum k-colourable induced subgraphs in (P \\({}_{5}\\) +rK \\({}_{1}\\) )-free graphs. arXiv:2410.08077. Retrieved from https:\/\/arxiv.org\/abs\/2410.08077"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9197-8"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00177"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.127"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2021.21"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28050-4_11"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.31"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00414-5"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.11.001"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/110845835"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2635810"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"e_1_3_2_37_2","unstructured":"Daniel Lokshtanov Pawe Rz\u0105\u017cewski Saket Saurabh Roohani Sharma and Meirav Zehavi. 2024. Maximum partial list h-coloring on P \\({}_{5}\\) -free graphs in polynomial time. arXiv:2410.21569. Retrieved from https:\/\/arxiv.org\/abs\/2410.21569"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10217-2_37"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2012.424"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.43"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.12.004"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.23"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1334-2"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_3_2_45_2","unstructured":"Yotaro Takazawa and Shinji Mizuno. 2018. On a reduction of the weighted induced bipartite subgraph problem to the weighted independent Set problem. arXiv:1807.10277. Retrieved from https:\/\/arxiv.org\/abs\/1807.10277"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708544","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708544","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:46Z","timestamp":1750295866000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708544"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,6]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4,30]]}},"alternative-id":["10.1145\/3708544"],"URL":"https:\/\/doi.org\/10.1145\/3708544","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,1,6]]},"assertion":[{"value":"2024-02-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}