1 Search Results for "Tamura, Yuma"

Document

DOI: 10.4230/LIPIcs.ISAAC.2020.40

Minimization and Parameterized Variants of Vertex Partition Problems on Graphs

Authors: Yuma Tamura, Takehiro Ito, and Xiao Zhou

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

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

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)

Copy BibTex To Clipboard

@InProceedings{tamura_et_al:LIPIcs.ISAAC.2020.40,
  author =	{Tamura, Yuma and Ito, Takehiro and Zhou, Xiao},
  title =	{{Minimization and Parameterized Variants of Vertex Partition Problems on Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{40:1--40:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.40},
  URN =		{urn:nbn:de:0030-drops-133844},
  doi =		{10.4230/LIPIcs.ISAAC.2020.40},
  annote =	{Keywords: Graph Algorithms, Approximability, Fixed-Parameter Tractability, Vertex Partition Problem, Feedback Vertex Set Problem}
}

Refine by Author
1 Ito, Takehiro
1 Tamura, Yuma
1 Zhou, Xiao

Refine by Classification
1 Mathematics of computing → Graph algorithms

Refine by Keyword
1 Approximability
1 Feedback Vertex Set Problem
1 Fixed-Parameter Tractability
1 Graph Algorithms
1 Vertex Partition Problem

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Tamura, Yuma"

Minimization and Parameterized Variants of Vertex Partition Problems on Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message