7 Search Results for "Ries, Bernard"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.29
A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width

Authors: Narek Bojikian and Stefan Kratsch

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

Abstract
Given a graph G = (V,E), a set T ⊆ V, and an integer b, the Steiner Tree problem asks whether G has a connected subgraph H with at most b vertices that spans all of T. This work presents a 3^k⋅ n^𝒪(1) time one-sided Monte-Carlo algorithm for solving Steiner Tree when additionally a clique-expression of width k is provided. Known lower bounds for less expressive parameters imply that this dependence on the clique-width of G is optimal assuming the Strong Exponential-Time Hypothesis (SETH). Indeed our work establishes that the parameter dependence of Steiner Tree is the same for any graph parameter between cutwidth and clique-width, assuming SETH. Our work contributes to the program of determining the exact parameterized complexity of fundamental hard problems relative to structural graph parameters such as treewidth, which was initiated by Lokshtanov et al. [SODA 2011 & TALG 2018] and which by now has seen a plethora of results. Since the cut-and-count framework of Cygan et al. [FOCS 2011 & TALG 2022], connectivity problems have played a key role in this program as they pose many challenges for developing tight upper and lower bounds. Recently, Hegerfeld and Kratsch [ESA 2023] gave the first application of the cut-and-count technique to problems parameterized by clique-width and obtained tight bounds for Connected Dominating Set and Connected Vertex Cover, leaving open the complexity of other benchmark connectivity problems such as Steiner Tree and Feedback Vertex Set. Our algorithm for Steiner Tree does not follow the cut-and-count technique and instead works with the connectivity patterns of partial solutions. As a first technical contribution we identify a special family of so-called complete patterns that has strong (existential) representation properties, and using these at least one solution will be preserved. Furthermore, there is a family of 3^k basis patterns that (parity) represents the complete patterns, i.e., it has the same number of solutions modulo two. Our main technical contribution, a new technique called "isolating a representative," allows us to leverage both forms of representation (existential and parity). Both complete patterns and isolation of a representative will likely be applicable to other (connectivity) problems.
Cite as

