Search Results

Documents authored by Picavet, Timothé

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.4
Induced Disjoint Paths Without an Induced Minor

Authors: Pierre Aboulker, Édouard Bonnet, Timothé Picavet, and Nicolas Trotignon

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

Abstract
We exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs - which avoids the 1-subdivision of, say, K₅ as an induced minor - Induced 2-Disjoint Paths is NP-complete. So, while k-Disjoint Paths, for a fixed k, is polynomial-time solvable in general graphs, the absence of a graph as an induced minor does not make its induced variant tractable, even for k = 2. This answers a question of Korhonen and Lokshtanov [SODA '24], and complements a polynomial-time algorithm for Induced k-Disjoint Paths in classes of bounded genus by Kobayashi and Kawarabayashi [SODA '09]. In addition to being string graphs, our produced hard instances are subgraphs of a constant power of bounded-degree planar graphs, hence have bounded twin-width and bounded maximum degree. We also leverage our new result to show that there is a fixed subcubic graph H such that deciding if an input graph contains H as an induced subdivision is NP-complete. Until now, all the graphs H for which such a statement was known had a vertex of degree at least 4. This answers a question by Chudnovsky, Seymour, and Trotignon [JCTB '13], and by Le [JGT '19]. Finally we resolve another question of Korhonen and Lokshtanov by exhibiting a subcubic graph H without two adjacent degree-3 vertices and such that deciding if an input n-vertex graph contains H as an induced minor is NP-complete, and unless the Exponential-Time Hypothesis fails, requires time 2^{Ω(√ n)}. This complements an algorithm running in subexponential time 2^{Õ(n^{2/3})} by these authors [SODA '24] under the same technical condition.
Cite as

Pierre Aboulker, Édouard Bonnet, Timothé Picavet, and Nicolas Trotignon. Induced Disjoint Paths Without an Induced Minor. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aboulker_et_al:LIPIcs.ICALP.2025.4,
  author =	{Aboulker, Pierre and Bonnet, \'{E}douard and Picavet, Timoth\'{e} and Trotignon, Nicolas},
  title =	{{Induced Disjoint Paths Without an Induced Minor}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{4:1--4:14},
  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.4},
  URN =		{urn:nbn:de:0030-drops-233813},
  doi =		{10.4230/LIPIcs.ICALP.2025.4},
  annote =	{Keywords: Induced Disjoint Paths, string graphs, induced subdivisions, induced minors}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.33
A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items

Authors: Mathieu Mari, Timothé Picavet, and Michał Pilipczuk

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal is to pack as many of these rectangles inside the box without overlap. Naturally, this problem is NP-complete. Recently, Grandoni et al. [ESA'19] showed that it is also 𝖶[1]-hard when parameterized by the size k of the sought packing, and they presented a parameterized approximation scheme (PAS) for the variant where we are allowed to rotate the rectangles by 90° before packing them into the box. Obtaining a PAS for the original 2D-Knapsack problem, without rotation, appears to be a challenging open question. In this work, we make progress towards this goal by showing a PAS under the following assumptions: - both the box and all the input rectangles have integral, polynomially bounded sidelengths; - every input rectangle is wide - its width is greater than its height; and - the aspect ratio of the box is bounded by a constant. Our approximation scheme relies on a mix of various parameterized and approximation techniques, including color coding, rounding, and searching for a structured near-optimum packing using dynamic programming.
Cite as

Mathieu Mari, Timothé Picavet, and Michał Pilipczuk. A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mari_et_al:LIPIcs.IPEC.2023.33,
  author =	{Mari, Mathieu and Picavet, Timoth\'{e} and Pilipczuk, Micha{\l}},
  title =	{{A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{33:1--33:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.33},
  URN =		{urn:nbn:de:0030-drops-194529},
  doi =		{10.4230/LIPIcs.IPEC.2023.33},
  annote =	{Keywords: Parameterized complexity, Approximation scheme, Geometric knapsack, Color coding, Dynamic programming, Computational geometry}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.40
Brief Announcement: Distributed Derandomization Revisited

Authors: Sameep Dahal, Francesco d'Amore, Henrik Lievonen, Timothé Picavet, and Jukka Suomela

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
One of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves a locally checkable labeling problem (LCL) can be derandomized with at most exponential overhead. The original proof assumes that the number of random bits is bounded by some function of the input size. We give a new, simple proof that does not make any such assumptions - it holds even if the randomized algorithm uses infinitely many bits. While at it, we also broaden the scope of the result so that it is directly applicable far beyond LCL problems.
Cite as

Sameep Dahal, Francesco d'Amore, Henrik Lievonen, Timothé Picavet, and Jukka Suomela. Brief Announcement: Distributed Derandomization Revisited. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 40:1-40:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dahal_et_al:LIPIcs.DISC.2023.40,
  author =	{Dahal, Sameep and d'Amore, Francesco and Lievonen, Henrik and Picavet, Timoth\'{e} and Suomela, Jukka},
  title =	{{Brief Announcement: Distributed Derandomization Revisited}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{40:1--40:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.40},
  URN =		{urn:nbn:de:0030-drops-191660},
  doi =		{10.4230/LIPIcs.DISC.2023.40},
  annote =	{Keywords: Distributed algorithm, Derandomization, LOCAL model}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact