10 Search Results for "Groenland, Carla"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.27
Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters

Authors: Hans L. Bodlaender, Carla Groenland, and Michał Pilipczuk

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows: - Binary CSP parameterized by the vertex cover number is W[3]-complete. More generally, for every positive integer d, Binary CSP parameterized by the size of a modulator to a treedepth-d graph is W[2d+1]-complete. This provides a new family of natural problems that are complete for odd levels of the W-hierarchy. - We introduce a new complexity class XSLP, defined so that Binary CSP parameterized by treedepth is complete for this class. We provide two equivalent characterizations of XSLP: the first one relates XSLP to a model of an alternating Turing machine with certain restrictions on conondeterminism and space complexity, while the second one links XSLP to the problem of model-checking first-order logic with suitably restricted universal quantification. Interestingly, the proof of the machine characterization of XSLP uses the concept of universal trees, which are prominently featured in the recent work on parity games. - We describe a new complexity hierarchy sandwiched between the W-hierarchy and the A-hierarchy: For every odd t, we introduce a parameterized complexity class S[t] with W[t] ⊆ S[t] ⊆ A[t], defined using a parameter that interpolates between the vertex cover number and the treedepth. We expect that many of the studied classes will be useful in the future for pinpointing the complexity of various structural parameterizations of graph problems.
Cite as

