Document Open Access Logo

Independent Feedback Vertex Set for P_5-free Graphs

Authors Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2017.16.pdf
  • Filesize: 0.56 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • feedback vertex set
  • odd cycle transversal
  • independent set
  • H-free graph

Metrics

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

Abstract

The NP-complete problem Feedback Vertex Set is to decide if it is possible, for a given integer k>=0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding if a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P_4-free graphs. We show that it remains in P for P_5-free graphs. We prove analogous results for the  Independent Odd Cycle Transversal problem, which asks if a graph has an independent odd cycle transversal of size at most k for a given integer k>=0.

Cite As Get BibTex

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Independent Feedback Vertex Set for P_5-free Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.16

Author Details

Marthe Bonamy
Konrad K. Dabrowski
Carl Feghali
Matthew Johnson
Daniël Paulusma

References

  1. Akanksha Agrawal, Sushmita Gupta, Saket Saurabh, and Roohani Sharma. Improved algorithms and combinatorial bounds for independent feedback vertex set. Proc. IPEC 2016, LIPIcs, 63:2:1-2:14, 2017. Google Scholar
  2. Gábor Bacsó and Zsolt Tuza. Dominating cliques in P₅-free graphs. Periodica Mathematica Hungarica, 21(4):303-308, 1990. Google Scholar
  3. Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Recognizing graphs close to bipartite graphs. Proc. MFCS 2017, LIPIcs, 83:70:1-70:14, 2017. Google Scholar
  4. Andreas Brandstädt, Synara Brito, Sulamita Klein, Loana Tito Nogueira, and Fábio Protti. Cycle transversals in perfect graphs and cographs. Theoretical Computer Science, 469:15-23, 2013. Google Scholar
  5. Keith Edwards. The complexity of colouring problems on dense graphs. Theoretical Computer Science, 43:337-343, 1986. Google Scholar
  6. Wayne Goddard and Michael A. Henning. Independent domination in graphs: A survey and recent results. Discrete Mathematics, 313(7):839-854, 2013. Google Scholar
  7. Petr A. Golovach and Pinar Heggernes. Choosability of P₅-free graphs. Proc. MFCS 2009, LNCS, 5734:382-391, 2009. Google Scholar
  8. Chính T. Hoàng, Marcin Kamiński, Vadim V. Lozin, Joe Sawada, and Xiao Shu. Deciding k-colorability of P₅-free graphs in polynomial time. Algorithmica, 57(1):74-81, 2010. Google Scholar
  9. Daniel Lokshantov, Martin Vatshelle, and Yngve Villanger. Independent set in P₅-free graphs in polynomial time. Proc. SODA 2014, pages 570-581, 2014. Google Scholar
  10. Dániel Marx, Barry O'Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. ACM Transactions on Algorithms, 9(4):30:1-30:35, 2013. Google Scholar
  11. Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh. On parameterized independent feedback vertex set. Theoretical Computer Science, 461:65-75, 2012. Google Scholar
  12. Andrea Munaro. On line graphs of subcubic triangle-free graphs. Discrete Mathematics, 340(6):1210-1226, 2017. Google Scholar
  13. Bert Randerath, Ingo Schiermeyer, and Meike Tewes. Three-colourability and forbidden subgraphs. II: polynomial algorithms. Discrete Mathematics, 251(1-3):137-153, 2002. Google Scholar
  14. Yuma Tamura, Takehiro Ito, and Xiao Zhou. Algorithms for the independent feedback vertex set problem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E98-A(6):1179-1188, 2015. Google Scholar
  15. Aifeng Yang and Jinjiang Yuan. Partition the vertices of a graph into one independent set and one acyclic set. Discrete Mathematics, 306(12):1207-1216, 2006. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact