3 Search Results for "Defrain, Oscar"

Document
DOI: 10.4230/LIPIcs.IPEC.2021.21
Close Relatives (Of Feedback Vertex Set), Revisited

Authors: Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk

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

Abstract
At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon (Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth, IPEC 2020, LIPIcs vol. 180, pp. 3:1-3:17) showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a 2^{o(k log k)} ⋅ n^{𝒪(1)}-time algorithm on graphs of treewidth at most k, assuming the Exponential Time Hypothesis. This contrasts with the 3^{k} ⋅ k^{𝒪(1)} ⋅ n-time algorithm for FVS using the Cut&Count technique. During their live talk at IPEC 2020, Bergougnoux et al. posed a number of open questions, which we answer in this work. - Subset Even Cycle Transversal, Subset Odd Cycle Transversal, Subset Feedback Vertex Set can be solved in time 2^{𝒪(k log k)} ⋅ n in graphs of treewidth at most k. This matches a lower bound for Even Cycle Transversal of Bergougnoux et al. and improves the polynomial factor in some of their upper bounds. - Subset Feedback Vertex Set and Node Multiway Cut can be solved in time 2^{𝒪(k log k)} ⋅ n, if the input graph is given as a cliquewidth expression of size n and width k. - Odd Cycle Transversal can be solved in time 4^k ⋅ k^{𝒪(1)} ⋅ n if the input graph is given as a cliquewidth expression of size n and width k. Furthermore, the existence of a constant ε > 0 and an algorithm performing this task in time (4-ε)^k ⋅ n^{𝒪(1)} would contradict the Strong Exponential Time Hypothesis. A common theme of the first two algorithmic results is to represent connectivity properties of the current graph in a state of a dynamic programming algorithm as an auxiliary forest with 𝒪(k) nodes. This results in a 2^{𝒪(k log k)} bound on the number of states for one node of the tree decomposition or cliquewidth expression and allows to compare two states in k^{𝒪(1)} time, resulting in linear time dependency on the size of the graph or the input cliquewidth expression.
Cite as

Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk. Close Relatives (Of Feedback Vertex Set), Revisited. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jacob_et_al:LIPIcs.IPEC.2021.21,
  author =	{Jacob, Hugo and Bellitto, Thomas and Defrain, Oscar and Pilipczuk, Marcin},
  title =	{{Close Relatives (Of Feedback Vertex Set), Revisited}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{21:1--21:15},
  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.21},
  URN =		{urn:nbn:de:0030-drops-154049},
  doi =		{10.4230/LIPIcs.IPEC.2021.21},
  annote =	{Keywords: feedback vertex set, treewidth, cliquewidth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.63
Neighborhood Inclusions for Minimal Dominating Sets Enumeration: Linear and Polynomial Delay Algorithms in P_7 - Free and P_8 - Free Chordal Graphs

Authors: Oscar Defrain and Lhouari Nourine

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

Abstract
In [M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. SIAM Journal on Discrete Mathematics, 28(4):1916–1929, 2014.] the authors give an O(n+m) delay algorithm based on neighborhood inclusions for the enumeration of minimal dominating sets in split and P_6-free chordal graphs. In this paper, we investigate generalizations of this technique to P_k-free chordal graphs for larger integers k. In particular, we give O(n+m) and O(n^3 * m) delays algorithms in the classes of P_7-free and P_8-free chordal graphs. As for P_k-free chordal graphs for k >= 9, we give evidence that such a technique is inefficient as a key step of the algorithm, namely the irredundant extension problem, becomes NP-complete.
Cite as

Oscar Defrain and Lhouari Nourine. Neighborhood Inclusions for Minimal Dominating Sets Enumeration: Linear and Polynomial Delay Algorithms in P_7 - Free and P_8 - Free Chordal Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{defrain_et_al:LIPIcs.ISAAC.2019.63,
  author =	{Defrain, Oscar and Nourine, Lhouari},
  title =	{{Neighborhood Inclusions for Minimal Dominating Sets Enumeration: Linear and Polynomial Delay Algorithms in P\underline7 - Free and P\underline8 - Free Chordal Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{63:1--63:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.63},
  URN =		{urn:nbn:de:0030-drops-115591},
  doi =		{10.4230/LIPIcs.ISAAC.2019.63},
  annote =	{Keywords: Minimal dominating sets, enumeration algorithms, linear delay enumeration, chordal graphs, forbidden induced paths}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.16
Enumerating Minimal Dominating Sets in Triangle-Free Graphs

Authors: Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we prove that this is the case in triangle-free graphs. This answers a question of Kanté et al. Additionally, we show that deciding if a set of vertices of a bipartite graph can be completed into a minimal dominating set is a NP-complete problem.
Cite as

Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond. Enumerating Minimal Dominating Sets in Triangle-Free Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.STACS.2019.16,
  author =	{Bonamy, Marthe and Defrain, Oscar and Heinrich, Marc and Raymond, Jean-Florent},
  title =	{{Enumerating Minimal Dominating Sets in Triangle-Free Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.16},
  URN =		{urn:nbn:de:0030-drops-102557},
  doi =		{10.4230/LIPIcs.STACS.2019.16},
  annote =	{Keywords: Enumeration algorithms, output-polynomial algorithms, minimal dominating set, triangle-free graphs, split graphs}
}
  • Refine by Author
  • 3 Defrain, Oscar
  • 1 Bellitto, Thomas
  • 1 Bonamy, Marthe
  • 1 Heinrich, Marc
  • 1 Jacob, Hugo
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph enumeration
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Enumeration algorithms
  • 1 Minimal dominating sets
  • 1 chordal graphs
  • 1 cliquewidth
  • 1 enumeration algorithms
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2019
  • 1 2021

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