Narek Bojikian and Stefan Kratsch. A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bojikian_et_al:LIPIcs.ICALP.2024.29,
  author =	{Bojikian, Narek and Kratsch, Stefan},
  title =	{{A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{29:1--29: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.29},
  URN =		{urn:nbn:de:0030-drops-201728},
  doi =		{10.4230/LIPIcs.ICALP.2024.29},
  annote =	{Keywords: Parameterized complexity, Steiner tree, clique-width}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.31
Matching Cuts in Graphs of High Girth and H-Free Graphs

Authors: Carl Feghali, Felicia Lucke, Daniël Paulusma, and Bernard Ries

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

Abstract
The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a connected graph has a perfect matching that contains a matching cut. Both Matching Cut and Disconnected Perfect Matching are NP-complete for planar graphs of girth 5, whereas Perfect Matching Cut is known to be NP-complete even for subcubic bipartite graphs of arbitrarily large fixed girth. We prove that Matching Cut and Disconnected Perfect Matching are also NP-complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Our result for Matching Cut resolves a 20-year old open problem. We also show that the more general problem d-Cut, for every fixed d ≥ 1, is NP-complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Furthermore, we show that Matching Cut, Perfect Matching Cut and Disconnected Perfect Matching are NP-complete for H-free graphs whenever H contains a connected component with two vertices of degree at least 3. Afterwards, we update the state-of-the-art summaries for H-free graphs and compare them with each other, and with a known and full classification of the Maximum Matching Cut problem, which is to determine a largest matching cut of a graph G. Finally, by combining existing results, we obtain a complete complexity classification of Perfect Matching Cut for H-subgraph-free graphs where H is any finite set of graphs.
Cite as

Carl Feghali, Felicia Lucke, Daniël Paulusma, and Bernard Ries. Matching Cuts in Graphs of High Girth and H-Free Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{feghali_et_al:LIPIcs.ISAAC.2023.31,
  author =	{Feghali, Carl and Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard},
  title =	{{Matching Cuts in Graphs of High Girth and H-Free Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{31:1--31:16},
  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.31},
  URN =		{urn:nbn:de:0030-drops-193332},
  doi =		{10.4230/LIPIcs.ISAAC.2023.31},
  annote =	{Keywords: matching cut, perfect matching, girth, H-free graph}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.64
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius

Authors: Felicia Lucke, Daniël Paulusma, and Bernard Ries

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
The (Perfect) Matching Cut problem is to decide if a graph G has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of G. Both Matching Cut and Perfect Matching Cut are known to be NP-complete, leading to many complexity results for both problems on special graph classes. A perfect matching cut is also a matching cut with maximum number of edges. To increase our understanding of the relationship between the two problems, we introduce the Maximum Matching Cut problem. This problem is to determine a largest matching cut in a graph. We generalize and unify known polynomial-time algorithms for Matching Cut and Perfect Matching Cut restricted to graphs of diameter at most 2 and to (P₆+sP₂)-free graphs. We also show that the complexity of Maximum Matching Cut differs from the complexities of Matching Cut and Perfect Matching Cut by proving NP-hardness of Maximum Matching Cut for 2P₃-free quadrangulated graphs of diameter 3 and radius 2 and for subcubic line graphs of triangle-free graphs. In this way, we obtain full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and H-free graphs.
Cite as

Felicia Lucke, Daniël Paulusma, and Bernard Ries. Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 64:1-64:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lucke_et_al:LIPIcs.MFCS.2023.64,
  author =	{Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard},
  title =	{{Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{64:1--64:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.64},
  URN =		{urn:nbn:de:0030-drops-185981},
  doi =		{10.4230/LIPIcs.MFCS.2023.64},
  annote =	{Keywords: matching cut, perfect matching, H-free graph, diameter, radius, dichotomy}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.22
Finding Matching Cuts in H-Free Graphs

Authors: Felicia Lucke, Daniël Paulusma, and Bernard Ries

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
The well-known NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. We also prove new complexity results for two recently studied variants of Matching Cut, on H-free graphs. The first variant requires that the matching cut must be extendable to a perfect matching of the graph. The second variant requires the matching cut to be a perfect matching. In particular, we prove that there exists a small constant r > 0 such that the first variant is NP-complete for P_r-free graphs. This addresses a question of Bouquet and Picouleau (arXiv, 2020). For all three problems, we give state-of-the-art summaries of their computational complexity for H-free graphs.
Cite as

Felicia Lucke, Daniël Paulusma, and Bernard Ries. Finding Matching Cuts in H-Free Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lucke_et_al:LIPIcs.ISAAC.2022.22,
  author =	{Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard},
  title =	{{Finding Matching Cuts in H-Free Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.22},
  URN =		{urn:nbn:de:0030-drops-173076},
  doi =		{10.4230/LIPIcs.ISAAC.2022.22},
  annote =	{Keywords: matching cut, perfect matching, H-free graph, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.31
Locally Checkable Problems Parameterized by Clique-Width

Authors: Narmina Baghirova, Carolina Lucía Gonzalez, Bernard Ries, and David Schindl

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We continue the study initiated by Bonomo-Braberman and Gonzalez in 2020 on r-locally checkable problems. We propose a dynamic programming algorithm that takes as input a graph with an associated clique-width expression and solves a 1-locally checkable problem under certain restrictions. We show that it runs in polynomial time in graphs of bounded clique-width, when the number of colors of the locally checkable problem is fixed. Furthermore, we present a first extension of our framework to global properties by taking into account the sizes of the color classes, and consequently enlarge the set of problems solvable in polynomial time with our approach in graphs of bounded clique-width. As examples, we apply this setting to show that, when parameterized by clique-width, the [k]-Roman domination problem is FPT, and the k-community problem, Max PDS and other variants are XP.
Cite as

Narmina Baghirova, Carolina Lucía Gonzalez, Bernard Ries, and David Schindl. Locally Checkable Problems Parameterized by Clique-Width. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{baghirova_et_al:LIPIcs.ISAAC.2022.31,
  author =	{Baghirova, Narmina and Gonzalez, Carolina Luc{\'\i}a and Ries, Bernard and Schindl, David},
  title =	{{Locally Checkable Problems Parameterized by Clique-Width}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.31},
  URN =		{urn:nbn:de:0030-drops-173167},
  doi =		{10.4230/LIPIcs.ISAAC.2022.31},
  annote =	{Keywords: locally checkable problem, clique-width, dynamic programming, coloring}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.21
Blocking Dominating Sets for H-Free Graphs via Edge Contractions

Authors: Esther Galby, Paloma T. Lima, and Bernard Ries

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
In this paper, we consider the following problem: given a connected graph G, can we reduce the domination number of G by one by using only one edge contraction? We show that the problem is NP-hard when restricted to {P_6,P_4+P_2}-free graphs and that it is coNP-hard when restricted to subcubic claw-free graphs and 2P_3-free graphs. As a consequence, we are able to establish a complexity dichotomy for the problem on H-free graphs when H is connected.
Cite as

Esther Galby, Paloma T. Lima, and Bernard Ries. Blocking Dominating Sets for H-Free Graphs via Edge Contractions. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.ISAAC.2019.21,
  author =	{Galby, Esther and Lima, Paloma T. and Ries, Bernard},
  title =	{{Blocking Dominating Sets for H-Free Graphs via Edge Contractions}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.21},
  URN =		{urn:nbn:de:0030-drops-115171},
  doi =		{10.4230/LIPIcs.ISAAC.2019.21},
  annote =	{Keywords: domination number, blocker problem, H-free graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.41
Reducing the Domination Number of Graphs via Edge Contractions

Authors: Esther Galby, Paloma T. Lima, and Bernard Ries

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

Abstract
In this paper, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k >= 0? We show that for k <= 2, the problem is coNP-hard. We further prove that for k=1, the problem is W[1]-hard parameterized by the size of a minimum dominating set plus the mim-width of the input graph, and that it remains NP-hard when restricted to P_9-free graphs, bipartite graphs and {C_3,...,C_{l}}-free graphs for any l >= 3. Finally, we show that for any k >= 1, the problem is polynomial-time solvable for P_5-free graphs and that it can be solved in FPT-time and XP-time when parameterized by tree-width and mim-width, respectively.
Cite as

Esther Galby, Paloma T. Lima, and Bernard Ries. Reducing the Domination Number of Graphs via Edge Contractions. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.MFCS.2019.41,
  author =	{Galby, Esther and Lima, Paloma T. and Ries, Bernard},
  title =	{{Reducing the Domination Number of Graphs via Edge Contractions}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{41:1--41: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.41},
  URN =		{urn:nbn:de:0030-drops-109856},
  doi =		{10.4230/LIPIcs.MFCS.2019.41},
  annote =	{Keywords: domination number, blocker problem, graph classes}
}
  • Refine by Author
  • 6 Ries, Bernard
  • 3 Lucke, Felicia
  • 3 Paulusma, Daniël
  • 2 Galby, Esther
  • 2 Lima, Paloma T.
  • Show More...

  • Refine by Classification
  • 4 Mathematics of computing → Graph algorithms
  • 2 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Graph coloring
  • Show More...

  • Refine by Keyword
  • 3 H-free graph
  • 3 matching cut
  • 3 perfect matching
  • 2 blocker problem
  • 2 clique-width
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2019
  • 2 2022
  • 2 2023
  • 1 2024

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact