Minimization and Parameterized Variants of Vertex Partition Problems on Graphs

Tamura, Yuma; Ito, Takehiro; Zhou, Xiao

doi:10.4230/LIPIcs.ISAAC.2020.40

Abstract

Let Π₁, Π₂, …, Π_c be graph properties for a fixed integer c. Then, (Π₁, Π₂, …, Π_c)-Partition is the problem of asking whether the vertex set of a given graph can be partitioned into c subsets V₁, V₂, …, V_c such that the subgraph induced by V_i satisfies the graph property Π_i for every i ∈ {1,2, …, c}. Minimization and parameterized variants of (Π₁, Π₂, …, Π_c)-Partition have been studied for several specific graph properties, where the size of the vertex subset V₁ satisfying Π₁ is minimized or taken as a parameter. In this paper, we first show that the minimization variant is hard to approximate for any nontrivial additive hereditary graph properties, unless c = 2 and both Π₁ and Π₂ are classes of edgeless graphs. We then give FPT algorithms for the parameterized variant when restricted to the case where c = 2, Π₁ is a hereditary graph property, and Π₂ is the class of acyclic graphs.

Cite As Get BibTex

Yuma Tamura, Takehiro Ito, and Xiao Zhou. Minimization and Parameterized Variants of Vertex Partition Problems on Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.40

Author Details

Yuma Tamura

Graduate School of Information Sciences, Tohoku University, Sendai, Japan

Takehiro Ito

Graduate School of Information Sciences, Tohoku University, Sendai, Japan

Xiao Zhou

Graduate School of Information Sciences, Tohoku University, Sendai, Japan

Funding

Tamura, Yuma: Partially supported by JSPS KAKENHI Grant Number JP20J11259, Japan.
Ito, Takehiro: Partially supported by JSPS KAKENHI Grant Numbers JP18H04091 and JP19K11814, Japan.
Zhou, Xiao: Partially supported by JSPS KAKENHI Grant Number JP19K11813, Japan.

References

Vladimir E. Alekseev, Alastair Farrugia, and Vadim V. Lozin. New results on generalized graph coloring. Discrete Mathematics and Theoretical Computer Science, 6(2):215-222, 2004. URL: http://dmtcs.episciences.org/311.
Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM Journal on Discrete Mathematics, 12(3):289-297, 1999. URL: https://doi.org/10.1137/S0895480196305124.
Alastair Farrugia. Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electronic Journal of Combinatorics, 11:R46, 2004. URL: https://doi.org/10.37236/1799.
Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke. Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. Journal of Computer and System Sciences, 72(8):1386-1396, 2006. URL: https://doi.org/10.1016/j.jcss.2006.02.001.
Yoichi Iwata and Yusuke Kobayashi. Improved analysis of highest-degree branching for feedback vertex set. In Bart M. P. Jansen and Jan Arne Telle, editors, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, volume 148 of LIPIcs, pages 22:1-22:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.22.
Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen. Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs. Journal of Computer and System Sciences, 92:22-47, 2018. URL: https://doi.org/10.1016/j.jcss.2017.08.002.
Shaohua Li and Marcin Pilipczuk. An improved FPT algorithm for independent feedback vertex set. In Graph-Theoretic Concepts in Computer Science (WG 2018), pages 344-355, 2018. URL: https://doi.org/10.1007/978-3-030-00256-5_28.
Daniel Lokshtanov. Wheel-free deletion is W[2]-hard. In Parameterized and Exact Computation, Third International Workshop (IWPEC 2008), pages 141-147, 2018. URL: https://doi.org/10.1007/978-3-540-79723-4_14.
Junjie Luo, Hendrik Molter, and Ondrej Suchý. A Parameterized Complexity View on Collapsing k-Cores. In Christophe Paul and Michal Pilipczuk, editors, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), volume 115 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.7.
Dániel Marx, Barry O’sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. ACM Transactions on Algorithms, 9(4), 2013. URL: https://doi.org/10.1145/2500119.
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh. On parameterized independent feedback vertex set. Theoretical Computer Science, 461:65-75, 2012. URL: https://doi.org/10.1016/j.tcs.2012.02.012.
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. FPT algorithms for connected feedback vertex set. Journal of Combinatorial Optimization, 24(2):131-146, 2012. URL: https://doi.org/10.1007/s10878-011-9394-2.
Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (STOC'78), pages 216-226, 1978. URL: https://doi.org/10.1145/800133.804350.
Yuma Tamura, Takehiro Ito, and Xiao Zhou. Approximability of the independent feedback vertex set problem for bipartite graphs. In WALCOM: Algorithms and Computation - 14th International Conference ( 2020), pages 286-295, 2020. URL: https://doi.org/10.1007/978-3-030-39881-1_24.

Minimization and Parameterized Variants of Vertex Partition Problems on Graphs

Authors Yuma Tamura, Takehiro Ito , Xiao Zhou

File

Document Identifiers

Subject Classification

ACM Subject Classification

Keywords

Metrics

Abstract

Cite As Get BibTex

Author Details

References

Thanks for your feedback!

Could not send message