DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.11

Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width

Authors: Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, and Marek Sokołowski

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other traditional structural parameters. Having such a sequence at hand allows to solve many otherwise hard problems efficiently. Our paper focuses on a comparison of twin-width to the more traditional tree-width on sparse graphs. Namely, we prove that if a graph G of twin-width at most 2 contains no K_{t,t} subgraph for some integer t, then the tree-width of G is bounded by a polynomial function of t. As a consequence, for any sparse graph class C we obtain a polynomial time algorithm which for any input graph G ∈ C either outputs a contraction sequence of width at most c (where c depends only on C), or correctly outputs that G has twin-width more than 2. On the other hand, we present an easy example of a graph class of twin-width 3 with unbounded tree-width, showing that our result cannot be extended to higher values of twin-width.

Cite as

Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel, Petr Hliněný, Filip Pokrývka, and Marek Sokołowski. Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.ISAAC.2023.11,
  author =	{Bergougnoux, Benjamin and Gajarsk\'{y}, Jakub and Gu\'{s}piel, Grzegorz and Hlin\v{e}n\'{y}, Petr and Pokr\'{y}vka, Filip and Soko{\l}owski, Marek},
  title =	{{Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.11},
  URN =		{urn:nbn:de:0030-drops-193130},
  doi =		{10.4230/LIPIcs.ISAAC.2023.11},
  annote =	{Keywords: twin-width, tree-width, excluded grid, sparsity}
}

Document

DOI: 10.4230/LIPIcs.SAT.2022.15

Weighted Model Counting with Twin-Width

Authors: Robert Ganian, Filip Pokrývka, André Schidler, Kirill Simonov, and Stefan Szeider

Published in: LIPIcs, Volume 236, 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)

Abstract

Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and showed that many NP-hard problems are tractable for graphs of bounded twin-width, generalizing similar results for other width measures, including treewidth and clique-width. In this paper, we investigate the use of twin-width for solving the propositional satisfiability problem (SAT) and propositional model counting. We particularly focus on Bounded-ones Weighted Model Counting (BWMC), which takes as input a CNF formula F along with a bound k and asks for the weighted sum of all models with at most k positive literals. BWMC generalizes not only SAT but also (weighted) model counting. We develop the notion of "signed" twin-width of CNF formulas and establish that BWMC is fixed-parameter tractable when parameterized by the certified signed twin-width of F plus k. We show that this result is tight: it is neither possible to drop the bound k nor use the vanilla twin-width instead if one wishes to retain fixed-parameter tractability, even for the easier problem SAT. Our theoretical results are complemented with an empirical evaluation and comparison of signed twin-width on various classes of CNF formulas.

Cite as

Robert Ganian, Filip Pokrývka, André Schidler, Kirill Simonov, and Stefan Szeider. Weighted Model Counting with Twin-Width. In 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 236, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.SAT.2022.15,
  author =	{Ganian, Robert and Pokr\'{y}vka, Filip and Schidler, Andr\'{e} and Simonov, Kirill and Szeider, Stefan},
  title =	{{Weighted Model Counting with Twin-Width}},
  booktitle =	{25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-242-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{236},
  editor =	{Meel, Kuldeep S. and Strichman, Ofer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2022.15},
  URN =		{urn:nbn:de:0030-drops-166896},
  doi =		{10.4230/LIPIcs.SAT.2022.15},
  annote =	{Keywords: Weighted model counting, twin-width, parameterized complexity, SAT}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2017.19

FO Model Checking of Geometric Graphs

Authors: Petr Hlineny, Filip Pokrývka, and Bodhayan Roy

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract

Over the past two decades the main focus of research into first-order (FO) model checking algorithms has been on sparse relational structures – culminating in the FPT algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs. On contrary to that, except the case of locally bounded clique-width only little is currently known about FO model checking of dense classes of graphs or other structures. We study the FO model checking problem for dense graph classes definable by geometric means (intersection and visibility graphs). We obtain new nontrivial FPT results, e.g., for restricted subclasses of circular-arc, circle, box, disk, and polygon-visibility graphs. These results use the FPT algorithm by Gajarský et al. for FO model checking of posets of bounded width. We also complement the tractability results by related hardness reductions.

Cite as

Petr Hlineny, Filip Pokrývka, and Bodhayan Roy. FO Model Checking of Geometric Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 19:1-19:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hlineny_et_al:LIPIcs.IPEC.2017.19,
  author =	{Hlineny, Petr and Pokr\'{y}vka, Filip and Roy, Bodhayan},
  title =	{{FO Model Checking of Geometric Graphs}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{19:1--19:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.19},
  URN =		{urn:nbn:de:0030-drops-85597},
  doi =		{10.4230/LIPIcs.IPEC.2017.19},
  annote =	{Keywords: first-order logic, model checking, fixed-parameter tractability, intersection graphs, visibility graphs}
}

Search Results

Documents authored by Pokrývka, Filip

Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width

Abstract

Cite as

Weighted Model Counting with Twin-Width

Abstract

Cite as

FO Model Checking of Geometric Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message