Search Results

Documents authored by Gonçalves, Daniel

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}
}
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 About DROPS Imprint Privacy Contact