20 Search Results for "Lochet, William"

Document
DOI: 10.4230/LIPIcs.ESA.2025.46
Max-Distance Sparsification for Diversification and Clustering

Authors: Soh Kumabe

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Let 𝒟 be a set family that is the solution domain of some combinatorial problem. The max-min diversification problem on 𝒟 is the problem to select k sets from 𝒟 such that the Hamming distance between any two selected sets is at least d. FPT algorithms parameterized by k+𝓁, where 𝓁 = max_{D ∈ 𝒟}|D|, and k+d have been actively studied recently for several specific domains. This paper provides unified algorithmic frameworks to solve this problem. Specifically, for each parameterization k+𝓁 and k+d, we provide an FPT oracle algorithm for the max-min diversification problem using oracles related to 𝒟. We then demonstrate that our frameworks provide the first FPT algorithms on several new domains 𝒟, including the domain of t-linear matroid intersection, almost 2-SAT, minimum edge s,t-flows, vertex sets of s,t-mincut, vertex sets of edge bipartization, and Steiner trees. We also demonstrate that our frameworks generalize most of the existing domain-specific tractability results. Our main technical breakthrough is introducing the notion of max-distance sparsifier of 𝒟, a domain on which the max-min diversification problem is equivalent to the same problem on the original domain 𝒟. The core of our framework is to design FPT oracle algorithms that construct a constant-size max-distance sparsifier of 𝒟. Using max-distance sparsifiers, we provide FPT algorithms for the max-min and max-sum diversification problems on 𝒟, as well as k-center and k-sum-of-radii clustering problems on 𝒟, which are also natural problems in the context of diversification and have their own interests.
Cite as

