{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T17:38:20Z","timestamp":1769017100526,"version":"3.49.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T00:00:00Z","timestamp":1505779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Parameterized Approximation"},{"name":"ERC","award":["306992"],"award-info":[{"award-number":["306992"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"\n A skew-symmetric graph (\n D<\/jats:italic>\n =(\n V<\/jats:italic>\n ,\n A<\/jats:italic>\n ),\u03c3) is a directed graph\n D<\/jats:italic>\n with an involution \u03c3 on the set of vertices and arcs. Flows on skew-symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte and later by Goldberg and Karzanov. In this article, we introduce a separation problem,\n d<\/jats:italic>\n -S\n kew<\/jats:sc>\n -S\n ymmetric<\/jats:sc>\n M\n ulticut<\/jats:sc>\n , where we are given a skew-symmetric graph\n D<\/jats:italic>\n , a family \u03c4 of\n d<\/jats:italic>\n -size subsets of vertices, and an integer\n k<\/jats:italic>\n . The objective is to decide whether there is a set\n X<\/jats:italic>\n \u2291\n A<\/jats:italic>\n of\n k<\/jats:italic>\n arcs such that every set\n J<\/jats:italic>\n in the family has a vertex \u03c5 such that \u03c5 and \u03c3(\u03c5) are in different strongly connected components of\n D<\/jats:italic>\n \u2032=(\n V<\/jats:italic>\n ,A \\ (\n X<\/jats:italic>\n \u222a \u03c3(\n X<\/jats:italic>\n )). In this work, we give an algorithm for\n d<\/jats:italic>\n -S\n kew<\/jats:sc>\n -S\n ymmetric<\/jats:sc>\n M\n ulticut<\/jats:sc>\n that runs in time\n O<\/jats:italic>\n ((4\n d<\/jats:italic>\n )\n k<\/jats:sup>\n (\n m<\/jats:italic>\n +\n n<\/jats:italic>\n +\u2113)), where\n m<\/jats:italic>\n is the number of arcs in the graph,\n n<\/jats:italic>\n is the number of vertices, and \u2113 is the length of the family given in the input.\n <\/jats:p>\n \n This problem, apart from being independently interesting, also captures the main combinatorial difficulty of numerous classical problems. Our algorithm for\n d<\/jats:italic>\n -S\n kew<\/jats:sc>\n -S\n ymmetric<\/jats:sc>\n M\n ulticut<\/jats:sc>\n paves the way for the first linear-time parameterized algorithms for several problems. We demonstrate its utility by obtaining the following linear-time parameterized algorithms:\n <\/jats:p>\n \n \u2014 We show that A\n lmost<\/jats:sc>\n 2-SAT is a special case of 1-S\n kew<\/jats:sc>\n -S\n ymmetric<\/jats:sc>\n M\n ulticut<\/jats:sc>\n , resulting in an algorithm for A\n lmost<\/jats:sc>\n 2-SAT that runs in time\n O<\/jats:italic>\n (4\n k<\/jats:sup>\n k\n 4<\/jats:sup>\n \u2113), where\n k<\/jats:italic>\n is the size of the solution and \u2113 is the length of the input formula. Then, using linear-time parameter-preserving reductions to A\n lmost<\/jats:sc>\n 2-SAT, we obtain algorithms for O\n dd<\/jats:sc>\n C\n ycle<\/jats:sc>\n T\n ransversal<\/jats:sc>\n and E\n dge<\/jats:sc>\n B\n ipartization<\/jats:sc>\n that run in time\n O<\/jats:italic>\n (4\n k<\/jats:sup>\n k\n 4<\/jats:sup>\n (\n m<\/jats:italic>\n +\n n<\/jats:italic>\n )) and\n O<\/jats:italic>\n (4\n k<\/jats:sup>\n k\n 5<\/jats:sup>\n (\n m<\/jats:italic>\n +\n n<\/jats:italic>\n )), respectively, where\n k<\/jats:italic>\n is the size of the solution, and\n m<\/jats:italic>\n and\n n<\/jats:italic>\n are the number of edges and vertices respectively. This resolves an open problem posed by Reed et al. and improves on the earlier almost-linear-time algorithm of Kawarabayashi and Reed.\n <\/jats:p>\n \n \u2014 We show that D\n eletion<\/jats:sc>\n q-Horn B\n ackdoor<\/jats:sc>\n S\n et<\/jats:sc>\n D\n etection<\/jats:sc>\n is a special case of 3-S\n kew<\/jats:sc>\n -S\n ymmetric<\/jats:sc>\n M\n ulticut<\/jats:sc>\n , giving us an algorithm for D\n eletion<\/jats:sc>\n q-Horn B\n ackdoor<\/jats:sc>\n S\n et<\/jats:sc>\n D\n etection<\/jats:sc>\n that runs in time\n O<\/jats:italic>\n (12\n k<\/jats:sup>\n k\n 5<\/jats:sup>\n \u2113), where\n k<\/jats:italic>\n is the size of the solution and \u2113 is the length of the input formula. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a work by Narayanaswamy et al. Using this result, we get an algorithm for S\n atisfiability<\/jats:sc>\n that runs in time\n O<\/jats:italic>\n (12\n k<\/jats:sup>\n k\n 5<\/jats:sup>\n \u2113), where\n k<\/jats:italic>\n is the size of the smallest q-Horn deletion backdoor set, with \u2113 being the length of the input formula.\n <\/jats:p>","DOI":"10.1145\/3128600","type":"journal-article","created":{"date-parts":[[2017,9,20]],"date-time":"2017-09-20T12:35:19Z","timestamp":1505910919000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts"],"prefix":"10.1145","volume":"13","author":[{"given":"M. S.","family":"Ramanujan","sequence":"first","affiliation":[{"name":"Institute of Mathematical Sciences, HBNI, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, HBNI, Chennai University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90033-7"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402004"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00028-5"},{"key":"e_1_2_1_6_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462896.2462899"},{"key":"e_1_2_1_8_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013","unstructured":"Rodney G. Downey and Michael R . Fellows . 2013 . Fundamentals of Parameterized Complexity. Springer . Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.08.013"},{"key":"e_1_2_1_10_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer-Verlag , Germany . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Germany."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_12_1","volume-title":"Connections in Combinatorial Optimization","author":"Frank A.","year":"2010","unstructured":"A. Frank . 2011. Connections in Combinatorial Optimization . Oxford University Press , Oxford, England . 2010 942420 https:\/\/books.google.co.in\/books?id=acQZuWho7m8C A. Frank. 2011. Connections in Combinatorial Optimization. Oxford University Press, Oxford, England. 2010942420 https:\/\/books.google.co.in\/books?id=acQZuWho7m8C"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9958-5"},{"key":"e_1_2_1_14_1","series-title":"Lecture Notes in Computer Science","volume-title":"The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday","author":"Gaspers Serge","unstructured":"Serge Gaspers and Stefan Szeider . 2012. Backdoors to satisfaction . In The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday . Lecture Notes in Computer Science , Vol. 7370 . Springer , 287--317. Serge Gaspers and Stefan Szeider. 2012. Backdoors to satisfaction. In The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, Vol. 7370. Springer, 287--317."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261321"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112680.3113156"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00177"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634201"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/140962838"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Kawarabayashi Ken-Ichi","year":"2002","unstructured":"Ken-Ichi Kawarabayashi and Bruce A. Reed . 2010. An (almost) linear time algorithm for odd cycles transversal . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910) . 365--378. Subhash Khot and Venkatesh Raman. 2002 . Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science 289, 2, 997--1008. Ken-Ichi Kawarabayashi and Bruce A. Reed. 2010. An (almost) linear time algorithm for odd cycles transversal. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). 365--378. Subhash Khot and Venkatesh Raman. 2002. Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science 289, 2, 997--1008."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_63"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10217-2_37"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201912)","author":"Lokshtanov Daniel","year":"2012","unstructured":"Daniel Lokshtanov , Saket Saurabh , and Magnus Wahlstr\u00f6m . 2012 . Subexponential parameterized odd cycle transversal on planar graphs . In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201912) . 424--434. Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlstr\u00f6m. 2012. Subexponential parameterized odd cycle transversal on planar graphs. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201912). 424--434."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0996"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500119"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.07.016"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/110855247"},{"key":"e_1_2_1_30_1","volume-title":"Algorithmic Aspects of Graph Connectivity","author":"Nagamochi Hiroshi","unstructured":"Hiroshi Nagamochi and Toshihide Ibaraki . 2008. Algorithmic Aspects of Graph Connectivity . Vol. 123 . Cambridge University Press, New York , NY. Hiroshi Nagamochi and Toshihide Ibaraki. 2008. Algorithmic Aspects of Graph Connectivity. Vol. 123. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","author":"Narayanaswamy N. S.","unstructured":"N. S. Narayanaswamy , V. Raman , M. S. Ramanujan , and S. Saurabh . 2012. LP can be a cure for parameterized problems . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201912) . 338--349. N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, and S. Saurabh. 2012. LP can be a cure for parameterized problems. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201912). 338--349."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201904)","author":"Nishimura Naomi","year":"2004","unstructured":"Naomi Nishimura , Prabhakar Ragde , and Stefan Szeider . 2004 . Detecting backdoor sets with respect to horn and binary clauses . In Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201904) . 96--103. Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. 2004. Detecting backdoor sets with respect to horn and binary clauses. In Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201904). 96--103."},{"key":"e_1_2_1_34_1","volume-title":"Algorithms in Bioinformatics","author":"Panconesi Alessandro","unstructured":"Alessandro Panconesi and Mauro Sozio . 2004. Fast hare: A fast heuristic for single individual SNP haplotype reconstruction . In Algorithms in Bioinformatics . Springer , 266--277. Alessandro Panconesi and Mauro Sozio. 2004. Fast hare: A fast heuristic for single individual SNP haplotype reconstruction. In Algorithms in Bioinformatics. Springer, 266--277."},{"key":"e_1_2_1_35_1","volume-title":"Lecture Notes in Computer Science","volume":"6942","author":"Raman V.","unstructured":"V. Raman , M. S. Ramanujan , and S. Saurabh . 2011. Paths, flowers and vertex cover. In Algorithms\u2014ESA 2011 . Lecture Notes in Computer Science , Vol. 6942 . Springer, 382--393. V. Raman, M. S. Ramanujan, and S. Saurabh. 2011. Paths, flowers and vertex cover. In Algorithms\u2014ESA 2011. Lecture Notes in Computer Science, Vol. 6942. Springer, 382--393."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_45"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_2_1_39_1","volume-title":"Algorithms in Bioinformatics","author":"Rizzi Romeo","unstructured":"Romeo Rizzi , Vineet Bafna , Sorin Istrail , and Giuseppe Lancia . 2002. Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem . In Algorithms in Bioinformatics . Springer , 29--43. Romeo Rizzi, Vineet Bafna, Sorin Istrail, and Giuseppe Lancia. 2002. Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem. In Algorithms in Bioinformatics. Springer, 29--43."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1967-101-8"},{"key":"e_1_2_1_42_1","volume-title":"On the Algorithmic Tractability of Single Nucleotide Polymorphism (SNP) Analysis and Related Problems. Master\u2019s Thesis","author":"Wernicke Sebastian","unstructured":"Sebastian Wernicke . 2003. On the Algorithmic Tractability of Single Nucleotide Polymorphism (SNP) Analysis and Related Problems. Master\u2019s Thesis . Wilhelm-Schickard-Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen . Sebastian Wernicke. 2003. On the Algorithmic Tractability of Single Nucleotide Polymorphism (SNP) Analysis and Related Problems. Master\u2019s Thesis. Wilhelm-Schickard-Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI\u201903)","author":"Williams Ryan","year":"2003","unstructured":"Ryan Williams , Carla Gomes , and Bart Selman . 2003 . Backdoors to typical case complexity . In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI\u201903) . 1173--1178. Ryan Williams, Carla Gomes, and Bart Selman. 2003. Backdoors to typical case complexity. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI\u201903). 1173--1178."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(13)80118-7"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"352","DOI":"10.21136\/CMJ.1976.101410","article-title":"Analoga of Menger\u2019s theorem for polar and polarized graphs","volume":"26","author":"Zelinka Bohdan","year":"1976","unstructured":"Bohdan Zelinka . 1976 . Analoga of Menger\u2019s theorem for polar and polarized graphs . Czechoslovak Mathematical Journal 26 , 3, 352 -- 360 . Bohdan Zelinka. 1976. Analoga of Menger\u2019s theorem for polar and polarized graphs. Czechoslovak Mathematical Journal 26, 3, 352--360.","journal-title":"Czechoslovak Mathematical Journal"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3128600","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3128600","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:14Z","timestamp":1750217414000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3128600"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,19]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3128600"],"URL":"https:\/\/doi.org\/10.1145\/3128600","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,19]]},"assertion":[{"value":"2015-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}