Simultaneous Feedback Vertex Set: A Parameterized Perspective

Authors Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh



PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.7.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Akanksha Agrawal
Daniel Lokshtanov
Amer E. Mouawad
Saket Saurabh

Cite AsGet BibTex

Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh. Simultaneous Feedback Vertex Set: A Parameterized Perspective. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.STACS.2016.7

Abstract

For a family of graphs F, 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. A graph G = (V, cup_{i=1}^{alpha} E_{i}), where the edge set of G is partitioned into alpha color classes, is called an alpha-edge-colored graph. A natural extension of the F-DELETION problem to edge-colored graphs is the alpha-SIMULTANEOUS F-DELETION problem. In the latter problem, we are given an alpha-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 <= alpha, is in F. In this work, we study alpha-SIMULTANEOUS F-DELETION for F being the family of forests. In other words, we focus on the alpha-SIMULTANEOUS FEEDBACK VERTEX SET (alpha-SIMFVS) problem. Algorithmically, we show that, like its classical counterpart, alpha-SIMFVS parameterized by k is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant alpha. In particular, we give an algorithm running in 2^{O(alpha * k)} * n^{O(1)} time and a kernel with O(alpha * k^{3(alpha + 1)}) vertices. The running time of our algorithm implies that alpha-SIMFVS is FPT even when alpha in o(log(n)). We complement this positive result by showing that for alpha in O(log(n)), where n is the number of vertices in the input graph, alpha-SIMFVS becomes W[1]-hard. Our positive results answer one of the open problems posed by Cai and Ye (MFCS 2014).
Keywords
  • parameterized complexity ,feedback vertex set
  • kernel
  • edge-colored graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discret. Math., 12(3):289-297, September 1999. URL: http://dx.doi.org/10.1137/S0895480196305124,
  2. Jorgen Bang-Jensen and Gregory Gutin. Alternating cycles and paths in edge-coloured multigraphs: A surve. Discrete Mathematics, 165-166:39-60, 1997. Graphs and Combinatorics. Google Scholar
  3. Leizhen Cai and Junjie Ye. Dual connectedness of edge-bicolored graphs and beyond. In Mathematical Foundations of Computer Science 2014, volume 8635 of Lecture Notes in Computer Science, pages 141-152. Springer Berlin Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_13.
  4. Yixin Cao and Dániel Marx. Interval deletion is fixed-parameter tractable. ACM Trans. Algorithms, 11(3):21:1-21:35, January 2015. URL: http://doi.acm.org/10.1145/2629595, URL: http://dx.doi.org/10.1145/2629595.
  5. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. Journal of Computer and System Sciences, 74(7):1188-1198, 2008. URL: http://www.sciencedirect.com/science/article/pii/S0022000008000500, URL: http://dx.doi.org/http://dx.doi.org/10.1016/j.jcss.2008.05.002.
  6. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, September 2010. URL: http://dx.doi.org/10.1016/j.tcs.2010.06.026,
  7. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3,
  8. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Joham M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Proceedings of the 2011 IEEE 52Nd Annual Symposium on Foundations of Computer Science, FOCS'11, pages 150-159, Washington, DC, USA, 2011. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2011.23,
  9. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  10. Rod G. Downey and Michael R. Fellows. Parameterized complexity. Springer-Verlag, 1997. Google Scholar
  11. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-Deletion: Approximation, kernelization and optimal FPT algorithms. In FOCS, pages 470-479. IEEE Computer Society, 2012. URL: http://dblp.uni-trier.de/db/conf/focs/focs2012.html#FominLMS12.
  12. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1979. Google Scholar
  13. Martin Grohe and Dániel Marx. On tree width, bramble size, and expansion. Journal of Combinatorial Theory, Series B, 99(1):218-228, 2009. URL: http://www.sciencedirect.com/science/article/pii/S0095895608000683, URL: http://dx.doi.org/http://dx.doi.org/10.1016/j.jctb.2008.06.004.
  14. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: http://www.sciencedirect.com/science/article/pii/S0022000000917276, URL: http://dx.doi.org/http://dx.doi.org/10.1006/jcss.2000.1727.
  15. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: http://www.sciencedirect.com/science/article/pii/S002200000191774X, URL: http://dx.doi.org/http://dx.doi.org/10.1006/jcss.2001.1774.
  16. Mikio Kano and Xueliang Li. Monochromatic and heterochromatic subgraphs in edge-colored graphs - a survey. Graphs and Combinatorics, 24(4):237-263, 2008. Google Scholar
  17. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. In Automata, Languages, and Programming, volume 7965 of Lecture Notes in Computer Science, pages 613-624. Springer Berlin Heidelberg, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_52.
  18. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Information Processing Letters, 114(10):556-560, 2014. URL: http://www.sciencedirect.com/science/article/pii/S0020019014000969, URL: http://dx.doi.org/http://dx.doi.org/10.1016/j.ipl.2014.05.001.
  19. Stefan Kratsch and Magnus Wahlstrom. Representative sets and irrelevant vertices: New tools for kernelization. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 0:450-459, 2012. URL: http://dx.doi.org/http://doi.ieeecomputersociety.org/10.1109/FOCS.2012.46.
  20. Daniel Lokshtanov. Wheel-free deletion is W[2]-Hard. In Martin Grohe and Rolf Niedermeier, editors, Parameterized and Exact Computation, volume 5018 of Lecture Notes in Computer Science, pages 141-147. Springer Berlin Heidelberg, 2008. URL: http://dx.doi.org/10.1007/978-3-540-79723-4_14,
  21. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Trans. Algorithms, 11(2):15:1-15:31, October 2014. URL: http://doi.acm.org/10.1145/2566616, URL: http://dx.doi.org/10.1145/2566616.
  22. Dániel Marx. Chordal deletion is fixed-parameter tractable. In FedorV. Fomin, editor, Graph-Theoretic Concepts in Computer Science, volume 4271 of Lecture Notes in Computer Science, pages 37-48. Springer Berlin Heidelberg, 2006. URL: http://dx.doi.org/10.1007/11917496_4,
  23. Dániel Marx. Can you beat treewidth? In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS'07, pages 169-179, Washington, DC, USA, 2007. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2007.18,
  24. Dániel Marx and Ildiko Schlotter. Obtaining a planar graph by vertex deletion. In Graph-Theoretic Concepts in Computer Science, volume 4769 of Lecture Notes in Computer Science, pages 292-303. Springer Berlin Heidelberg, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74839-7_28.
  25. Pranabendu Misra, Venkatesh Raman, M.S. Ramanujan, and Saket Saurabh. Parameterized algorithms for even cycle transversal. In MartinCharles Golumbic, Michal Stern, Avivit Levy, and Gila Morgenstern, editors, Graph-Theoretic Concepts in Computer Science, volume 7551 of Lecture Notes in Computer Science, pages 172-183. Springer Berlin Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-34611-8_19,
  26. Bruce Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Operations Research Letters, 32(4):299-301, 2004. URL: http://www.sciencedirect.com/science/article/pii/S0167637703001482, URL: http://dx.doi.org/http://dx.doi.org/10.1016/j.orl.2003.10.009.
  27. Stéphan Thomassé. A 4k² kernel for feedback vertex set. ACM Trans. Algorithms, 6(2):32:1-32:8, April 2010. URL: http://doi.acm.org/10.1145/1721837.1721848, URL: http://dx.doi.org/10.1145/1721837.1721848.
  28. Mingyu Xiao and Hiroshi Nagamochi. An improved exact algorithm for undirected feedback vertex set. In Peter Widmayer, Yinfeng Xu, and Binhai Zhu, editors, Combinatorial Optimization and Applications, volume 8287 of Lecture Notes in Computer Science, pages 153-164. Springer International Publishing, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03780-6_14,
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail