Search Results

Documents authored by Bourneuf, Romain

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.15
A Polynomial-Time Approximation Algorithm for Complete Interval Minors

Authors: Romain Bourneuf, Julien Cocquet, Chaoliang Tang, and Stéphan Thomassé

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
As shown by Robertson and Seymour, deciding whether the complete graph K_t is a minor of an input graph G is a fixed parameter tractable problem when parameterized by t. From the approximation viewpoint, a substantial gap remains: there is no PTAS for finding the largest complete minor unless P = NP, whereas the best known result is a polytime O(√ n)-approximation algorithm by Alon, Lingas and Wahlén. We investigate the complexity of finding K_t as interval minor in ordered graphs (i.e. graphs with a linear order on the vertices, in which intervals are contracted to form minors). Our main result is a polytime f(t)-approximation algorithm, where f is triply exponential in t but independent of n. The algorithm is based on delayed decompositions and shows that ordered graphs without a K_t interval minor can be constructed via a bounded number of three operations: closure under substitutions, edge union, and concatenation of a stable set. As a byproduct, graphs avoiding K_t as an interval minor have bounded chromatic number.
Cite as

Romain Bourneuf, Julien Cocquet, Chaoliang Tang, and Stéphan Thomassé. A Polynomial-Time Approximation Algorithm for Complete Interval Minors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bourneuf_et_al:LIPIcs.APPROX/RANDOM.2025.15,
  author =	{Bourneuf, Romain and Cocquet, Julien and Tang, Chaoliang and Thomass\'{e}, St\'{e}phan},
  title =	{{A Polynomial-Time Approximation Algorithm for Complete Interval Minors}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{15:1--15:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.15},
  URN =		{urn:nbn:de:0030-drops-243814},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.15},
  annote =	{Keywords: Approximation algorithm, Ordered graphs, Interval minors, Delayed decompositions}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.28
Graphs with No Long Claws: An Improved Bound for the Analog of the Gyárfás' Path Argument

Authors: Romain Bourneuf, Jana Masaříková, Wojciech Nadara, and Marcin Pilipczuk

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
For a fixed integer t ⩾ 1, a (t-)long claw, denoted S_{t,t,t}, is the unique tree with three leaves, each at distance exactly t from the vertex of degree three. Majewski et al. [ICALP 2022, ACM ToCT 2024] proved an analog of the Gyárfás' path argument for S_{t,t,t}-free graphs: given an n-vertex S_{t,t,t}-free graph, one can delete neighborhoods of 𝒪(log n) vertices so that the remainder admits an extended strip decomposition (an appropriate generalization of partition into connected components) into particles of multiplicatively smaller size. In this work, we refine the argument of Majewski et al. to its arguably final form: we show that a constant number of neighborhoods suffice. The statement of Majewski et al. is one of the two pillars of a recent quasi-polynomial time algorithm for Maximum Weight Independent Set in S_{t,t,t}-free graphs [Gartland et al., STOC 2024]; our work immediately improves the quasi-polynomial function in the running time bound. Furthermore, our result significantly simplifies known polynomial-time algorithms for Maximum Weight Independent Set in S_{t,t,t}-free graphs with an additional sparsity assumption such as bounded degree or excluding a fixed biclique as a subgraph.
Cite as

Romain Bourneuf, Jana Masaříková, Wojciech Nadara, and Marcin Pilipczuk. Graphs with No Long Claws: An Improved Bound for the Analog of the Gyárfás' Path Argument. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bourneuf_et_al:LIPIcs.MFCS.2025.28,
  author =	{Bourneuf, Romain and Masa\v{r}{\'\i}kov\'{a}, Jana and Nadara, Wojciech and Pilipczuk, Marcin},
  title =	{{Graphs with No Long Claws: An Improved Bound for the Analog of the Gy\'{a}rf\'{a}s' Path Argument}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.28},
  URN =		{urn:nbn:de:0030-drops-241350},
  doi =		{10.4230/LIPIcs.MFCS.2025.28},
  annote =	{Keywords: long-claw-free graphs, extended strip decomposition, maximum weight independent set, Gy\'{a}rf\'{a}s' path, three in a tree}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.22
PPP-Completeness and Extremal Combinatorics

Authors: Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček, Alon Rosen, and Nikolaj I. Schwartzbach

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey’s theorem on monochromatic subgraphs and the Erdős-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard under randomized reductions in the case of Ramsey’s theorem and PWPP-hard in the case of the sunflower lemma; here "implicit” means that the collection is represented by a poly-sized circuit inducing an exponentially large number of objects. We show that several other well-known theorems from extremal combinatorics - including Erdős-Ko-Rado, Sperner, and Cayley’s formula – give rise to complete problems for PWPP and PPP. This is in contrast to the Ramsey and Erdős-Rado problems, for which establishing inclusion in PWPP has remained elusive. Besides significantly expanding the set of problems that are complete for PWPP and PPP, our work identifies some key properties of combinatorial proofs of existence that can give rise to completeness for these classes. Our completeness results rely on efficient encodings for which finding collisions allows extracting the desired substructure. These encodings are made possible by the tightness of the bounds for the problems at hand (tighter than what is known for Ramsey’s theorem and the sunflower lemma). Previous techniques for proving bounds in TFNP invariably made use of structured algorithms. Such algorithms are not known to exist for the theorems considered in this work, as their proofs "from the book" are non-constructive.
Cite as

Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček, Alon Rosen, and Nikolaj I. Schwartzbach. PPP-Completeness and Extremal Combinatorics. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bourneuf_et_al:LIPIcs.ITCS.2023.22,
  author =	{Bourneuf, Romain and Folwarczn\'{y}, Luk\'{a}\v{s} and Hub\'{a}\v{c}ek, Pavel and Rosen, Alon and Schwartzbach, Nikolaj I.},
  title =	{{PPP-Completeness and Extremal Combinatorics}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.22},
  URN =		{urn:nbn:de:0030-drops-175255},
  doi =		{10.4230/LIPIcs.ITCS.2023.22},
  annote =	{Keywords: total search problems, extremal combinatorics, PPP-completeness}
}
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