wovepaper — the arXiv observatory

papers

Publications (23)

cs.DS2022

Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs

Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +2

We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on $H$ -minor free graphs. In particular, we obtain the following resul…

cs.DM2025

On a tree-based variant of bandwidth and forbidding simple topological minors

Hugo Jacob, William Lochet, Christophe Paul

We obtain structure theorems for graphs excluding a fan (a path with a universal vertex) or a dipole ( $K_{2, k}$ ) as a topological minor. The corresponding decompositions can be com…

math.CO2016

Subdivisions of oriented cycles in digraphs with large chromatic number

Nathann Cohen, FrÃ©dÃ©ric Havet, William Lochet +1

An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle $C$ , there are digraphs containing no subdivision of $C$ (as a subdigraph) and…

cs.DS2024

Packing Short Cycles

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +6

Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of v…

cs.DS2024

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii

Sayan Bandyapadhyay, William Lochet, Saket Saurabh

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 approx…

cs.DS2022

Detours in Directed Graphs

Fedor V. Fomin, Petr A. Golovach, William Lochet +3

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 Pa…

math.CO2016

The structure of typical eye-free graphs and a Turan-type result for two weighted colours

Peter Keevash, William Lochet

The $(a, b)$ -eye is the graph $I_{a, b} = K_{a + b} - K_{b}$ obtained by deleting the edges of a clique of size $b$ from a clique of size $a + b$ . We show that for any $a, b \geq 2$ and $p \in…

cs.CG2023

Minimum-Membership Geometric Set Cover, Revisited

Sayan Bandyapadhyay, William Lochet, Saket Saurabh +1

We revisit a natural variant of geometric set cover, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set $S$ of points and a set $\m…

math.CO2020

A Polynomial Time Algorithm for the $k$ -Disjoint Shortest Paths Problem

William Lochet

The disjoint paths problem is a fundamental problem in algorithmic graph theory and combinatorial optimization. For a given graph $G$ and a set of $k$ pairs of terminals in $G$ , it…

math.CO2020

Progress on the adjacent vertex distinguishing edge colouring conjecture

GwenaÃ«l Joret, William Lochet

A proper edge colouring of a graph is adjacent vertex distinguishing if no two adjacent vertices see the same set of colours. Using a clever application of the Local Lemma, Hatami…

math.CO2016

Equitable orientations of sparse uniform hypergraphs

Nathann Cohen, William Lochet

Caro, West, and Yuster studied how $r$ -uniform hypergraphs can be oriented in such a way that (generalizations of) indegree and outdegree are as close to each other as can be hoped…

math.CO2024

Blow-ups and extensions of trees in tournaments

Pierre Aboulker, FrÃ©dÃ©ric Havet, William Lochet +3

A class of acyclic digraphs $C$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D \in C$ is contained in all tournaments of order…

cs.DS2020

A Polynomial Kernel for Line Graph Deletion

Eduard Eiben, William Lochet

The line graph of a graph $G$ is the graph $L (G)$ whose vertex set is the edge set of $G$ and there is an edge between $e, f \in E (G)$ if $e$ and $f$ share an endpoint in $G$ . A grap…

math.CO2020

Packing and covering balls in graphs excluding a minor

Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet +4

We prove that for every integer $t \geq 1$ there exists a constant $c_{t}$ such that for every $K_{t}$ -minor-free graph $G$ , and every set $S$ of balls in $G$ , the minimum size of a set…

math.CO2021

Powers of paths in tournaments

Nemanja DraganiÄ, FranÃ§ois Dross, Jacob Fox +7

In this short note we prove that every tournament contains the $k$ -th power of a directed path of linear length. This improves upon recent results of Yuster and of GirÃ£o. We also…

cs.CC2019

The directed 2-linkage problem with length constraints

JÃ¸rgen Bang-Jensen, Thomas Bellitto, William Lochet +1

The {\sc weak 2-linkage} problem for digraphs asks for a given digraph and vertices $s_{1}, s_{2}, t_{1}, t_{2}$ whether $D$ contains a pair of arc-disjoint paths $P_{1}, P_{2}$ such that $P_{i}$ is…

cs.CG2023

Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable

Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +2

In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of $n$ points in $R^{2}$ called terminals and a parameter $k$ , and the goal is to compute a Ste…

cs.DS2024

Robust Contraction Decomposition for Minor-Free Graphs and its Applications

Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +6

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 polynomi…

math.CO2022

Edge separators for graphs excluding a minor

GwenaÃ«l Joret, William Lochet, MichaÅ T. Seweryn

We prove that every $n$ -vertex $K_{t}$ -minor-free graph $G$ of maximum degree $I^$ has a set $F$ of $O (t^{2} (lo g t)^{1/4} I^ n)$ edges such that every component of $G - F$ has at…

math.CO2019

A Polynomial Kernel for Paw-Free Editing

Eduard Eiben, William Lochet, Saket Saurabh

For a fixed graph $H$ , the $H$ -free-editing problem asks whether we can modify a given graph $G$ by adding or deleting at most $k$ edges such that the resulting graph does not cont…

cs.DS2020

EPTAS for $k$ -means Clustering of Affine Subspaces

Eduard Eiben, Fedor V. Fomin, Petr A. Golovach +3

We consider a generalization of the fundamental $k$ -means clustering for data with incomplete or corrupted entries. When data objects are represented by points in $R^{d}$ , a…

cs.DS2021

How to Find a Good Explanation for Clustering?

Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach +3

$k$ -means and $k$ -median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpr…

math.CO2016

Subdivisions in digraphs of large out-degree or large dichromatic number

In 1985, Mader conjectured the existence of a function $f$ such that every digraph with minimum out-degree at least $f (k)$ contains a subdivision of the transitive tournament of or…

Publications (23)

Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs

On a tree-based variant of bandwidth and forbidding simple topological minors

Subdivisions of oriented cycles in digraphs with large chromatic number

Packing Short Cycles

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii

Detours in Directed Graphs

The structure of typical eye-free graphs and a Turan-type result for two weighted colours

Minimum-Membership Geometric Set Cover, Revisited

A Polynomial Time Algorithm for the k-Disjoint Shortest Paths Problem

Progress on the adjacent vertex distinguishing edge colouring conjecture

Equitable orientations of sparse uniform hypergraphs

Blow-ups and extensions of trees in tournaments

A Polynomial Kernel for Line Graph Deletion

Packing and covering balls in graphs excluding a minor

Powers of paths in tournaments

The directed 2-linkage problem with length constraints

Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable

Robust Contraction Decomposition for Minor-Free Graphs and its Applications

Edge separators for graphs excluding a minor

A Polynomial Kernel for Paw-Free Editing

EPTAS for k-means Clustering of Affine Subspaces

How to Find a Good Explanation for Clustering?

Subdivisions in digraphs of large out-degree or large dichromatic number

A Polynomial Time Algorithm for the $k$ -Disjoint Shortest Paths Problem

EPTAS for $k$ -means Clustering of Affine Subspaces