Soh Kumabe. Max-Distance Sparsification for Diversification and Clustering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kumabe:LIPIcs.ESA.2025.46,
  author =	{Kumabe, Soh},
  title =	{{Max-Distance Sparsification for Diversification and Clustering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.46},
  URN =		{urn:nbn:de:0030-drops-245146},
  doi =		{10.4230/LIPIcs.ESA.2025.46},
  annote =	{Keywords: Fixed-Parameter Tractability, Diversification, Clustering}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.62
Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering

Authors: Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In a seminal work, Chierichetti et al. [Chierichetti et al., 2017] introduced the (t,k)-fair clustering problem: Given a set of red points and a set of blue points in a metric space, a clustering is called fair if the number of red points in each cluster is at most t times and at least 1/t times the number of blue points in that cluster. The goal is to compute a fair clustering with at most k clusters that optimizes certain objective function. Considering this problem, they designed a polynomial-time O(1)- and O(t)-approximation for the k-center and the k-median objective, respectively. Recently, Carta et al. [Carta et al., 2024] studied this problem with the sum-of-radii objective and obtained a (6+ε)-approximation with running time O((k log_{1+ε}(k/ε))^k n^O(1)), i.e., fixed-parameter tractable in k. Here n is the input size. In this work, we design the first polynomial-time O(1)-approximation for (t,k)-fair clustering with the sum-of-radii objective, improving the result of Carta et al. Our result places sum-of-radii in the same group of objectives as k-center, that admit polynomial-time O(1)-approximations. This result also implies a polynomial-time O(1)-approximation for the Euclidean version of the problem, for which an f(k)⋅n^O(1)-time (1+ε)-approximation was known due to Drexler et al. [Drexler et al., 2023]. Here f is an exponential function of k. We are also able to extend our result to any arbitrary 𝓁 ≥ 2 number of colors when t = 1. This matches known results for the k-center and k-median objectives in this case. The significant disparity of sum-of-radii compared to k-center and k-median presents several complex challenges, all of which we successfully overcome in our work. Our main contribution is a novel cluster-merging-based analysis technique for sum-of-radii that helps us achieve the constant-approximation bounds.
Cite as

Sina Bagheri Nezhad, Sayan Bandyapadhyay, and Tianzhi Chen. Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bagherinezhad_et_al:LIPIcs.ESA.2025.62,
  author =	{Bagheri Nezhad, Sina and Bandyapadhyay, Sayan and Chen, Tianzhi},
  title =	{{Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{62:1--62:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.62},
  URN =		{urn:nbn:de:0030-drops-245309},
  doi =		{10.4230/LIPIcs.ESA.2025.62},
  annote =	{Keywords: fair clustering, sum-of-radii clustering, approximation algorithms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.23
Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints

Authors: Sayan Bandyapadhyay and Tianzhi Chen

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

Abstract
In this work, we study k-min-sum-of-radii (k-MSR) clustering under mergeable constraints. k-MSR seeks to group data points using a set of up to k balls, such that the sum of the radii of the balls is minimized. A clustering constraint is called mergeable if merging two clusters satisfying the constraint, results in a cluster that also satisfies the constraint. Many popularly studied constraints are mergeable, including fairness constraints and lower bound constraints. In our work, we design a (4+ε)-approximation for k-MSR under any given mergeable constraint with runtime 2^{O(k/(ε)⋅log²k/ε)} n⁴, i.e., fixed-parameter tractable in k for constant ε. Our result directly improves upon the FPT (6+ε)-approximation by Carta et al. [Carta et al., 2024]. We also provide a hardness result that excludes the exact solvability of k-MSR under any given mergeable constraint in time f(k)n^o(k), assuming ETH is true.
Cite as

Sayan Bandyapadhyay and Tianzhi Chen. Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.APPROX/RANDOM.2025.23,
  author =	{Bandyapadhyay, Sayan and Chen, Tianzhi},
  title =	{{Improved FPT Approximation for Sum of Radii Clustering with Mergeable Constraints}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{23:1--23:17},
  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.23},
  URN =		{urn:nbn:de:0030-drops-243894},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.23},
  annote =	{Keywords: sum-of-radii clustering, mergeable constraints, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.38
Clustering Point Sets Revisited

Authors: Md. Billal Hossain and Benjamin Raichel

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
In the sets clustering problem one is given a collection of point sets 𝒫 = {P_1,… P_m} in ℝ^d, where for any set of k centers in ℝ^d, each P_i is assigned to its nearest center as determine by some local cost functions. The goal is then to select a set of k centers to minimize some global cost function of the corresponding local assignment costs. Specifically, we consider either summing or taking the maximum cost over all P_i, where for each P_i the cost of assigning it to a center c is either max_{p ∈ P_i} ‖c-p‖, ∑_{p ∈ P_i} ‖c-p‖, or ∑_{p ∈ P_i} ‖c-p‖². Different combinations of the global and local cost functions naturally generalize the k-center, k-median, and k-means clustering problems. In this paper, we improve the prior results for the natural generalization of k-center, give the first result for the natural generalization of k-means, and give results for generalizations of k-median and k-center which differ from those previously studied.
Cite as

Md. Billal Hossain and Benjamin Raichel. Clustering Point Sets Revisited. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hossain_et_al:LIPIcs.WADS.2025.38,
  author =	{Hossain, Md. Billal and Raichel, Benjamin},
  title =	{{Clustering Point Sets Revisited}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.38},
  URN =		{urn:nbn:de:0030-drops-242693},
  doi =		{10.4230/LIPIcs.WADS.2025.38},
  annote =	{Keywords: Clustering, k-center, k-median, k-means}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.17
Robust Contraction Decomposition for Minor-Free Graphs and Its Applications

Authors: Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Dániel Marx, Pranabendu Misra, Daniel Neuen, Saket Saurabh, Prafullkumar Tale, and Jie Xue

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

Abstract
We prove a robust contraction decomposition theorem for H-minor-free graphs, which states that given an H-minor-free graph G and an integer p, one can partition in polynomial time the vertices of G into p sets Z₁,… ,Z_p such that tw(G/(Z_i ⧵ Z')) = O(p + |Z'|) for all i ∈ [p] and Z' ⊆ Z_i. Here, tw(⋅) denotes the treewidth of a graph and G/(Z_i ⧵ Z') denotes the graph obtained from G by contracting all edges with both endpoints in Z_i ⧵ Z'. Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et al. [STOC 2011] based on partitioning E(G), and some recent theorems for planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022]. The robust contraction decomposition theorem directly results in parameterized algorithms with running time 2^{Õ(√k)} ⋅ n^{O(1)} or n^{O(√k)} for every vertex/edge deletion problems on H-minor-free graphs that can be formulated as Permutation CSP Deletion or 2-Conn Permutation CSP Deletion. Consequently, we obtain the first subexponential-time parameterized algorithms for Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn Component Order Connectivity on H-minor-free graphs. For other problems which already have subexponential-time parameterized algorithms on H-minor-free graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut, etc.), our theorem gives much simpler algorithms of the same running time.
Cite as

Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Dániel Marx, Pranabendu Misra, Daniel Neuen, Saket Saurabh, Prafullkumar Tale, and Jie Xue. Robust Contraction Decomposition for Minor-Free Graphs and Its Applications. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.ICALP.2025.17,
  author =	{Bandyapadhyay, Sayan and Lochet, William and Lokshtanov, Daniel and Marx, D\'{a}niel and Misra, Pranabendu and Neuen, Daniel and Saurabh, Saket and Tale, Prafullkumar and Xue, Jie},
  title =	{{Robust Contraction Decomposition for Minor-Free Graphs and Its Applications}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{17:1--17:19},
  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.17},
  URN =		{urn:nbn:de:0030-drops-233948},
  doi =		{10.4230/LIPIcs.ICALP.2025.17},
  annote =	{Keywords: subexponential time algorithms, graph decomposition, planar graphs, minor-free graphs, graph contraction}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.53
A PTAS for TSP with Neighbourhoods over Parallel Line Segments

Authors: Benyamin Ghaseminia and Mohammad R. Salavatipour

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We consider the Travelling Salesman Problem with Neighbourhoods (TSPN) on the Euclidean plane (ℝ²) and present a Polynomial-Time Approximation Scheme (PTAS) when the neighbourhoods are parallel line segments with lengths between [1, λ] for any constant value λ ≥ 1. In TSPN (which generalizes classic TSP), each client represents a set (or neighbourhood) of points in a metric and the goal is to find a minimum cost TSP tour that visits at least one point from each client set. In the Euclidean setting, each neighbourhood is a region on the plane. TSPN is significantly more difficult than classic TSP even in the Euclidean setting, as it captures group TSP. A notable case of TSPN is when each neighbourhood is a line segment. Although there are PTASs for when neighbourhoods are fat objects (with limited overlap), TSPN over line segments is APX-hard even if all the line segments have unit length. For parallel (unit) line segments, the best approximation factor is 3√2 from more than two decades ago. The PTAS we present in this paper settles the approximability of this case of the problem. Our algorithm finds a (1 + ε)-factor approximation for an instance of the problem for n segments with lengths in [1,λ] in time n^O(λ/ε³).
Cite as

Benyamin Ghaseminia and Mohammad R. Salavatipour. A PTAS for TSP with Neighbourhoods over Parallel Line Segments. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghaseminia_et_al:LIPIcs.SoCG.2025.53,
  author =	{Ghaseminia, Benyamin and Salavatipour, Mohammad R.},
  title =	{{A PTAS for TSP with Neighbourhoods over Parallel Line Segments}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.53},
  URN =		{urn:nbn:de:0030-drops-232058},
  doi =		{10.4230/LIPIcs.SoCG.2025.53},
  annote =	{Keywords: Approximation Scheme, TSP Neighbourhood, Parallel line segments}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.17
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

Authors: Matthias Bentert, Fedor V. Fomin, and Petr A. Golovach

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths. In this problem, the input is an edge-weighted (directed or undirected) n-vertex graph G along with k terminal pairs (s_1,t_1),(s_2,t_2),…,(s_k,t_k). The task is to connect as many terminal pairs as possible by pairwise vertex-disjoint paths such that each path is a shortest path between the respective terminals. Our work is anchored in the recent breakthrough by Lochet [SODA '21], which demonstrates the polynomial-time solvability of the problem for a fixed value of k. Lochet’s result implies the existence of a polynomial-time ck-approximation for Maximum Vertex-Disjoint Shortest Paths, where c ≤ 1 is a constant. (One can guess 1/c terminal pairs to connect in k^O(1/c) time and then utilize Lochet’s algorithm to compute the solution in n^f(1/c) time.) Our first result suggests that this approximation algorithm is, in a sense, the best we can hope for. More precisely, assuming the gap-ETH, we exclude the existence of an o(k)-approximation within f(k) ⋅ poly(n) time for any function f that only depends on k. Our second result demonstrates the infeasibility of achieving an approximation ratio of m^{1/2-ε} in polynomial time, unless P = NP. It is not difficult to show that a greedy algorithm selecting a path with the minimum number of arcs results in a ⌈√𝓁⌉-approximation, where 𝓁 is the number of edges in all the paths of an optimal solution. Since 𝓁 ≤ n, this underscores the tightness of the m^{1/2-ε}-inapproximability bound. Additionally, we establish that Maximum Vertex-Disjoint Shortest Paths is fixed-parameter tractable when parameterized by 𝓁 but does not admit a polynomial kernel. Our hardness results hold for undirected graphs with unit weights, while our positive results extend to scenarios where the input graph is directed and features arbitrary (non-negative) edge weights.
Cite as

Matthias Bentert, Fedor V. Fomin, and Petr A. Golovach. Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2025.17,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A.},
  title =	{{Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.17},
  URN =		{urn:nbn:de:0030-drops-228422},
  doi =		{10.4230/LIPIcs.STACS.2025.17},
  annote =	{Keywords: Inapproximability, Fixed-parameter tractability, Parameterized approximation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.52
Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion

Authors: Séhane Bel Houari-Durand, Eduard Eiben, and Magnus Wahlström

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Given a graph G and an integer k, the H-free Edge Deletion problem asks whether there exists a set of at most k edges of G whose deletion makes G free of induced copies of H. Significant attention has been given to the kernelizability aspects of this problem - i.e., for which graphs H does the problem admit an "efficient preprocessing" procedure, known as a polynomial kernelization, where an instance I of the problem with parameter k is reduced to an equivalent instance I' whose size and parameter value are bounded polynomially in k? Although such routines are known for many graphs H where the class of H-free graphs has significant restricted structure, it is also clear that for most graphs H the problem is incompressible, i.e., admits no polynomial kernelization parameterized by k unless the polynomial hierarchy collapses. These results led Marx and Sandeep to the conjecture that H-free Edge Deletion is incompressible for any graph H with at least five vertices, unless H is complete or has at most one edge (JCSS 2022). This conjecture was reduced to the incompressibility of H-free Edge Deletion for a finite list of graphs H. We consider one of these graphs, which we dub the prison, and show that Prison-Free Edge Deletion has a polynomial kernel, refuting the conjecture. On the other hand, the same problem for the complement of the prison is incompressible.
Cite as

Séhane Bel Houari-Durand, Eduard Eiben, and Magnus Wahlström. Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{houaridurand_et_al:LIPIcs.STACS.2025.52,
  author =	{Houari-Durand, S\'{e}hane Bel and Eiben, Eduard and Wahlstr\"{o}m, Magnus},
  title =	{{Polynomial Kernel and Incompressibility for Prison-Free Edge Deletion and Completion}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.52},
  URN =		{urn:nbn:de:0030-drops-228770},
  doi =		{10.4230/LIPIcs.STACS.2025.52},
  annote =	{Keywords: Graph modification problems, parameterized complexity, polynomial kernelization}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.15
Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems

Authors: Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar, and Saket Saurabh

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In this paper, we begin the exploration of vertex-ordering problems through the lens of exponential-time approximation algorithms. In particular, we ask the following question: Can we simultaneously beat the running times of the fastest known (exponential-time) exact algorithms and the best known approximation factors that can be achieved in polynomial time? Following the recent research initiated by Esmer et al. (ESA 2022, IPEC 2023, SODA 2024) on vertex-subset problems, and by Inamdar et al. (ITCS 2024) on graph-partitioning problems, we focus on vertex-ordering problems. In particular, we give positive results for Feedback Arc Set, Optimal Linear Arrangement, Cutwidth, and Pathwidth. Most of our algorithms build upon a novel "balanced-cut" approach - which is our main conceptual contribution. This allows us to solve various problems in very general settings allowing for directed and arc-weighted input graphs. Our main technical contribution is a (1+ε)-approximation for any ε > 0 for (weighted) Feedback Arc Set in O^*((2-δ_ε)^n) time, where δ_ε > 0 is a constant only depending on ε.
Cite as

Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar, and Saket Saurabh. Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ITCS.2025.15,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Inamdar, Tanmay and Saurabh, Saket},
  title =	{{Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.15},
  URN =		{urn:nbn:de:0030-drops-226431},
  doi =		{10.4230/LIPIcs.ITCS.2025.15},
  annote =	{Keywords: Feedback Arc Set, Cutwidth, Optimal Linear Arrangement, Pathwidth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.46
Uniform Polynomial Kernel for Deletion to K_{2,p} Minor-Free Graphs

Authors: William Lochet and Roohani Sharma

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
In the F-Deletion problem, where F is a fixed finite family of graphs, the input is a graph G and an integer k, and the goal is to determine if there exists a set of at most k vertices whose deletion results in a graph that does not contain any graph of F as a minor. The F-Deletion problem encapsulates a large class of natural and interesting graph problems like Vertex Cover, Feedback Vertex Set, Treewidth-η Deletion, Treedepth-η Deletion, Pathwidth-η Deletion, Outerplanar Deletion, Vertex Planarization and many more. We study the F-Deletion problem from the kernelization perspective. In a seminal work, Fomin et al. [FOCS 2012] gave a polynomial kernel for this problem when the family F contains at least one planar graph. The asymptotic growth of the size of the kernel is not uniform with respect to the family F: that is, the size of the kernel is k^{f(F)}, for some function f that depends only on F. Later Giannopoulou et al. [TALG 2017] showed that the non-uniformity in the kernel size bound is unavoidable as Treewidth-η Deletion cannot admit a kernel of size 𝒪(k^{(η+1)/2 - ε}), for any ε > 0, unless NP ⊆ coNP/poly. On the other hand it was also shown that Treedepth-η Deletion admits a uniform kernel of size f(F) ⋅ k⁶ depicting that there are subclasses of F where the asymptotic kernel sizes do not grow as a function of the family F. This work led to the question of determining classes of F where the problem admits uniform polynomial kernels. In this paper, we show that if all the graphs in F are connected and ℱ contains K_{2,p} (a bipartite graph with 2 vertices on one side and p vertices on the other), then the problem admits a uniform kernel of size f(F) ⋅ k^10. The graph K_{2,p} is one natural extension of the graph θ_p, where θ_p is a graph on two vertices and p parallel edges. The case when F contains θ_p has been studied earlier and serves as (the only) other example where the problem admits a uniform polynomial kernel.
Cite as

William Lochet and Roohani Sharma. Uniform Polynomial Kernel for Deletion to K_{2,p} Minor-Free Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lochet_et_al:LIPIcs.ISAAC.2024.46,
  author =	{Lochet, William and Sharma, Roohani},
  title =	{{Uniform Polynomial Kernel for Deletion to K\underline\{2,p\} Minor-Free Graphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.46},
  URN =		{urn:nbn:de:0030-drops-221731},
  doi =		{10.4230/LIPIcs.ISAAC.2024.46},
  annote =	{Keywords: Uniform polynomial kernel, ℱ-minor-free deletion, complete bipartite minor-free graphs, K\underline\{2,p\}, protrusions}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.11
Minimum-Membership Geometric Set Cover, Revisited

Authors: Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We revisit a natural variant of the geometric set cover problem, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set S of points and a set ℛ of geometric objects, and the goal is to find a subset ℛ^* ⊆ ℛ to cover all points in S such that the membership of S with respect to ℛ^*, denoted by memb(S,ℛ^*), is minimized, where memb(S,ℛ^*) = max_{p ∈ S} |{R ∈ ℛ^*: p ∈ R}|. We give the first polynomial-time approximation algorithms for MMGSC in ℝ². Specifically, we achieve the following two main results. - We give the first polynomial-time constant-approximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constant-approximation algorithm with running time n^{O(opt)} where opt is the optimum of the problem (i.e., the minimum membership). - We give the first polynomial-time approximation scheme (PTAS) for MMGSC with halfplanes. Prior to this work, it was even unknown whether the problem can be approximated with a factor of o(log n) in polynomial time, while it is well-known that the minimum-size set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimum-ply geometric set cover (MPGSC), in which the goal is to find ℛ^* ⊆ ℛ to cover S such that the ply of ℛ^* is minimized, where the ply is defined as the maximum number of objects in ℛ^* which have a nonempty common intersection. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in O(n^{12}) time. We give a significantly simpler constant-approximation algorithm with near-linear running time.
Cite as

Sayan Bandyapadhyay, William Lochet, Saket Saurabh, and Jie Xue. Minimum-Membership Geometric Set Cover, Revisited. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.11,
  author =	{Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket and Xue, Jie},
  title =	{{Minimum-Membership Geometric Set Cover, Revisited}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.11},
  URN =		{urn:nbn:de:0030-drops-178610},
  doi =		{10.4230/LIPIcs.SoCG.2023.11},
  annote =	{Keywords: geometric set cover, geometric optimization, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.12
FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii

Authors: Sayan Bandyapadhyay, William Lochet, and Saket Saurabh

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Clustering with capacity constraints is a fundamental problem that attracted significant attention throughout the years. In this paper, we give the first FPT constant-factor approximation algorithm for the problem of clustering points in a general metric into k clusters to minimize the sum of cluster radii, subject to non-uniform hard capacity constraints (Capacitated Sum of Radii ). In particular, we give a (15+ε)-approximation algorithm that runs in 2^𝒪(k²log k) ⋅ n³ time. When capacities are uniform, we obtain the following improved approximation bounds. - A (4 + ε)-approximation with running time 2^𝒪(klog(k/ε)) n³, which significantly improves over the FPT 28-approximation of Inamdar and Varadarajan [ESA 2020]. - A (2 + ε)-approximation with running time 2^𝒪(k/ε² ⋅log(k/ε)) dn³ and a (1+ε)-approxim- ation with running time 2^𝒪(kdlog ((k/ε))) n³ in the Euclidean space. Here d is the dimension. - A (1 + ε)-approximation in the Euclidean space with running time 2^𝒪(k/ε² ⋅log(k/ε)) dn³ if we are allowed to violate the capacities by (1 + ε)-factor. We complement this result by showing that there is no (1 + ε)-approximation algorithm running in time f(k)⋅ n^𝒪(1), if any capacity violation is not allowed.
Cite as

Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.12,
  author =	{Bandyapadhyay, Sayan and Lochet, William and Saurabh, Saket},
  title =	{{FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.12},
  URN =		{urn:nbn:de:0030-drops-178628},
  doi =		{10.4230/LIPIcs.SoCG.2023.12},
  annote =	{Keywords: Clustering, FPT-approximation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.11
True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs

Authors: Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, and Jie Xue

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

Abstract
We prove a structural theorem for unit-disk graphs, which (roughly) states that given a set 𝒟 of n unit disks inducing a unit-disk graph G_𝒟 and a number p ∈ [n], one can partition 𝒟 into p subsets 𝒟₁,… ,𝒟_p such that for every i ∈ [p] and every 𝒟' ⊆ 𝒟_i, the graph obtained from G_𝒟 by contracting all edges between the vertices in 𝒟_i $1𝒟' admits a tree decomposition in which each bag consists of O(p+|𝒟'|) cliques. Our theorem can be viewed as an analog for unit-disk graphs of the structural theorems for planar graphs and almost-embeddable graphs proved very recently by Marx et al. [SODA'22] and Bandyapadhyay et al. [SODA'22]. By applying our structural theorem, we give several new combinatorial and algorithmic results for unit-disk graphs. On the combinatorial side, we obtain the first Contraction Decomposition Theorem (CDT) for unit-disk graphs, resolving an open question in the work Panolan et al. [SODA'19]. On the algorithmic side, we obtain a new FPT algorithm for bipartization (also known as odd cycle transversal) on unit-disk graphs, which runs in 2^{O(√k log k)} ⋅ n^{O(1)} time, where k denotes the solution size. Our algorithm significantly improves the previous slightly subexponential-time algorithm given by Lokshtanov et al. [SODA'22] (which works more generally for disk graphs) and is almost optimal, as the problem cannot be solved in 2^{o(√k)} ⋅ n^{O(1)} time assuming the ETH.
Cite as

Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, and Jie Xue. True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2022.11,
  author =	{Bandyapadhyay, Sayan and Lochet, William and Lokshtanov, Daniel and Saurabh, Saket and Xue, Jie},
  title =	{{True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{11:1--11:16},
  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.11},
  URN =		{urn:nbn:de:0030-drops-160190},
  doi =		{10.4230/LIPIcs.SoCG.2022.11},
  annote =	{Keywords: unit-disk graphs, tree decomposition, contraction decomposition, bipartization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.29
Detours in Directed Graphs

Authors: Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s,t)-path of length at least dist_G(s,t)+k (where dist_G(s,t) denotes the length of a shortest path from s to t). Bezáková et al. [Ivona Bezáková et al., 2019] proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2^{O(k)}⋅ n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2^{O (k)}· n^{O(1)} time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path above Diameter, the task is to decide whether the graph has a path of length at least diam(G)+k(diam(G)denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path above Diameter is NP-complete even for k=1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path above Diameter is solvable in polynomial time for each k ∈ {1,..., 4} and is NP-complete for every k ≥ 5. The parameterized complexity of Longest Detour on general directed graphs remains an interesting open problem.
Cite as

Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh. Detours in Directed Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.STACS.2022.29,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Sagunov, Danil and Simonov, Kirill and Saurabh, Saket},
  title =	{{Detours in Directed Graphs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.29},
  URN =		{urn:nbn:de:0030-drops-158390},
  doi =		{10.4230/LIPIcs.STACS.2022.29},
  annote =	{Keywords: longest path, longest detour, diameter, directed graphs, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.50
Exploiting Dense Structures in Parameterized Complexity

Authors: William Lochet, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
Over the past few decades, the study of dense structures from the perspective of approximation algorithms has become a wide area of research. However, from the viewpoint of parameterized algorithm, this area is largely unexplored. In particular, properties of random samples have been successfully deployed to design approximation schemes for a number of fundamental problems on dense structures [Arora et al. FOCS 1995, Goldreich et al. FOCS 1996, Giotis and Guruswami SODA 2006, Karpinksi and Schudy STOC 2009]. In this paper, we fill this gap, and harness the power of random samples as well as structure theory to design kernelization as well as parameterized algorithms on dense structures. In particular, we obtain linear vertex kernels for Edge-Disjoint Paths, Edge Odd Cycle Transversal, Minimum Bisection, d-Way Cut, Multiway Cut and Multicut on everywhere dense graphs. In fact, these kernels are obtained by designing a polynomial-time algorithm when the corresponding parameter is at most Ω(n). Additionally, we obtain a cubic kernel for Vertex-Disjoint Paths on everywhere dense graphs. In addition to kernelization results, we obtain randomized subexponential-time parameterized algorithms for Edge Odd Cycle Transversal, Minimum Bisection, and d-Way Cut. Finally, we show how all of our results (as well as EPASes for these problems) can be de-randomized.
Cite as

William Lochet, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Exploiting Dense Structures in Parameterized Complexity. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 50:1-50:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lochet_et_al:LIPIcs.STACS.2021.50,
  author =	{Lochet, William and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav},
  title =	{{Exploiting Dense Structures in Parameterized Complexity}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{50:1--50:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.50},
  URN =		{urn:nbn:de:0030-drops-136950},
  doi =		{10.4230/LIPIcs.STACS.2021.50},
  annote =	{Keywords: Dense graphs, disjoint paths, odd cycle transversal, kernels}
}
  • Refine by Type
  • 20 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 9 2025
  • 1 2024
  • 2 2023
  • 2 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 12 Lochet, William
  • 11 Saurabh, Saket
  • 6 Bandyapadhyay, Sayan
  • 4 Fomin, Fedor V.
  • 4 Lokshtanov, Daniel
  • Show More...

  • Refine by Series/Journal
  • 20 LIPIcs

  • Refine by Classification
  • 8 Theory of computation → Parameterized complexity and exact algorithms
  • 5 Theory of computation → Approximation algorithms analysis
  • 5 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Fixed parameter tractability
  • 3 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 3 Clustering
  • 3 parameterized complexity
  • 2 H-free editing
  • 2 Kernelization
  • 2 approximation algorithms
  • Show More...

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