Search Results

Documents authored by Jaffke, Lars

Document
DOI: 10.4230/LIPIcs.IPEC.2023.7
Treewidth Is NP-Complete on Cubic Graphs

Authors: Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, and Ondřej Suchý

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.
Cite as

Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, and Ondřej Suchý. Treewidth Is NP-Complete on Cubic Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2023.7,
  author =	{Bodlaender, Hans L. and Bonnet, \'{E}douard and Jaffke, Lars and Knop, Du\v{s}an and Lima, Paloma T. and Milani\v{c}, Martin and Ordyniak, Sebastian and Pandey, Sukanya and Such\'{y}, Ond\v{r}ej},
  title =	{{Treewidth Is NP-Complete on Cubic Graphs}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.7},
  URN =		{urn:nbn:de:0030-drops-194263},
  doi =		{10.4230/LIPIcs.IPEC.2023.7},
  annote =	{Keywords: Treewidth, cubic graphs, degree, NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.26
Dynamic Programming on Bipartite Tree Decompositions

Authors: Lars Jaffke, Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number. Intuitively, a bipartite tree decomposition is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one vertex from the bipartite part of any other bag, while the width of such decomposition measures how far the bags are from being bipartite. Adapted from a tree decomposition originally defined by Demaine, Hajiaghayi, and Kawarabayashi [SODA 2010] and explicitly defined by Tazari [Theor. Comput. Sci. 2012], bipartite treewidth appears to play a crucial role for solving problems related to odd-minors, which have recently attracted considerable attention. As a first step toward a theory for solving these problems efficiently, the main goal of this paper is to develop dynamic programming techniques to solve problems on graphs of small bipartite treewidth. For such graphs, we provide a number of para-NP-completeness results, FPT-algorithms, and XP-algorithms, as well as several open problems. In particular, we show that K_t-Subgraph-Cover, Weighted Vertex Cover/Independent Set, Odd Cycle Transversal, and Maximum Weighted Cut are FPT parameterized by bipartite treewidth. We also provide the following complexity dichotomy when H is a 2-connected graph, for each of the H-Subgraph-Packing, H-Induced-Packing, H-Scattered-Packing, and H-Odd-Minor-Packing problems: if H is bipartite, then the problem is para-NP-complete parameterized by bipartite treewidth while, if H is non-bipartite, then the problem is solvable in XP-time. Beyond bipartite treewidth, we define 1-ℋ-treewidth by replacing the bipartite graph class by any graph class ℋ. Most of the technology developed here also works for this more general parameter.
Cite as

Lars Jaffke, Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos. Dynamic Programming on Bipartite Tree Decompositions. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2023.26,
  author =	{Jaffke, Lars and Morelle, Laure and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Dynamic Programming on Bipartite Tree Decompositions}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.26},
  URN =		{urn:nbn:de:0030-drops-194455},
  doi =		{10.4230/LIPIcs.IPEC.2023.26},
  annote =	{Keywords: tree decomposition, bipartite graphs, dynamic programming, odd-minors, packing, maximum cut, vertex cover, independent set, odd cycle transversal}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.40
Structural Parameterizations of b-Coloring

Authors: Lars Jaffke, Paloma T. Lima, and Roohani Sharma

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

Abstract
The b-Coloring problem, which given a graph G and an integer k asks whether G has a proper k-coloring such that each color class has a vertex adjacent to all color classes except its own, is known to be FPT parameterized by the vertex cover number and XP and 𝖶[1]-hard parameterized by clique-width. Its complexity when parameterized by the treewidth of the input graph remained an open problem. We settle this question by showing that b-Coloring is XNLP-complete when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathwidth is 𝖶[t]-hard for all t, and resolves the parameterized complexity of b-Coloring parameterized by treewidth. We complement this result by showing that b-Coloring is FPT when parameterized by neighborhood diversity and by twin cover, two parameters that generalize vertex cover to more dense graphs, but are incomparable to pathwidth.
Cite as

Lars Jaffke, Paloma T. Lima, and Roohani Sharma. Structural Parameterizations of b-Coloring. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.ISAAC.2023.40,
  author =	{Jaffke, Lars and Lima, Paloma T. and Sharma, Roohani},
  title =	{{Structural Parameterizations of b-Coloring}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{40:1--40:14},
  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.40},
  URN =		{urn:nbn:de:0030-drops-193429},
  doi =		{10.4230/LIPIcs.ISAAC.2023.40},
  annote =	{Keywords: b-coloring, structural parameterization, XNLP, pathwidth, neighborhood diversity, twin cover}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.3
On the Hardness of Generalized Domination Problems Parameterized by Mim-Width

Authors: Brage I. K. Bakkane and Lars Jaffke

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
For nonempty σ, ρ ⊆ ℕ, a vertex set S in a graph G is a (σ, ρ)-dominating set if for all v ∈ S, |N(v) ∩ S| ∈ σ, and for all v ∈ V(G) ⧵ S, |N(v) ∩ S| ∈ ρ. The Min/Max (σ,ρ)-Dominating Set problems ask, given a graph G and an integer k, whether G contains a (σ, ρ)-dominating set of size at most k and at least k, respectively. This framework captures many well-studied graph problems related to independence and domination. Bui-Xuan, Telle, and Vatshelle [TCS 2013] showed that for finite or co-finite σ and ρ, the Min/Max (σ,ρ)-Dominating Set problems are solvable in XP time parameterized by the mim-width of a given branch decomposition of the input graph. In this work we consider the parameterized complexity of these problems and obtain the following: For minimization problems, we complete several scattered W[1]-hardness results in the literature to a full dichotomoy into polynomial-time solvable and W[1]-hard cases, and for maximization problems we obtain the same result under the additional restriction that σ and ρ are finite sets. All W[1]-hard cases hold assuming that a linear branch decomposition of bounded mim-width is given, and with the solution size being an additional part of the parameter. Furthermore, for all W[1]-hard cases we also rule out f(w)n^o(w/log w)-time algorithms assuming the Exponential Time Hypothesis, where f is any computable function, n is the number of vertices and w the mim-width of the given linear branch decomposition of the input graph.
Cite as

Brage I. K. Bakkane and Lars Jaffke. On the Hardness of Generalized Domination Problems Parameterized by Mim-Width. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bakkane_et_al:LIPIcs.IPEC.2022.3,
  author =	{Bakkane, Brage I. K. and Jaffke, Lars},
  title =	{{On the Hardness of Generalized Domination Problems Parameterized by Mim-Width}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.3},
  URN =		{urn:nbn:de:0030-drops-173597},
  doi =		{10.4230/LIPIcs.IPEC.2022.3},
  annote =	{Keywords: generalized domination, linear mim-width, W\lbrack1\rbrack-hardness, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.8
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure

Authors: Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, and Paloma T. Lima

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna [ToCT 2018], that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, (q-)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, and Bipartite Bandwidth.
Cite as

Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, and Paloma T. Lima. XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2022.8,
  author =	{Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo and Jaffke, Lars and Lima, Paloma T.},
  title =	{{XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.8},
  URN =		{urn:nbn:de:0030-drops-173640},
  doi =		{10.4230/LIPIcs.IPEC.2022.8},
  annote =	{Keywords: parameterized complexity, XNLP, linear clique-width, W-hierarchy, pathwidth, linear mim-width, bandwidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.58
Taming Graphs with No Large Creatures and Skinny Ladders

Authors: Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ 𝒢 contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from 𝒢. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).
Cite as

Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza. Taming Graphs with No Large Creatures and Skinny Ladders. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 58:1-58:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gajarsky_et_al:LIPIcs.ESA.2022.58,
  author =	{Gajarsk\'{y}, Jakub and Jaffke, Lars and Lima, Paloma T. and Novotn\'{a}, Jana and Pilipczuk, Marcin and Rz\k{a}\.{z}ewski, Pawe{\l} and Souza, U\'{e}verton S.},
  title =	{{Taming Graphs with No Large Creatures and Skinny Ladders}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{58:1--58:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.58},
  URN =		{urn:nbn:de:0030-drops-169969},
  doi =		{10.4230/LIPIcs.ESA.2022.58},
  annote =	{Keywords: Minimal separator, hereditary graph class}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.38
Classes of Intersection Digraphs with Good Algorithmic Properties

Authors: Lars Jaffke, O-joung Kwon, and Jan Arne Telle

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions towards a better understanding of the algorithmic treatment of intersection digraphs. First, we introduce natural classes of intersection digraphs that generalize several classes studied in the literature. Second, we define the directed locally checkable vertex (DLCV) problems, which capture many well-studied problems on digraphs such as (Independent) Dominating Set, Kernel, and H-Homomorphism. Third, we give a new width measure of digraphs, bi-mim-width, and show that the DLCV problems are polynomial-time solvable when we are provided a decomposition of small bi-mim-width. Fourth, we show that several classes of intersection digraphs have bounded bi-mim-width, implying that we can solve all DLCV problems on these classes in polynomial time given an intersection representation of the input digraph. We identify reflexivity as a useful condition to obtain intersection digraph classes of bounded bi-mim-width, and therefore to obtain positive algorithmic results.
Cite as

Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Classes of Intersection Digraphs with Good Algorithmic Properties. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.STACS.2022.38,
  author =	{Jaffke, Lars and Kwon, O-joung and Telle, Jan Arne},
  title =	{{Classes of Intersection Digraphs with Good Algorithmic Properties}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.38},
  URN =		{urn:nbn:de:0030-drops-158480},
  doi =		{10.4230/LIPIcs.STACS.2022.38},
  annote =	{Keywords: intersection digraphs, H-digraphs, reflexive digraphs, directed domination, directed H-homomorphism}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.63
A Unifying Framework for Characterizing and Computing Width Measures

Authors: Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify ℱ-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of ℱ-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can approximate every possible ℱ-branchwidth, providing a unifying parameterized framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions.
Cite as

Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon. A Unifying Framework for Characterizing and Computing Width Measures. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 63:1-63:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.ITCS.2022.63,
  author =	{Eiben, Eduard and Ganian, Robert and Hamm, Thekla and Jaffke, Lars and Kwon, O-joung},
  title =	{{A Unifying Framework for Characterizing and Computing Width Measures}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{63:1--63:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.63},
  URN =		{urn:nbn:de:0030-drops-156592},
  doi =		{10.4230/LIPIcs.ITCS.2022.63},
  annote =	{Keywords: branchwidth, parameterized algorithms, mim-width, treewidth, clique-width}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.43
b-Coloring Parameterized by Clique-Width

Authors: Lars Jaffke, Paloma T. Lima, and Daniel Lokshtanov

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial-time results on graph classes, and answers open questions posed by Campos and Silva [Algorithmica, 2018] and Bonomo et al. [Graphs Combin., 2009]. This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b-Coloring and Fall Coloring are tight under the Exponential Time Hypothesis.
Cite as

Lars Jaffke, Paloma T. Lima, and Daniel Lokshtanov. b-Coloring Parameterized by Clique-Width. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.STACS.2021.43,
  author =	{Jaffke, Lars and Lima, Paloma T. and Lokshtanov, Daniel},
  title =	{{b-Coloring Parameterized by Clique-Width}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.43},
  URN =		{urn:nbn:de:0030-drops-136881},
  doi =		{10.4230/LIPIcs.STACS.2021.43},
  annote =	{Keywords: b-Coloring, clique-width, vertex cover, structural parameterization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.26
Diverse Pairs of Matchings

Authors: Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov

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

Abstract
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if k is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by k. We round off the work by showing that Diverse Pair of Matchings has a kernel on 𝒪(k²) vertices.
Cite as

Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov. Diverse Pairs of Matchings. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.ISAAC.2020.26,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Jaffke, Lars and Philip, Geevarghese and Sagunov, Danil},
  title =	{{Diverse Pairs of Matchings}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{26:1--26:12},
  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.26},
  URN =		{urn:nbn:de:0030-drops-133706},
  doi =		{10.4230/LIPIcs.ISAAC.2020.26},
  annote =	{Keywords: Matching, Solution Diversity, Fixed-Parameter Tractability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.49
Structural Parameterizations of Clique Coloring

Authors: Lars Jaffke, Paloma T. Lima, and Geevarghese Philip

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with q colors. For fixed q ≥ 2, we give an 𝒪^⋆(q^{tw})-time algorithm when the input graph is given together with one of its tree decompositions of width tw. We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is XP parameterized by clique-width.
Cite as

Lars Jaffke, Paloma T. Lima, and Geevarghese Philip. Structural Parameterizations of Clique Coloring. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.MFCS.2020.49,
  author =	{Jaffke, Lars and Lima, Paloma T. and Philip, Geevarghese},
  title =	{{Structural Parameterizations of Clique Coloring}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.49},
  URN =		{urn:nbn:de:0030-drops-127157},
  doi =		{10.4230/LIPIcs.MFCS.2020.49},
  annote =	{Keywords: clique coloring, treewidth, clique-width, structural parameterization, Strong Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.50
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

Authors: Lars Jaffke, Mateus de Oliveira Oliveira, and Hans Raj Tiwary

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+|G|) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can be embedded in the n-clique K_n, a connected graph with n vertices. In this work, we show that the minimum size of a context-free grammar generating a finite permutation group G⊑ 𝕊_n can be upper bounded by three structural parameters of connected graphs embedding G: the number of vertices, the treewidth, and the maximum degree. More precisely, we show that any permutation group G ⊑ 𝕊_n that can be embedded into a connected graph with m vertices, treewidth k, and maximum degree Δ, can also be generated by a context-free grammar of size 2^{O(kΔlogΔ)}⋅ m^{O(k)}. By combining our upper bound with a connection established by Pesant, Quimper, Rousseau and Sellmann [Gilles Pesant et al., 2009] between the extension complexity of a permutation group and the grammar complexity of a formal language, we also get that these permutation groups can be represented by polytopes of extension complexity 2^{O(kΔlogΔ)}⋅ m^{O(k)}. The above upper bounds can be used to provide trade-offs between the index of permutation groups, and the number of vertices, treewidth and maximum degree of connected graphs embedding these groups. In particular, by combining our main result with a celebrated 2^{Ω(n)} lower bound on the grammar complexity of the symmetric group 𝕊_n due to Glaister and Shallit [Glaister and Shallit, 1996] we have that connected graphs of treewidth o(n/log n) and maximum degree o(n/log n) embedding subgroups of 𝕊_n of index 2^{cn} for some small constant c must have n^{ω(1)} vertices. This lower bound can be improved to exponential on graphs of treewidth n^{ε} for ε < 1 and maximum degree o(n/log n).
Cite as

Lars Jaffke, Mateus de Oliveira Oliveira, and Hans Raj Tiwary. Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.MFCS.2020.50,
  author =	{Jaffke, Lars and de Oliveira Oliveira, Mateus and Tiwary, Hans Raj},
  title =	{{Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.50},
  URN =		{urn:nbn:de:0030-drops-127161},
  doi =		{10.4230/LIPIcs.MFCS.2020.50},
  annote =	{Keywords: Permutation Groups, Context Free Grammars, Extension Complexity, Graph Embedding Complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.57
Typical Sequences Revisited - Computing Width Parameters of Graphs

Authors: Hans L. Bodlaender, Lars Jaffke, and Jan Arne Telle

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in ?(n²) time.
Cite as

Hans L. Bodlaender, Lars Jaffke, and Jan Arne Telle. Typical Sequences Revisited - Computing Width Parameters of Graphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.STACS.2020.57,
  author =	{Bodlaender, Hans L. and Jaffke, Lars and Telle, Jan Arne},
  title =	{{Typical Sequences Revisited - Computing Width Parameters of Graphs}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{57:1--57:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.57},
  URN =		{urn:nbn:de:0030-drops-119189},
  doi =		{10.4230/LIPIcs.STACS.2020.57},
  annote =	{Keywords: typical sequences, treewidth, series parallel digraphs, cutwidth, modified cutwidth}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.34
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs

Authors: Lars Jaffke and Paloma T. Lima

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has a b-coloring with k colors. The b-chromatic number of a graph G, denoted by chi_b(G), is the maximum number k such that G admits a b-coloring with k colors. We consider the complexity of the b-Coloring problem, whenever the value of k is close to one of two upper bounds on chi_b(G): The maximum degree Delta(G) plus one, and the m-degree, denoted by m(G), which is defined as the maximum number i such that G has i vertices of degree at least i-1. We obtain a dichotomy result for all fixed k in N when k is close to one of the two above mentioned upper bounds. Concretely, we show that if k in {Delta(G) + 1 - p, m(G) - p}, the problem is polynomial-time solvable whenever p in {0, 1} and, even when k = 3, it is NP-complete whenever p >= 2. We furthermore consider parameterizations of the b-Coloring problem that involve the maximum degree Delta(G) of the input graph G and give two FPT-algorithms. First, we show that deciding whether a graph G has a b-coloring with m(G) colors is FPT parameterized by Delta(G). Second, we show that b-Coloring{} is FPT parameterized by Delta(G) + l_k(G), where l_k(G) denotes the number of vertices of degree at least k.
Cite as

Lars Jaffke and Paloma T. Lima. A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.MFCS.2019.34,
  author =	{Jaffke, Lars and Lima, Paloma T.},
  title =	{{A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{34:1--34:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.34},
  URN =		{urn:nbn:de:0030-drops-109784},
  doi =		{10.4230/LIPIcs.MFCS.2019.34},
  annote =	{Keywords: b-Coloring, b-Chromatic Number}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.6
Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width

Authors: Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
We generalize the family of (sigma, rho)-problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as distance-r dominating set and distance-r independent set. We show that these distance problems are XP parameterized by the structural parameter mim-width, and hence polynomial on graph classes where mim-width is bounded and quickly computable, such as k-trapezoid graphs, Dilworth k-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, k-polygon graphs, circular arc graphs, complements of d-degenerate graphs, and H-graphs if given an H-representation. To supplement these findings, we show that many classes of (distance) (sigma, rho)-problems are W[1]-hard parameterized by mim-width + solution size.
Cite as

Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2018.6,
  author =	{Jaffke, Lars and Kwon, O-joung and Str{\o}mme, Torstein J. F. and Telle, Jan Arne},
  title =	{{Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.6},
  URN =		{urn:nbn:de:0030-drops-102074},
  doi =		{10.4230/LIPIcs.IPEC.2018.6},
  annote =	{Keywords: Graph Width Parameters, Graph Classes, Distance Domination Problems, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.21
Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width

Authors: Lars Jaffke, O-joung Kwon, and Jan Arne Telle

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

Abstract
We give the first polynomial-time algorithms on graphs of bounded maximum induced matching width (mim-width) for problems that are not locally checkable. In particular, we give n^O(w)-time algorithms on graphs of mim-width at most w, when given a decomposition, for the following problems: Longest Induced Path, Induced Disjoint Paths and H-Induced Topological Minor for fixed H. Our results imply that the following graph classes have polynomial-time algorithms for these three problems: Interval and Bi-Interval graphs, Circular Arc, Per- mutation and Circular Permutation graphs, Convex graphs, k-Trapezoid, Circular k-Trapezoid, k-Polygon, Dilworth-k and Co-k-Degenerate graphs for fixed k.
Cite as

Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2017.21,
  author =	{Jaffke, Lars and Kwon, O-joung and Telle, Jan Arne},
  title =	{{Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{21:1--21:13},
  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.21},
  URN =		{urn:nbn:de:0030-drops-85643},
  doi =		{10.4230/LIPIcs.IPEC.2017.21},
  annote =	{Keywords: graph width parameters, dynamic programming, graph classes, induced paths, induced topological minors}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.42
A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width

Authors: Lars Jaffke, O-joung Kwon, and Jan Arne Telle

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
We give a first polynomial-time algorithm for (Weighted) Feedback Vertex Set on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width w, we give an n^{O(w)}-time algorithm that solves Feedback Vertex Set. This provides a unified algorithm for many well-known classes, such as Interval graphs and Permutation graphs, and furthermore, it gives the first polynomial-time algorithms for other classes of bounded mim-width, such as Circular Permutation and Circular k-Trapezoid graphs for fixed k. In all these classes the decomposition is computable in polynomial time, as shown by Belmonte and Vatshelle [Theor. Comput. Sci. 2013]. We show that powers of graphs of tree-width w-1 or path-width w and powers of graphs of clique-width w have mim-width at most w. These results extensively provide new classes of bounded mim-width. We prove a slight strengthening of the first statement which implies that, surprisingly, Leaf Power graphs which are of importance in the field of phylogenetic studies have mim-width at most 1. Given a tree decomposition of width w-1, a path decomposition of width w, or a clique-width w-expression of a graph G, one can for any value of k find a mim-width decomposition of its k-power in polynomial time, and apply our algorithm to solve Feedback Vertex Set on the k-power in time n^{O(w)}. In contrast to Feedback Vertex Set, we show that Hamiltonian Cycle is NP-complete even on graphs of linear mim-width 1, which further hints at the expressive power of the mim-width parameter.
Cite as

Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.STACS.2018.42,
  author =	{Jaffke, Lars and Kwon, O-joung and Telle, Jan Arne},
  title =	{{A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.42},
  URN =		{urn:nbn:de:0030-drops-85348},
  doi =		{10.4230/LIPIcs.STACS.2018.42},
  annote =	{Keywords: graph width parameters, graph classes, feedback vertex set, leaf powers}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.175
Definability Equals Recognizability for k-Outerplanar Graphs

Authors: Lars Jaffke and Hans L. Bodlaender

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
One of the most famous algorithmic meta-theorems states that every graph property that can be defined by a sentence in counting monadic second order logic (CMSOL) can be checked in linear time for graphs of bounded treewidth, which is known as Courcelle's Theorem. These algorithms are constructed as finite state tree automata, and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e., every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. We prove this conjecture for k-outerplanar graphs, which are known to have treewidth at most 3k-1.
Cite as

Lars Jaffke and Hans L. Bodlaender. Definability Equals Recognizability for k-Outerplanar Graphs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 175-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2015.175,
  author =	{Jaffke, Lars and Bodlaender, Hans L.},
  title =	{{Definability Equals Recognizability for k-Outerplanar Graphs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{175--186},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.175},
  URN =		{urn:nbn:de:0030-drops-55815},
  doi =		{10.4230/LIPIcs.IPEC.2015.175},
  annote =	{Keywords: treewidth, monadic second order logic of graphs, finite state tree automata, \$k\$-outerplanar graphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact