Simultaneous Feedback Vertex Set: A Parameterized Perspective

Abstract

For a family F of graphs, a graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. For an integer α ≥ 1, an n-vertex (multi) graph G = (V, ⋃_i=1^α E_i), where the edge set of G is partitioned into α color classes, is called an α-edge-colored (multi) graph. A natural extension of the F-Deletion problem to edge-colored graphs is the Simultaneous F-Deletion problem. In the latter problem, we are given an α-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph G_i − S, where G_i = (V, E_i) and 1 ≤ i ≤ α, is in F. In this work, we study Simultaneous F-Deletion for F being the family of forests. In other words, we focus on the Simultaneous Feedback Vertex Set (SimFVS) problem. Algorithmically, we show that, like its classical counterpart, SimFVS parameterized by k is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant α. In particular, we give an algorithm running in 2^{O(α k)}n^O(1) time and a kernel with O(αk^3(α+1)) vertices. The running time of our algorithm implies that SimFVS is FPT even when α ∈ o(log n). We complement this positive result by showing that if we allow α to be in O(log n), where n is the number of vertices in the input graph, then SimFVS becomes W[1]-hard. In particular, when α is roughly equal to c log n, for a non-zero positive constant c, the problem becomes W[1]-hard. Our positive results answer one of the open problems posed by Cai and Ye (MFCS 2014).

References

1. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. 1999. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discr. Math. 12, 3 (1999), 289--297.
2. Jørgen Bang-Jensen and Gregory Gutin. 1997. Alternating cycles and paths in edge-coloured multigraphs: A survey. Discr. Math. 165-166 (1997), 39--60.
3. Leizhen Cai and Junjie Ye. 2014. Dual connectedness of edge-bicolored graphs and beyond. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS’14). 141--152.
4. Yixin Cao and Dániel Marx. 2015. Interval deletion is fixed-parameter tractable. ACM Trans. Algor. 11, 3 (2015), 21:1--21:35.
5. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. 2008. Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74, 7 (2008), 1188--1198.
6. Jianer Chen, Iyad A. Kanj, and Ge Xia. 2010. Improved upper bounds for vertex cover. Theor. Comput. Sci. 411, 40-42 (2010), 3736--3756.
7. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer.
8. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. 2011. Solving connectivity problems parameterized by treewidth in single exponential time. In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS’11). 150--159.
9. Reinhard Diestel. 2012. Graph Theory (4th ed.). Graduate texts in mathematics, Vol. 173. Springer.
10. Rod G. Downey and Michael R. Fellows. 1997. Parameterized Complexity. Springer-Verlag.
11. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’12). 470--479.
12. M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
13. Martin Grohe and Dániel Marx. 2009. On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99, 1 (2009), 218--228.
14. Russell Impagliazzo and Ramamohan Paturi. 2001. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 2 (2001), 367--375.
15. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 4 (2001), 512--530.
16. Mikio Kano and Xueliang Li. 2008. Monochromatic and heterochromatic subgraphs in edge-colored graphs—survey. Graphs Combin. 24, 4 (2008), 237--263.
17. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. 2016. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algor. 12, 2 (2016), 21:1--21:41.
18. Tomasz Kociumaka and Marcin Pilipczuk. 2014. Faster deterministic feedback vertex set. Inf. Process. Lett. 114, 10 (2014), 556--560.
19. Stefan Kratsch and Magnus Wahlström. 2012. Representative sets and irrelevant vertices: New tools for kernelization. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS’12). 450--459.
20. Daniel Lokshtanov. 2008. Wheel-free deletion Is W{2}-hard. In Proceedings of the 3rd International Workshop on Parameterized and Exact Computation IWPEC’08). Proceedings. 141--147.
21. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. 2014. Faster parameterized algorithms using linear programming. ACM Trans. Algor. 11, 2 (2014), 15:1--15:31.
22. Dániel Marx. 2010. Can you beat treewidth? Theory Comput. 6, 1 (2010), 85--112.
23. Dániel Marx. 2010. Chordal deletion is fixed-parameter tractable. Algorithmica 57, 4 (2010), 747--768.
24. Dániel Marx and Ildikó Schlotter. 2012. Obtaining a planar graph by vertex deletion. Algorithmica 62, 3-4 (2012), 807--822.
25. Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. 2012. Parameterized algorithms for even cycle transversal. In Proceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’12). 172--183.
26. Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. 2004. Finding odd cycle transversals. Oper. Res. Lett. 32, 4 (2004), 299--301.
27. Stéphan Thomassé. 2010. A 4k² kernel for feedback vertex set. ACM Trans. Algor. 6, 2 (2010), 32:1--32:8.
28. V. G. Vizing. 1964. On an estimate of the chromatic class of a p-graph. Diskret. Analiz No. 3 (1964), 25--30.
29. Mingyu Xiao and Hiroshi Nagamochi. 2015. An improved exact algorithm for undirected feedback vertex set. J. Comb. Optim. 30, 2 (2015), 214--241.
30. Junjie Ye. 2015. A note on finding dual feedback vertex set. CoRR abs/1510.00773 (2015). http://arxiv.org/abs/1510.00773

Index Terms

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes

    • Problems, reductions and completeness

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Backtracking

      • Branch-and-bound

    • Graph algorithms analysis

    • Parameterized complexity and exact algorithms

      • Fixed parameter tractability