Hans L. Bodlaender, Carla Groenland, and Michał Pilipczuk. Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.ICALP.2023.27,
  author =	{Bodlaender, Hans L. and Groenland, Carla and Pilipczuk, Micha{\l}},
  title =	{{Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.27},
  URN =		{urn:nbn:de:0030-drops-180798},
  doi =		{10.4230/LIPIcs.ICALP.2023.27},
  annote =	{Keywords: Parameterized Complexity, Constraint Satisfaction Problems, Binary CSP, List Coloring, Vertex Cover, Treedepth, W-hierarchy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.14
Tight Bounds for Connectivity Problems Parameterized by Cutwidth

Authors: Narek Bojikian, Vera Chekan, Falko Hegerfeld, and Stefan Kratsch

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
In this work we start the investigation of tight complexity bounds for connectivity problems parameterized by cutwidth assuming the Strong Exponential-Time Hypothesis (SETH). Van Geffen et al. [Bas A. M. van Geffen et al., 2020] posed this question for Odd Cycle Transversal and Feedback Vertex Set. We answer it for these two and four further problems, namely Connected Vertex Cover, Connected Dominating Set, Steiner Tree, and Connected Odd Cycle Transversal. For the latter two problems it sufficed to prove lower bounds that match the running time inherited from parameterization by treewidth; for the others we provide faster algorithms than relative to treewidth and prove matching lower bounds. For upper bounds we first extend the idea of Groenland et al. [Carla Groenland et al., 2022] to solve what we call coloring-like problems. Such problems are defined by a symmetric matrix M over 𝔽₂ indexed by a set of colors. The goal is to count the number (modulo some prime p) of colorings of a graph such that M has a 1-entry if indexed by the colors of the end-points of any edge. We show that this problem can be solved faster if M has small rank over 𝔽_p. We apply this result to get our upper bounds for CVC and CDS. The upper bounds for OCT and FVS use a subdivision trick to get below the bounds that matrix rank would yield.
Cite as

Narek Bojikian, Vera Chekan, Falko Hegerfeld, and Stefan Kratsch. Tight Bounds for Connectivity Problems Parameterized by Cutwidth. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bojikian_et_al:LIPIcs.STACS.2023.14,
  author =	{Bojikian, Narek and Chekan, Vera and Hegerfeld, Falko and Kratsch, Stefan},
  title =	{{Tight Bounds for Connectivity Problems Parameterized by Cutwidth}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.14},
  URN =		{urn:nbn:de:0030-drops-176667},
  doi =		{10.4230/LIPIcs.STACS.2023.14},
  annote =	{Keywords: Parameterized complexity, connectivity problems, cutwidth}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.6
On the Complexity of Problems on Tree-Structured Graphs

Authors: Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk

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

Abstract
In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in f(k)n^O(1) time and f(k)log n space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on "tree-structured graphs" are complete for this class: we show that List Coloring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by log n, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a "natural home" for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most f(k)n^O(1) and use f(k)log n space. Moreover, we introduce "tree-shaped" variants of Weighted CNF-Satisfiability and Multicolor Clique that are XALP-complete.
Cite as

Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk. On the Complexity of Problems on Tree-Structured Graphs. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2022.6,
  author =	{Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo and Pilipczuk, Marcin and Pilipczuk, Micha{\l}},
  title =	{{On the Complexity of Problems on Tree-Structured Graphs}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{6:1--6:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.6},
  URN =		{urn:nbn:de:0030-drops-173626},
  doi =		{10.4230/LIPIcs.IPEC.2022.6},
  annote =	{Keywords: Parameterized Complexity, Treewidth, XALP, XNLP}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.7
On the Parameterized Complexity of Computing Tree-Partitions

Authors: Hans L. Bodlaender, Carla Groenland, and Hugo Jacob

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

Abstract
We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that, given an n-vertex graph G and an integer k, constructs a tree-partition of width O(k⁷) for G or reports that G has tree-partition width more than k, in time k^O(1) n². We can improve slightly on the approximation factor by sacrificing the dependence on k, or on n. On the other hand, we show the problem of computing tree-partition-width exactly is XALP-complete, which implies that it is W[t]-hard for all t. We deduce XALP-completeness of the problem of computing the domino treewidth. Finally, we adapt some known results on the parameter tree-partition-width and the topological minor relation, and use them to compare tree-partition-width to tree-cut width.
Cite as

Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. On the Parameterized Complexity of Computing Tree-Partitions. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2022.7,
  author =	{Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo},
  title =	{{On the Parameterized Complexity of Computing Tree-Partitions}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{7:1--7:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.7},
  URN =		{urn:nbn:de:0030-drops-173633},
  doi =		{10.4230/LIPIcs.IPEC.2022.7},
  annote =	{Keywords: Parameterized algorithms, Tree partitions, tree-partition-width, Treewidth, Domino Treewidth, Approximation Algorithms, Parameterized Complexity}
}
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-dev.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.24
List Colouring Trees in Logarithmic Space

Authors: Hans L. Bodlaender, Carla Groenland, and Hugo Jacob

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

Abstract
We show that List Colouring can be solved on n-vertex trees by a deterministic Turing machine using O(log n) bits on the worktape. Given an n-vertex graph G = (V,E) and a list L(v) ⊆ {1,… ,n} of available colours for each v ∈ V, a list colouring for G is a proper colouring c such that c(v) ∈ L(v) for all v.
Cite as

Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. List Colouring Trees in Logarithmic Space. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.ESA.2022.24,
  author =	{Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo},
  title =	{{List Colouring Trees in Logarithmic Space}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{24:1--24:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.24},
  URN =		{urn:nbn:de:0030-drops-169620},
  doi =		{10.4230/LIPIcs.ESA.2022.24},
  annote =	{Keywords: List colouring, trees, space complexity, logspace, graph algorithms, tree-partition-width}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.36
Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth

Authors: Carla Groenland, Isja Mannens, Jesper Nederlof, and Krisztina Szilágyi

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

Abstract
We study the fine-grained complexity of counting the number of colorings and connected spanning edge sets parameterized by the cutwidth and treewidth of the graph. While decompositions of small treewidth decompose the graph with small vertex separators, decompositions with small cutwidth decompose the graph with small edge separators. Let p,q ∈ ℕ such that p is a prime and q ≥ 3. We show: - If p divides q-1, there is a (q-1)^{ctw}n^{O(1)} time algorithm for counting list q-colorings modulo p of n-vertex graphs of cutwidth ctw. Furthermore, there is no ε > 0 for which there is a (q-1-ε)^{ctw} n^{O(1)} time algorithm that counts the number of list q-colorings modulo p of n-vertex graphs of cutwidth ctw, assuming the Strong Exponential Time Hypothesis (SETH). - If p does not divide q-1, there is no ε > 0 for which there exists a (q-ε)^{ctw} n^{O(1)} time algorithm that counts the number of list q-colorings modulo p of n-vertex graphs of cutwidth ctw, assuming SETH. The lower bounds are in stark contrast with the existing 2^{ctw}n^{O(1)} time algorithm to compute the chromatic number of a graph by Jansen and Nederlof [Theor. Comput. Sci.'18]. Furthermore, by building upon the above lower bounds, we obtain the following lower bound for counting connected spanning edge sets: there is no ε > 0 for which there is an algorithm that, given a graph G and a cutwidth ordering of cutwidth ctw, counts the number of spanning connected edge sets of G modulo p in time (p - ε)^{ctw} n^{O(1)}, assuming SETH. We also give an algorithm with matching running time for this problem. Before our work, even for the treewidth parameterization, the best conditional lower bound by Dell et al. [ACM Trans. Algorithms'14] only excluded 2^{o(tw)}n^{O(1)} time algorithms for this problem. Both our algorithms and lower bounds employ use of the matrix rank method, by relating the complexity of the problem to the rank of a certain "compatibility matrix" in a non-trivial way.
Cite as

Carla Groenland, Isja Mannens, Jesper Nederlof, and Krisztina Szilágyi. Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{groenland_et_al:LIPIcs.STACS.2022.36,
  author =	{Groenland, Carla and Mannens, Isja and Nederlof, Jesper and Szil\'{a}gyi, Krisztina},
  title =	{{Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{36:1--36:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.36},
  URN =		{urn:nbn:de:0030-drops-158464},
  doi =		{10.4230/LIPIcs.STACS.2022.36},
  annote =	{Keywords: connected edge sets, cutwidth, parameterized algorithms, colorings, counting modulo p}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.9
Parameterized Complexities of Dominating and Independent Set Reconfiguration

Authors: Hans L. Bodlaender, Carla Groenland, and Céline M. F. Swennenhuis

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
We settle the parameterized complexities of several variants of independent set reconfiguration and dominating set reconfiguration, parameterized by the number of tokens. We show that both problems are XL-complete when there is no limit on the number of moves and XNL-complete when a maximum length 𝓁 for the sequence is given in binary in the input. The problems are known to be XNLP-complete when 𝓁 is given in unary instead, and W[1]- and W[2]-hard respectively when 𝓁 is also a parameter. We complete the picture by showing membership in those classes. Moreover, we show that for all the variants that we consider, token sliding and token jumping are equivalent under pl-reductions. We introduce partitioned variants of token jumping and token sliding, and give pl-reductions between the four variants that have precise control over the number of tokens and the length of the reconfiguration sequence.
Cite as

Hans L. Bodlaender, Carla Groenland, and Céline M. F. Swennenhuis. Parameterized Complexities of Dominating and Independent Set Reconfiguration. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2021.9,
  author =	{Bodlaender, Hans L. and Groenland, Carla and Swennenhuis, C\'{e}line M. F.},
  title =	{{Parameterized Complexities of Dominating and Independent Set Reconfiguration}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.9},
  URN =		{urn:nbn:de:0030-drops-153920},
  doi =		{10.4230/LIPIcs.IPEC.2021.9},
  annote =	{Keywords: Parameterized complexity, independent set reconfiguration, dominating set reconfiguration, W-hierarchy, XL, XNL, XNLP}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.13
A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs

Authors: Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We show there is no such algorithm that finds a (5-ε)-approximation, for any ε > 0. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed.
Cite as

Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek. A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.DISC.2021.13,
  author =	{Bonamy, Marthe and Cook, Linda and Groenland, Carla and Wesolek, Alexandra},
  title =	{{A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.13},
  URN =		{urn:nbn:de:0030-drops-148159},
  doi =		{10.4230/LIPIcs.DISC.2021.13},
  annote =	{Keywords: Outerplanar graphs, dominating set, LOCAL model, constant-factor approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.37
Faster 3-Coloring of Small-Diameter Graphs

Authors: Michał Dębski, Marta Piecyk, and Paweł Rzążewski

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We study the 3-Coloring problem in graphs with small diameter. In 2013, Mertzios and Spirakis showed that for n-vertex diameter-2 graphs this problem can be solved in subexponential time 2^{𝒪(√{n log n})}. Whether the problem can be solved in polynomial time remains a well-known open question in the area of algorithmic graphs theory. In this paper we present an algorithm that solves 3-Coloring in n-vertex diameter-2 graphs in time 2^{𝒪(n^{1/3} log² n)}. This is the first improvement upon the algorithm of Mertzios and Spirakis in the general case, i.e., without putting any further restrictions on the instance graph. In addition to standard branchings and reducing the problem to an instance of 2-Sat, the crucial building block of our algorithm is a combinatorial observation about 3-colorable diameter-2 graphs, which is proven using a probabilistic argument. As a side result, we show that 3-Coloring can be solved in time 2^{𝒪((n log n)^{2/3})} in n-vertex diameter-3 graphs. We also generalize our algorithms to the problem of finding a list homomorphism from a small-diameter graph to a cycle.
Cite as

Michał Dębski, Marta Piecyk, and Paweł Rzążewski. Faster 3-Coloring of Small-Diameter Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{debski_et_al:LIPIcs.ESA.2021.37,
  author =	{D\k{e}bski, Micha{\l} and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Faster 3-Coloring of Small-Diameter Graphs}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.37},
  URN =		{urn:nbn:de:0030-drops-146181},
  doi =		{10.4230/LIPIcs.ESA.2021.37},
  annote =	{Keywords: 3-coloring, fine-grained complexity, subexponential-time algorithm, diameter}
}
  • Refine by Author
  • 8 Groenland, Carla
  • 6 Bodlaender, Hans L.
  • 4 Jacob, Hugo
  • 2 Pilipczuk, Michał
  • 1 Bojikian, Narek
  • Show More...

  • Refine by Classification
  • 8 Theory of computation → Parameterized complexity and exact algorithms
  • 4 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Graph coloring
  • Show More...

  • Refine by Keyword
  • 3 Parameterized Complexity
  • 3 W-hierarchy
  • 3 XNLP
  • 2 Parameterized complexity
  • 2 Treewidth
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 5 2022
  • 3 2021
  • 2 2023

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