Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts

Abstract

A skew-symmetric graph (D=(V,A),σ) is a directed graph D with an involution σ 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, d-Skew-Symmetric Multicut, where we are given a skew-symmetric graph D, a family τ of d-size subsets of vertices, and an integer k. The objective is to decide whether there is a set X ⊑ A of k arcs such that every set J in the family has a vertex υ such that υ and σ(υ) are in different strongly connected components of D′=(V,A \ (X ∪ σ(X)). In this work, we give an algorithm for d-Skew-Symmetric Multicut that runs in time O((4d)^k(m+n+ℓ)), where m is the number of arcs in the graph, n is the number of vertices, and ℓ is the length of the family given in the input.

This problem, apart from being independently interesting, also captures the main combinatorial difficulty of numerous classical problems. Our algorithm for d-Skew-Symmetric Multicut 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:

— We show that Almost 2-SAT is a special case of 1-Skew-Symmetric Multicut, resulting in an algorithm for Almost 2-SAT that runs in time O(4^kk⁴ℓ), where k is the size of the solution and ℓ is the length of the input formula. Then, using linear-time parameter-preserving reductions to Almost 2-SAT, we obtain algorithms for Odd Cycle Transversal and Edge Bipartization that run in time O(4^kk⁴(m+n)) and O(4^kk⁵(m+n)), respectively, where k is the size of the solution, and m and 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.

— We show that Deletion q-Horn Backdoor Set Detection is a special case of 3-Skew-Symmetric Multicut, giving us an algorithm for Deletion q-Horn Backdoor Set Detection that runs in time O(12^kk⁵ℓ), where k is the size of the solution and ℓ 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 Satisfiability that runs in time O(12^kk⁵ℓ), where k is the size of the smallest q-Horn deletion backdoor set, with ℓ being the length of the input formula.

References

1. Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. 1979. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters 8, 3, 121--123
2. Endre Boros, Peter L. Hammer, and Xiaorong Sun. 1994. Recognition of -horn formulae in linear time. Discrete Applied Mathematics 55, 1, 1--13.
3. Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, and Igor Razgon. 2008. A fixed-parameter algorithm for the directed feedback vertex set problem. Journal of the ACM 55, 5, Article No. 21.
4. Hyeong-Ah Choi, Kazuo Nakajima, and Chong S. Rim. 1989. Graph bipartization and via minimization. SIAM Journal on Discrete Mathematics 2, 1, 38--47.
5. Y. Crama, O. Ekin, and P. L. Hammer. 1997. Variable and term removal from Boolean formulae. Discrete Applied Mathematics 75, 3, 217--230.
6. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer.
7. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. 2013. On multiway cut parameterized above lower bounds. ACM Transactions on Computation Theory 5, 1, 3:1--3:11.
8. Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer.
9. Samuel Fiorini, Nadia Hardy, Bruce A. Reed, and Adrian Vetta. 2008. Planar graph bipartization in linear time. Discrete Applied Mathematics 156, 7, 1175--1180.
10. Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Germany.
11. L. R. Ford Jr. and D. R. Fulkerson. 1956. Maximal flow through a network. Canadian Journal of Mathematics 8, 399--404.
12. A. Frank. 2011. Connections in Combinatorial Optimization. Oxford University Press, Oxford, England. 2010942420 https://books.google.co.in/books?id=acQZuWho7m8C
13. S. Gaspers, S. Ordyniak, M. S. Ramanujan, S. Saurabh, and S. Szeider. 2016. Backdoors to q-Horn. Algorithmica 74, 1, 540--557.
14. 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.
15. Andrew V. Goldberg and Alexander V. Karzanov. 1996. Path problems in skew-symmetric graphs. Combinatorica 16, 3, 353--382.
16. Andrew V. Goldberg and Alexander V. Karzanov. 2004. Maximum skew-symmetric flows and matchings. Mathematical Programming 100, 3, 537--568.
17. Falk Hüffner. 2009. Algorithm engineering for optimal graph bipartization. Journal of Graph Algorithms and Applications 13, 2, 77--98.
18. Yoichi Iwata, Keigo Oka, and Yuichi Yoshida. 2014. Linear-time FPT algorithms via network flow. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14). 1749--1761.
19. Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida. 2016. Half-integrality, LP-branching, and FPT algorithms. SIAM Journal on Computing 45, 4, 1377--1411.
20. 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’10). 365--378. Subhash Khot and Venkatesh Raman. 2002. Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science 289, 2, 997--1008.
21. Stefan Kratsch and Magnus Wahlström. 2012. Representative sets and irrelevant vertices: New tools for kernelization. In Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS’12). 450--459.
22. D. Lokshtanov, N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, and S. Saurabh. 2014. Faster parameterized algorithms using linear programming. ACM Transctions on Algorithms 11, 2, 15:1--15:31.
23. Daniel Lokshtanov and M. S. Ramanujan. 2012. Parameterized tractability of multiway cut with parity constraints. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming, Volume Part I (ICALP’12). 750--761.
24. Daniel Lokshtanov, Saket Saurabh, and Somnath Sikdar. 2009. Simpler parameterized algorithm for OCT. In Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA’09). 380--384.
25. Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlström. 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’12). 424--434.
26. Meena Mahajan and Venkatesh Raman. 1999. Parameterizing above guaranteed values: Maxsat and maxcut. Journal of Algorithms 31, 2, 335--354.
27. Dániel Marx, Barry O’Sullivan, and Igor Razgon. 2013. Finding small separators in linear time via treewidth reduction. ACM Transactions on Algorithms 9, 4, 30:1--30:35.
28. Dániel Marx and Igor Razgon. 2009. Constant ratio fixed-parameter approximation of the edge multicut problem. Information Processing Letters 109, 20, 1161--1166.
29. Dániel Marx and Igor Razgon. 2014. Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM Journal on Computing 43, 2, 355--388.
30. Hiroshi Nagamochi and Toshihide Ibaraki. 2008. Algorithmic Aspects of Graph Connectivity. Vol. 123. Cambridge University Press, New York, NY.
31. 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’12). 338--349.
32. Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, Vol. 31. Oxford University Press, Oxford, England.
33. 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’04). 96--103.
34. Alessandro Panconesi and Mauro Sozio. 2004. Fast hare: A fast heuristic for single individual SNP haplotype reconstruction. In Algorithms in Bioinformatics. Springer, 266--277.
35. V. Raman, M. S. Ramanujan, and S. Saurabh. 2011. Paths, flowers and vertex cover. In Algorithms—ESA 2011. Lecture Notes in Computer Science, Vol. 6942. Springer, 382--393.
36. Igor Razgon and Barry O’Sullivan. 2008. Almost 2-SAT is fixed-parameter tractable (extended abstract). In Proceedings of the 35th Intenational Colloquium on Automata, Languages, and Programming (ICALP’08). 551--562.
37. Igor Razgon and Barry O’Sullivan. 2009. Almost 2-SAT is fixed-parameter tractable.Journal of Computer and System Sciences 75, 8, 435--450. http://dblp.uni-trier.de/db/journals/jcss/jcss75.html#RazgonO09
38. Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. 2004. Finding odd cycle transversals. Operations Research Letters 32, 4, 299--301.
39. 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.
40. Robert Endre Tarjan. 1975. Efficiency of a good but not linear set union algorithm. Journal of the ACM 22, 2, 215--225.
41. W. T. Tutte. 1967. Antisymmetrical digraphs. Canadian Journal of Mathematics 19, 1101--1117.
42. Sebastian Wernicke. 2003. On the Algorithmic Tractability of Single Nucleotide Polymorphism (SNP) Analysis and Related Problems. Master’s Thesis. Wilhelm-Schickard-Institut für Informatik, Universität Tübingen.
43. Ryan Williams, Carla Gomes, and Bart Selman. 2003. Backdoors to typical case complexity. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI’03). 1173--1178.
44. Thomas Zaslavsky. 1991. Orientation of signed graphs. European Journal of Combinatorics 12, 361--375.
45. Bohdan Zelinka. 1976. Analoga of Menger’s theorem for polar and polarized graphs. Czechoslovak Mathematical Journal 26, 3, 352--360.

Index Terms

• Theory of computation

  • Design and analysis of algorithms

    • Parameterized complexity and exact algorithms

      • Fixed parameter tractability