2 Search Results for "Yang, Shizhou"

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.51

Computing Tree Decompositions with Small Independence Number

Authors: Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP-hard graph problems, like maximum weight independent set, can be solved in time n^𝒪(k) if the input n-vertex graph is given together with a tree decomposition of independence number k. Yolov in [SODA 2018] gave an algorithm that given an n-vertex graph G and an integer k, in time n^𝒪(k³) either constructs a tree decomposition of G whose independence number is 𝒪(k³) or correctly reports that the tree-independence number of G is larger than k. In this paper, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time 2^𝒪(k²) n^𝒪(k) and either outputs a tree decomposition of G with independence number at most 8k, or determines that the tree-independence number of G is larger than k. This implies 2^𝒪(k²) n^𝒪(k)-time algorithms for various problems, like maximum weight independent set, parameterized by the tree-independence number k without needing the decomposition as an input. Assuming Gap-ETH, an n^Ω(k) factor in the running time is unavoidable for any approximation algorithm for the tree-independence number. Our second result is that the exact computation of the tree-independence number is para-NP-hard: We show that for every constant k ≥ 4 it is NP-hard to decide if a given graph has the tree-independence number at most k.

Cite as

Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič. Computing Tree Decompositions with Small Independence Number. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dallard_et_al:LIPIcs.ICALP.2024.51,
  author =	{Dallard, Cl\'{e}ment and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Milani\v{c}, Martin},
  title =	{{Computing Tree Decompositions with Small Independence Number}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{51:1--51:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.51},
  URN =		{urn:nbn:de:0030-drops-201945},
  doi =		{10.4230/LIPIcs.ICALP.2024.51},
  annote =	{Keywords: tree-independence number, approximation, parameterized algorithms}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2023.34

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs

Authors: Esther Galby, Andrea Munaro, and Shizhou Yang

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graph classes. Our approach unifies and extends several known polynomial-time approximation schemes on seemingly unrelated graph classes, such as classes of intersection graphs of fat objects in a fixed dimension or proper minor-closed classes. We also study the related notion of layered tree-independence number, a relaxation of layered treewidth.

Cite as

Esther Galby, Andrea Munaro, and Shizhou Yang. Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.SoCG.2023.34,
  author =	{Galby, Esther and Munaro, Andrea and Yang, Shizhou},
  title =	{{Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.34},
  URN =		{urn:nbn:de:0030-drops-178840},
  doi =		{10.4230/LIPIcs.SoCG.2023.34},
  annote =	{Keywords: Independent packings, intersection graphs, polynomial-time approximation schemes, tree-independence number}
}

Refine by Author
1 Dallard, Clément
1 Fomin, Fedor V.
1 Galby, Esther
1 Golovach, Petr A.
1 Korhonen, Tuukka
Show More...

Refine by Classification
1 Mathematics of computing → Graph algorithms
1 Theory of computation → Approximation algorithms analysis
1 Theory of computation → Graph algorithms analysis
1 Theory of computation → Parameterized complexity and exact algorithms

Refine by Keyword
2 tree-independence number
1 Independent packings
1 approximation
1 intersection graphs
1 parameterized algorithms
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2023
1 2024