Author name cluster

Rémi Watrigant

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

TCS Journal 2025 Journal Article

Channel allocation revisited through 1-extendability of graphs

Anthony Busson
Malory Marin
Rémi Watrigant

We revisit the classical problem of channel allocation for Wi-Fi access points (AP). Using mechanisms such as the CSMA/CA protocol, Wi-Fi access points which are in conflict within a same channel are still able to communicate to terminals. In graph theoretical terms, it means that it is not mandatory for the channel allocation to correspond to a proper coloring of the conflict graph. However, recent studies suggest that the structure–rather than the number–of conflicts plays a crucial role in the performance of each AP. More precisely, the graph induced by each channel must satisfy the so-called 1-extendability property, which requires each vertex to be contained in an independent set of maximum cardinality. In this paper we introduce the 1-extendable chromatic number, which is the minimum size of a partition of the vertex set of a graph such that each part induces a 1-extendable graph. We study this parameter and the related optimization problem through different perspectives: algorithms and complexity, structure, and extremal properties. We first show how to compute this number using modular decompositions of graphs, and analyze the running time with respect to the modular width of the input graph. We also focus on the special case of cographs, and prove that the 1-extendable chromatic number can be computed in quasi-polynomial time in this class. Concerning extremal results, we show that the 1-extendable chromatic number of a graph with n vertices is at most 2 n, whereas the classical chromatic number can be as large as n. We are also able to construct graphs whose 1-extendable chromatic number is at least logarithmic in the number of vertices.

Details DOI

MFCS Conference 2025 Conference Paper

Subcoloring of (Unit) Disk Graphs

Malory Marin
Rémi Watrigant

A subcoloring of a graph is a partition of its vertex set into subsets (called colors), each inducing a disjoint union of cliques. It is a natural generalization of the classical proper coloring, in which each color must instead induce an independent set. Similarly to proper coloring, we define the subchromatic number of a graph as the minimum integer k such that it admits a subcoloring with k colors, and the corresponding problem k-Subcoloring which asks whether a graph has subchromatic number at most k. In this paper, we initiate the study of the subcoloring of (unit) disk graphs. One motivation stems from the fact that disk graphs can be seen as a dense generalization of planar graphs where, intuitively, each vertex can be blown into a large clique-much like subcoloring generalizes proper coloring. Interestingly, it can be observed that every unit disk graph admits a subcoloring with at most 7 colors. We first prove that the subchromatic number can be 3-approximated in polynomial-time in unit disk graphs. We then present several hardness results for special cases of unit disk graphs which somehow prevents the use of classical approaches for improving this result. We show in particular that 2-Subcoloring remains NP-hard in triangle-free unit disk graphs, as well as in unit disk graphs representable within a strip of bounded height. We also solve an open question of Broersma, Fomin, Nešetřil, and Woeginger (2002) by proving that 3-Subcoloring remains NP-hard in co-comparability graphs (which contain unit disk graphs representable within a strip of height √3/2). Finally, we prove that every n-vertex disk graph admits a subcoloring with at most O(log³(n)) colors and present a O(log²(n))-approximation algorithm for computing the subchromatic number of such graphs. This is achieved by defining a decomposition and a special type of co-comparability disk graph, called Δ-disk graphs, which might be of independent interest.

Details

SODA Conference 2021 Conference Paper

Twin-width II: small classes

Édouard Bonnet
Colin Geniet
Eun Jung Kim 0002
Stéphan Thomassé
Rémi Watrigant

The recently introduced twin-width of a graph G is the minimum integer d such that G has a d-contraction sequence, that is, a sequence of | V ( G )| – 1 iterated vertex identifications for which the overall maximum number of red edges incident to a single vertex is at most d, where a red edge appears between two sets of identified vertices if they are not homogeneous in G (not fully adjacent nor fully non-adjacent). We show that if a graph admits a d -contraction sequence, then it also has a linear-arity tree of f ( d )-contractions, for some function f. Informally if we accept to worsen the twin-width bound, we can choose the next contraction from a set of Θ (| V ( G )|) pairwise disjoint pairs of vertices. This has two main consequences. First it permits to show that every bounded twin-width class is small, i. e. , has at most n! c n graphs labeled by [ n ], for some constant c. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al. , JCTB '06]. It implies in turn that bounded-degree graphs, interval graphs, and unit disk graphs have unbounded twin-width. The second consequence is an O (log n )-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the small conjecture that, conversely, every small hereditary class has bounded twin-width. The conjecture passes many tests. Inspired by sorting networks of logarithmic depth, we show that log Θ (log log d ) n -subdivisions of K n (a small class when d is constant) have twin-width at most d. We obtain a rather sharp converse with a surprisingly direct proof: the log d +1 n -subdivision of K n has twin-width at least d. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. These sparse classes are surprisingly rich since they contain certain (small) classes of expanders. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from K 4 [Bilu and Linial, Combinatorica '06] also have bounded twin-width. These graphs are related to so-called separable permutations and also form a small class. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width. We show that for a hereditary class of bounded twin-width the five following conditions are equivalent: every graph in (1) is K t, t -fr ee for some fixed t, (2) has an adjacency matrix without a d-by-d division with a 1 entry in each d 2 cells for some fixed d, (3) has at most linearly many edges, (4) the subgraph closure of has bounded twin-width, and (5) has bounded expansion. We discuss how sparse classes with similar behavior with respect to clique subdivisions compare to bounded sparse twin-width.

Details

FOCS Conference 2020 Conference Paper

Twin-width I: tractable FO model checking

Édouard Bonnet
Eun Jung Kim 0002
Stéphan Thomassé
Rémi Watrigant

Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, Kt - free unit d-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of d-contractions, witness that the twin-width is at most d. We show that FO model checking, that is deciding if a given first-order formula φ evaluates to true for a given binary structure G on a domain D, is FPT in |φ| on classes of bounded twin-width, provided the witness is given. More precisely, being given a d-contraction sequence for G, our algorithm runs in time f(d, |φ|)·|D| where f is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS '15].

Details

TCS Journal 2019 Journal Article

Parameterized resiliency problems

Jason Crampton
Gregory Gutin
Martin Koutecký
Rémi Watrigant

We introduce an extension of decision problems called resiliency problems. In a resiliency problem, the goal is to decide whether an instance remains positive after any (appropriately defined) perturbation has been applied to it. To tackle these kinds of problems, some of which might be of practical interest, we introduce a notion of resiliency for Integer Linear Programs (ILP) and show how to use a result of Eisenbrand and Shmonin (Math. Oper. Res. , 2008) on Parametric Linear Programming to prove that ILP Resiliency is fixed-parameter tractable (FPT) under a certain parameterization. To demonstrate the utility of our result, we consider natural resiliency variants of several concrete problems, and prove that they are FPT under natural parameterizations. Our first results concern a four-variate problem which generalizes the Disjoint Set Cover problem and which is of interest in access control. We obtain a complete parameterized complexity classification for every possible combination of the parameters. Then, we introduce and study a resiliency variant of the Closest String problem, for which we extend an FPT result of Gramm et al. (Algorithmica, 2003). We also consider problems in the fields of scheduling and social choice. We believe that many other problems can be tackled by our framework.

Details DOI

TCS Journal 2014 Journal Article

On the sum-max graph partitioning problem

Rémi Watrigant
Marin Bougeret
Rodolphe Giroudeau
Jean-Claude König

This paper tackles the following problem: given a connected graph G = ( V, E ) with a weight function on its edges and an integer k ⩽ | V |, find a partition of V into k clusters such that the sum (over all pairs of clusters) of the heaviest edges between the clusters is minimized. We first prove that this problem (and even the unweighted variant) cannot be approximated within a factor of O ( n 1 − ϵ ) unless P = NP, and cannot admit an FPT algorithm unless FPT = W [ 1 ]. Next, we develop several algorithms: we first present a greedy algorithm and prove that it achieves a tight approximation ratio smaller than k 2. Concerning the unweighted version of the problem, we study how the diameter of the input graph can influence its complexity, by obtaining negative results for graphs of low diameter, positive results for graphs of high diameter, and a polynomial-time approximation algorithm with an approximation ratio smaller than k 2 and depending on the diameter. We also highlight a link between the k -sparsest subgraph problem and the unweighted version. This allows us to develop several constant ratio approximation algorithms running in exponential time for general graphs, and in polynomial time in some restricted graph classes. Finally, we discuss the exact resolution for fixed k and the connections to a graph homomorphism problem.

Details DOI