Search Results

Documents authored by Dupré la Tour, Max

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.83
On the Hardness of Recognizing Graphs of Small Mim-Width and Its Variants

Authors: Max Dupré la Tour, Manuel Lafond, and Ndiamé Ndiaye

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

Abstract
The mim-width of a graph is a powerful structural parameter that, when bounded by a constant, allows several hard problems to be polynomial-time solvable - with a recent meta-theorem encompassing a large class of problems [SODA2023]. Since its introduction, several variants such as sim-width and omim-width were developed, along with a linear version of these parameters. It was recently shown that mim-width and all these variants are all paraNP-hard, a consequence of the NP-hardness of distinguishing between graphs of linear mim-width at most 1211 and graphs of sim-width at least 1216 [ICALP2025]. The complexity of recognizing graphs of small width, particularly those close to 1, remained open, despite their especially attractive algorithmic applications. In this work, we show that the width recognition problems remain NP-hard even on small widths. Specifically, after introducing the novel parameter Omim-width sandwiched between omim-width and mim-width, we show that: (1) deciding whether a graph has sim-width = 1, omim-width = 1, or Omim-width = 1 is NP-hard, and the same is true for their linear variants; (2) the problems of deciding whether mim-width ≤ 2 or linear mim-width ≤ 2 are both NP-hard. Interestingly, our reductions are relatively simple and are from the Unrooted Quartet Consistency problem, which is of great interest in computational biology but is not commonly used in the theory of algorithms.
Cite as

Max Dupré la Tour, Manuel Lafond, and Ndiamé Ndiaye. On the Hardness of Recognizing Graphs of Small Mim-Width and Its Variants. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 83:1-83:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duprelatour_et_al:LIPIcs.ICALP.2026.83,
  author =	{Dupr\'{e} la Tour, Max and Lafond, Manuel and Ndiaye, Ndiam\'{e}},
  title =	{{On the Hardness of Recognizing Graphs of Small Mim-Width and Its Variants}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{83:1--83:18},
  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.83},
  URN =		{urn:nbn:de:0030-drops-264725},
  doi =		{10.4230/LIPIcs.ICALP.2026.83},
  annote =	{Keywords: Mim-width, NP-hardness, Computational Biology}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.84
Faster and Simpler Greedy Algorithm for k-Median and k-Means

Authors: Max Dupré la Tour and David Saulpic

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

Abstract
Clustering problems such as k-means and k-median are staples of unsupervised learning, and many algorithmic techniques have been developed to tackle their numerous aspects. In this paper, we focus on the class of greedy approximation algorithm, that attracted less attention than local-search or primal-dual counterparts. In particular, we study the recursive greedy algorithm developed by Mettu and Plaxton [SIAM J. Comp 2003]. We provide a simplification of the algorithm, allowing for faster implementation: our algorithm matches the state-of-the-art running time for computing a constant-factor approximation in Euclidean space and graph metrics, and, in addition, is the first near-linear-time to compute a polylogarithmic approximation in Euclidean space.
Cite as

Max Dupré la Tour and David Saulpic. Faster and Simpler Greedy Algorithm for k-Median and k-Means. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duprelatour_et_al:LIPIcs.ICALP.2026.84,
  author =	{Dupr\'{e} la Tour, Max and Saulpic, David},
  title =	{{Faster and Simpler Greedy Algorithm for k-Median and k-Means}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{84:1--84:16},
  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.84},
  URN =		{urn:nbn:de:0030-drops-264735},
  doi =		{10.4230/LIPIcs.ICALP.2026.84},
  annote =	{Keywords: Clustering, k-means, approximation algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.72
k-Leaf Powers Cannot Be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5

Authors: Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye, and Adrian Vetta

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

Abstract
A graph G = (V,E) is a k-leaf power if there is a tree T whose leaves are the vertices of G, with the property that a pair of distinct leaves u and v share an edge in G if and only if they are distance at most k apart in T. For k ≤ 4, it is known that there exists a finite set F_k of graphs such that the class ℒ(k) of k-leaf power graphs is characterized as the set of strongly chordal graphs that do not contain any graph in F_k as an induced subgraph. We prove no such characterization holds for k ≥ 5. That is, for any k ≥ 5, there is no finite set F_k of graphs such that ℒ(k) is equivalent to the set of strongly chordal graphs that do not contain as an induced subgraph any graph in F_k.
Cite as

Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye, and Adrian Vetta. k-Leaf Powers Cannot Be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 72:1-72:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{duprelatour_et_al:LIPIcs.ICALP.2025.72,
  author =	{Dupr\'{e} la Tour, Max and Lafond, Manuel and Ndiaye, Ndiam\'{e} and Vetta, Adrian},
  title =	{{k-Leaf Powers Cannot Be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{72:1--72:17},
  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.72},
  URN =		{urn:nbn:de:0030-drops-234499},
  doi =		{10.4230/LIPIcs.ICALP.2025.72},
  annote =	{Keywords: Leaf Powers, Forbidden Graph Characterizations, Strongly Chordal Graphs}
}
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