DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2024.38

Finding Induced Subgraphs from Graphs with Small Mim-Width

Authors: Yota Otachi, Akira Suzuki, and Yuma Tamura

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract

In the last decade, algorithmic frameworks based on a structural graph parameter called mim-width have been developed to solve generally NP-hard problems. However, it is known that the frameworks cannot be applied to the Clique problem, and the complexity status of many problems of finding dense induced subgraphs remains open when parameterized by mim-width. In this paper, we investigate the complexity of the problem of finding a maximum induced subgraph that satisfies prescribed properties from a given graph with small mim-width. We first give a meta-theorem implying that various induced subgraph problems are NP-hard for bounded mim-width graphs. Moreover, we show that some problems, including Clique and Induced Cluster Subgraph, remain NP-hard even for graphs with (linear) mim-width at most 2. In contrast to the intractability, we provide an algorithm that, given a graph and its branch decomposition with mim-width at most 1, solves Induced Cluster Subgraph in polynomial time. We emphasize that our algorithmic technique is applicable to other problems such as Induced Polar Subgraph and Induced Split Subgraph. Since a branch decomposition with mim-width at most 1 can be constructed in polynomial time for block graphs, interval graphs, permutation graphs, cographs, distance-hereditary graphs, convex graphs, and their complement graphs, our positive results reveal the polynomial-time solvability of various problems for these graph classes.

Cite as

Yota Otachi, Akira Suzuki, and Yuma Tamura. Finding Induced Subgraphs from Graphs with Small Mim-Width. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{otachi_et_al:LIPIcs.SWAT.2024.38,
  author =	{Otachi, Yota and Suzuki, Akira and Tamura, Yuma},
  title =	{{Finding Induced Subgraphs from Graphs with Small Mim-Width}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.38},
  URN =		{urn:nbn:de:0030-drops-200788},
  doi =		{10.4230/LIPIcs.SWAT.2024.38},
  annote =	{Keywords: mim-width, graph algorithm, NP-hardness, induced subgraph problem, cluster vertex deletion}
}

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.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}
}

Search Results

Documents authored by Tamura, Yuma

Finding Induced Subgraphs from Graphs with Small Mim-Width

Abstract

Cite as

Minimization and Parameterized Variants of Vertex Partition Problems on Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message