Search Results

Documents authored by Gonçalves, Daniel

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.27
Plane Strong Connectivity Augmentation

Authors: Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph D can be augmented with (any number of) arcs X such that D+X is strongly connected, but still plane and oriented, is NP-hard. The hardness also holds for the planar variant. This question becomes trivial within plane (or planar) digraphs, like most connectivity augmentation problems without a budget constraint. The budgeted variant, Plane Strong Connectivity Augmentation (PSCA) considers a plane oriented graph D along with some integer k, and asks for an X of size at most k ensuring that D+X is strongly connected, while remaining plane and oriented. Our main result is a fixed-parameter tractable algorithm for PSCA, running in time 2^O(k) n² log n. The cornerstone of our procedure is a structural result showing that, for any fixed k, each face admits a bounded number of partial solutions "dominating" all others. Then, our algorithm for PSCA combines face-wise branching with a randomized reduction to the polynomial Minimum Dijoin problem, yielding a Monte-Carlo FPT algorithm, which we derandomize. To the best of our knowledge, this is the first FPT algorithm for a (hard) connectivity augmentation problem constrained by planarity.
Cite as

Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald, and Dimitrios M. Thilikos. Plane Strong Connectivity Augmentation. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 27:1-27:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bessy_et_al:LIPIcs.ICALP.2026.27,
  author =	{Bessy, St\'{e}phane and Gon\c{c}alves, Daniel and Reinald, Amadeus and Thilikos, Dimitrios M.},
  title =	{{Plane Strong Connectivity Augmentation}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{27:1--27:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.27},
  URN =		{urn:nbn:de:0030-drops-264163},
  doi =		{10.4230/LIPIcs.ICALP.2026.27},
  annote =	{Keywords: Connectivity augmentation, Directed graphs, Parameterized complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.26
Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set

Authors: Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph G and a parameter k, one has to decide if there is a set S of at most k vertices such that G-S is acyclic. Assuming the Exponential Time Hypothesis, it is known that FVS cannot be solved in time 2^{o(k)}n^{𝒪(1)} in general graphs. To overcome this, many recent results considered FVS restricted to particular intersection graph classes and provided such 2^{o(k)}n^{𝒪(1)} algorithms. In this paper we provide generic conditions on a graph class for the existence of an algorithm solving FVS in subexponential FPT time, i.e. time 2^k^ε poly(n), for some ε < 1, where n denotes the number of vertices of the instance and k the parameter. On the one hand this result unifies algorithms that have been proposed over the years for several graph classes such as planar graphs, map graphs, unit-disk graphs, pseudo-disk graphs, and string graphs of bounded edge-degree. On the other hand it extends the tractability horizon of FVS to new classes that are not amenable to previously used techniques, in particular intersection graphs of "thin" objects like segment graphs or more generally s-string graphs.
Cite as

Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.ICALP.2025.26,
  author =	{Berthe, Ga\'{e}tan and Bougeret, Marin and Gon\c{c}alves, Daniel and Raymond, Jean-Florent},
  title =	{{Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.26},
  URN =		{urn:nbn:de:0030-drops-234036},
  doi =		{10.4230/LIPIcs.ICALP.2025.26},
  annote =	{Keywords: Subexponential FPT algorithms, geometric intersection graphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2024.13
Kick the Cliques

Authors: Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
In the K_r-Hitting problem, given a graph G and an integer k one has to decide if there exists a set of at most k vertices whose removal destroys all r-cliques of G. In this paper we give an algorithm for K_r-Hitting that runs in subexponential FPT time on graph classes satisfying two simple conditions related to cliques and treewidth. As an application we show that our algorithm solves K_r-Hitting in time - 2^{O_r(k^{(r+1)/(r+2)}log k)} ⋅ n^{O_r(1)} in pseudo-disk graphs and map-graphs; - 2^{O_{t,r}(k^{2/3}log k)} ⋅ n^{O_r(1)} in K_{t,t}-subgraph-free string graphs; and - 2^{O_{H,r}(k^{2/3}log k)} ⋅ n^{O_r(1)} in H-minor-free graphs.
Cite as

Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Kick the Cliques. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.IPEC.2024.13,
  author =	{Berthe, Ga\'{e}tan and Bougeret, Marin and Gon\c{c}alves, Daniel and Raymond, Jean-Florent},
  title =	{{Kick the Cliques}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.13},
  URN =		{urn:nbn:de:0030-drops-222397},
  doi =		{10.4230/LIPIcs.IPEC.2024.13},
  annote =	{Keywords: Subexponential FPT algorithms, implicit hitting set problems, geometric intersection graphs}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.11
Subexponential Algorithms in Geometric Graphs via the Subquadratic Grid Minor Property: The Role of Local Radius

Authors: Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We investigate the existence in geometric graph classes of subexponential parameterized algorithms for cycle-hitting problems like Triangle Hitting (TH), Feedback Vertex Set (FVS) or Odd Cycle Transversal (OCT). These problems respectively ask for the existence in a graph G of a set X of at most k vertices such that G-X is triangle-free, acyclic, or bipartite. It is know that subexponential FPT algorithms of the form 2^o(k)n^𝒪(1) exist in planar and even H-minor free graphs from bidimensionality theory [Demaine et al. 2005], and there is a recent line of work lifting these results to geometric graph classes consisting of intersection of similarly sized "fat" objects ([Fomin et al. 2012], [Grigoriev et al. 2014], or disk graphs [Lokshtanov et al. 2022], [An et al. 2023]). In this paper we first identify sufficient conditions, for any graph class 𝒞 included in string graphs, to admit subexponential FPT algorithms for any problem in 𝒫, a family of bidimensional problems where one has to find a set of size at most k hitting a fixed family of graphs, containing in particular FVS. Informally, these conditions boil down to the fact that for any G ∈ 𝒞, the local radius of G (a new parameter introduced in [Lokshtanov et al. 2023]) is polynomial in the clique number of G and in the maximum matching in the neighborhood of a vertex. To demonstrate the applicability of this generic result, we bound the local radius for two special classes: intersection graphs of axis-parallel squares and of contact graphs of segments in the plane. This implies that any problem Π ∈ 𝒫 (in particular, FVS) can be solved in: - 2^𝒪(k^{3/4}log k) n^𝒪(1)-time in contact segment graphs, - 2^𝒪(k^{9/10}log k) n^𝒪(1) in intersection graphs of axis-parallel squares On the positive side, we also provide positive results for TH by solving it in: - 2^𝒪(k^{3/4}log k) n^𝒪(1)-time in contact segment graphs, - 2^𝒪(√dt²(log t)k^{2/3}log k) n^𝒪(1)-time in K_{t,t}-free d-DIR graphs (intersection of segments with d slopes) On the negative side, assuming the ETH we rule out the existence of algorithms solving: - TH and OCT in time 2^o(n) in 2-DIR graphs and more generally in time 2^o(√{Δn}) in 2-DIR graphs with maximum degree Δ, and - TH, FVS, and OCT in time 2^o(√n) in K_{2,2}-free contact-2-DIR graphs of maximum degree 6. Observe that together, these results show that the absence of large K_{t,t} is a necessary and sufficient condition for the existence of subexponential FPT algorithms for TH in 2-DIR.
Cite as

Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Subexponential Algorithms in Geometric Graphs via the Subquadratic Grid Minor Property: The Role of Local Radius. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.SWAT.2024.11,
  author =	{Berthe, Ga\'{e}tan and Bougeret, Marin and Gon\c{c}alves, Daniel and Raymond, Jean-Florent},
  title =	{{Subexponential Algorithms in Geometric Graphs via the Subquadratic Grid Minor Property: The Role of Local Radius}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.11},
  URN =		{urn:nbn:de:0030-drops-200519},
  doi =		{10.4230/LIPIcs.SWAT.2024.11},
  annote =	{Keywords: geometric intersection graphs, subexponential FPT algorithms, cycle-hitting problems, bidimensionality}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.38
On Comparable Box Dimension

Authors: Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Two boxes in ℝ^d are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph G is the minimum integer d such that G can be represented as a touching graph of comparable axis-aligned boxes in ℝ^d. We show that proper minor-closed classes have bounded comparable box dimension and explore further properties of this notion.
Cite as

Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On Comparable Box Dimension. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2022.38,
  author =	{Dvo\v{r}\'{a}k, Zden\v{e}k and Gon\c{c}alves, Daniel and Lahiri, Abhiruk and Tan, Jane and Ueckerdt, Torsten},
  title =	{{On Comparable Box Dimension}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.38},
  URN =		{urn:nbn:de:0030-drops-160461},
  doi =		{10.4230/LIPIcs.SoCG.2022.38},
  annote =	{Keywords: geometric graphs, minor-closed graph classes, treewidth fragility}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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