Document Open Access Logo

Structural Parameterizations of Feedback Vertex Set

Author Diptapriyo Majumdar

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.21.pdf
  • Filesize: 0.64 MB
  • 16 pages

Document Identifiers

Author Details

Diptapriyo Majumdar

Cite As Get BibTex

Diptapriyo Majumdar. Structural Parameterizations of Feedback Vertex Set. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.IPEC.2016.21

Abstract

A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. It is well-known that the problem of finding a minimum sized (or k sized in case of decision version of) feedback vertex set (FVS) is polynomial time solvable in (sub)-cubic graphs, in pseudo-forests (graphs where each component has at most one cycle) and mock-forests (graph where each vertex is part of at most one cycle). In general graphs, it is known that the problem is NP-Complete, and has an O*((3.619)^k) fixed-parameter algorithm and an O(k^2) kernel where k, the solution size is the parameter. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure of the input. In particular, we show that

* FVS is fixed-parameter tractable, but is unlikely to have polynomial sized kernel when parameterized by the number of vertices of the graph whose degree is at least 4. This answers a question asked in an earlier paper.

* When parameterized by k, the number of vertices, whose deletion results in a pseudo-forest, we give an O(k^6) vertices kernel improving from the previously known O(k^{10}) bound.

* When parameterized by the number k of vertices, whose deletion results in a mock-d-forest, we give a kernel consisting of O(k^{3d+3}) vertices and prove a lower bound of Omega(k^{d+2}) vertices (under complexity theoretic assumptions). Mock-d-forest for a constant d is a mock-forest where each component has at most d cycles.

Subject Classification

Keywords
  • Parameterized Complexity
  • Kernelization
  • Feedback Vertex Set
  • Structural Parameterization

Metrics

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

References

  1. E. Balas and C. S. Yu. On graphs with polynomially solvable maximum-weight clique problem. Networks, 19(2):247-253, 1989. Google Scholar
  2. H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch. Kernelization lower bounds by cross-composition. SIAM J. Discrete Math., 28(1):277-305, 2014. Google Scholar
  3. H. L. Bodlaender, S. Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci., 412(35):4570-4578, 2011. Google Scholar
  4. H. L. Bodlaender and T. C. van Dijk. A cubic kernel for feedback vertex set and loop cutset. Theory Comput. Syst., 46(3):566-597, 2010. Google Scholar
  5. Y. Cao, J. Chen, and Y. Liu. On feedback vertex set: New measure and new structures. Algorithmica, 73(1):63-86, 2015. Google Scholar
  6. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  7. H. Dell and D. van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM, 61(4):23:1-23:27, 2014. Google Scholar
  8. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  9. M. R. Fellows, B. M. P. Jansen, and F. A. Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb., 34(3):541-566, 2013. Google Scholar
  10. F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh. Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. In Proceedings of FOCS, pages 470-479, 2012. Google Scholar
  11. L. Fortnow and R. Santhanam. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. Google Scholar
  12. T. Fujito. A unified approximation algorithm for node-deletion problems. Discrete Applied Mathematics, 86(2-3):213-231, 1998. Google Scholar
  13. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  14. G. Gutin, E. J. Kim, M. Lampis, and V. Mitsou. Vertex cover problem parameterized above and below tight bounds. Theory Comput. Syst., 48(2):402-410, 2011. Google Scholar
  15. B. M. P. Jansen and S. Kratsch. Data reduction for graph coloring problems. Inf. Comput., 231:70-88, 2013. Google Scholar
  16. B. M. P. Jansen, V. Raman, and M. Vatshelle. Parameter ecology for feedback vertex set. Tsinghua Science and Technology, 19(4):387-409, 2014. Google Scholar
  17. T. Kloks, C. Liu, and S. Poon. Feedback vertex set on chordal bipartite graphs. CoRR, abs/1104.3915v2, 2011. Google Scholar
  18. T. Kociumaka and M. Pilipczuk. Faster deterministic feedback vertex set. Inf. Process. Lett., 114(10):556-560, 2014. Google Scholar
  19. D. Kratsch, H. Müller, and I. Todinca. Feedback vertex set on at-free graphs. Discrete Applied Mathematics, 156(10):1936-1947, 2008. Google Scholar
  20. R. Rizzi. Minimum weakly fundamental cycle bases are hard to find. Algorithmica, 53(3):402-424, 2009. Google Scholar
  21. S. Thomassé. A 4k² kernel for feedback vertex set. ACM Trans. Algorithms, 6(2), 2010. Google Scholar
  22. S. Ueno, Y. Kajitani, and S. Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics, 72(1-3):355-360, 1988. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact