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(4kk4ℓ), 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(4kk4(m+n)) and O(4kk5(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(12kk5ℓ), 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(12kk5ℓ), where k is the size of the smallest q-Horn deletion backdoor set, with ℓ being the length of the input formula.
- 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--123Google ScholarCross Ref
- Endre Boros, Peter L. Hammer, and Xiaorong Sun. 1994. Recognition of -horn formulae in linear time. Discrete Applied Mathematics 55, 1, 1--13. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Hyeong-Ah Choi, Kazuo Nakajima, and Chong S. Rim. 1989. Graph bipartization and via minimization. SIAM Journal on Discrete Mathematics 2, 1, 38--47. Google ScholarDigital Library
- Y. Crama, O. Ekin, and P. L. Hammer. 1997. Variable and term removal from Boolean formulae. Discrete Applied Mathematics 75, 3, 217--230. Google ScholarDigital Library
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer. Google ScholarDigital Library
- Samuel Fiorini, Nadia Hardy, Bruce A. Reed, and Adrian Vetta. 2008. Planar graph bipartization in linear time. Discrete Applied Mathematics 156, 7, 1175--1180. Google ScholarDigital Library
- Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Germany. Google ScholarDigital Library
- L. R. Ford Jr. and D. R. Fulkerson. 1956. Maximal flow through a network. Canadian Journal of Mathematics 8, 399--404.Google ScholarCross Ref
- A. Frank. 2011. Connections in Combinatorial Optimization. Oxford University Press, Oxford, England. 2010942420 https://books.google.co.in/books?id=acQZuWho7m8CGoogle Scholar
- S. Gaspers, S. Ordyniak, M. S. Ramanujan, S. Saurabh, and S. Szeider. 2016. Backdoors to q-Horn. Algorithmica 74, 1, 540--557. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Andrew V. Goldberg and Alexander V. Karzanov. 1996. Path problems in skew-symmetric graphs. Combinatorica 16, 3, 353--382.Google ScholarCross Ref
- Andrew V. Goldberg and Alexander V. Karzanov. 2004. Maximum skew-symmetric flows and matchings. Mathematical Programming 100, 3, 537--568.Google ScholarDigital Library
- Falk Hüffner. 2009. Algorithm engineering for optimal graph bipartization. Journal of Graph Algorithms and Applications 13, 2, 77--98.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Yoichi Iwata, Magnus Wahlström, and Yuichi Yoshida. 2016. Half-integrality, LP-branching, and FPT algorithms. SIAM Journal on Computing 45, 4, 1377--1411.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 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.Google Scholar
- Meena Mahajan and Venkatesh Raman. 1999. Parameterizing above guaranteed values: Maxsat and maxcut. Journal of Algorithms 31, 2, 335--354. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Dániel Marx and Igor Razgon. 2009. Constant ratio fixed-parameter approximation of the edge multicut problem. Information Processing Letters 109, 20, 1161--1166. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Hiroshi Nagamochi and Toshihide Ibaraki. 2008. Algorithmic Aspects of Graph Connectivity. Vol. 123. Cambridge University Press, New York, NY. Google ScholarDigital Library
- 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.Google Scholar
- Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, Vol. 31. Oxford University Press, Oxford, England.Google ScholarCross Ref
- 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.Google Scholar
- Alessandro Panconesi and Mauro Sozio. 2004. Fast hare: A fast heuristic for single individual SNP haplotype reconstruction. In Algorithms in Bioinformatics. Springer, 266--277.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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 Google ScholarDigital Library
- Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. 2004. Finding odd cycle transversals. Operations Research Letters 32, 4, 299--301. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Robert Endre Tarjan. 1975. Efficiency of a good but not linear set union algorithm. Journal of the ACM 22, 2, 215--225. Google ScholarDigital Library
- W. T. Tutte. 1967. Antisymmetrical digraphs. Canadian Journal of Mathematics 19, 1101--1117.Google ScholarCross Ref
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Thomas Zaslavsky. 1991. Orientation of signed graphs. European Journal of Combinatorics 12, 361--375. Google ScholarDigital Library
- Bohdan Zelinka. 1976. Analoga of Menger’s theorem for polar and polarized graphs. Czechoslovak Mathematical Journal 26, 3, 352--360.Google Scholar
Index Terms
- Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
Recommendations
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
In the Subset Feedback Vertex Set (Subset FVS) problem, the input is a graph G on n vertices and m edges, a subset of vertices T, referred to as terminals, and an integer k. The objective is to determine whether there exists a set of at most k vertices ...
Linear time parameterized algorithms via skew-symmetric multicuts
SODA '14: Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithmsA 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 [1967]...
Parameterized Complexity of Length-bounded Cuts and Multicuts
We study the Minimum Length-Bounded Cut problem where the task is to find a set of edges of a graph such that after removal of this set, the shortest path between two prescribed vertices is at least $$L + 1$$L+1 long. We show the problem can be computed ...
Comments