Source author record

Stéphan Thomassé

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms Computational Complexity Logic in Computer Science Information Theory math.GR math.IT math.RA quant-ph

Catalog footprint

Research overview

35works

10topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$

Dallard, Milanič, and Štorgel [arXiv '22] ask if for every class excluding a fixed planar graph $H$ as an induced minor, Maximum Independent Set can be solved in polynomial time, and show that this is indeed the case when $H$ is any planar complete bipartite graph, or the 5-vertex clique minus one edge, or minus two disjoint edges. A positive answer would constitute a far-reaching generalization of the state-of-the-art, when we currently do not know if a polynomial-time algorithm exists when $H$ is the 7-vertex path. Relaxing tractability to the existence of a quasipolynomial-time algorithm, we know substantially more. Indeed, quasipolynomial-time algorithms were recently obtained for the $t$ -vertex cycle, $C_t$ [Gartland et al., STOC '21] and the disjoint union of $t$ triangles, $tC_3$ [Bonamy et al., SODA '23]. We give, for every integer $t$ , a polynomial-time algorithm running in $n^{O(t^5)}$ when $H$ is the friendship graph $K_1 + tK_2$ ( $t$ disjoint edges plus a vertex fully adjacent to them), and a quasipolynomial-time algorithm running in $n^{O(t^2 \log n)+f(t)}$ , with $f$ a single-exponential function, when $H$ is $tC_3 \uplus C_4$ (the disjoint union of $t$ triangles and a 4-vertex cycle). The former extends a classical result on graphs excluding $tK_2$ as an induced subgraph [Alekseev, DAM '07], while the latter extends Bonamy et al.'s result.

preprint2023arXiv

(P6, triangle)-free digraphs have bounded dichromatic number

The dichromatic number of an oriented graph is the minimum size of a partition of its vertices into acyclic induced subdigraphs. We prove that oriented graphs with no induced directed path on six vertices and no triangle have bounded dichromatic number. This is one (small) step towards the general conjecture asserting that for every oriented tree T and every integer k, any oriented graph that does not contain an induced copy of T nor a clique of size k has dichromatic number at most some function of k and T.

preprint2023arXiv

Extremal Independent Set Reconfiguration

The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the intermediate sets remain independent. Extremal problems on independent sets are widely studied: for example, it is well known that an $n$ -vertex graph has at most $3^{n/3}$ maximum independent sets (and this is tight). This paper investigates the asymptotic behavior of maximum possible length of a shortest reconfiguration sequence for independent sets of size $k$ among all $n$ -vertex graphs. We give a tight bound for $k=2$ . We also provide a subquadratic upper bound (using the hypergraph removal lemma) as well as an almost tight construction for $k=3$ . We generalize our results for larger values of $k$ by proving an $n^{2\lfloor k/3 \rfloor}$ lower bound.

preprint2022arXiv

A quasi-quadratic vertex Kernel for Cograph edge editing

We provide a $O(k^2 \mathrm{log} k)$ vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez [1] which involved four reduction rules. We generalize one of their rules, based on packing of induced paths of length four, by introducing t-modules, which are modules up to t edge modifications. The key fact is that large t-modules cannot be edited more than t times, and this allows to obtain a near quadratic kernel. The extra $\mathrm{log} k$ factor seems tricky to remove as it is necessary in the combinatorial lemma on trees which is central in our proof. Nevertheless, we think that a quadratic bound should be reachable.

preprint2022arXiv

Twin-width VI: the lens of contraction sequences

A contraction sequence of a graph consists of iteratively merging two of its vertices until only one vertex remains. The recently introduced twin-width graph invariant is based on contraction sequences. More precisely, if one puts red edges between two vertices representing non-homogeneous subsets, the twin-width is the minimum integer $d$ such that a contraction sequence keeps red degree at most $d$ . By changing the condition imposed on the trigraphs (i.e., graphs with some edges being red) and possibly slightly tweaking the notion of contractions, we show how to characterize the well-established bounded rank-width, tree-width, linear rank-width, path-width, and proper minor-closed classes by means of contraction sequences. As an application we give a transparent alternative proof of the celebrated Courcelle's theorem (actually of its generalization by Courcelle, Makowsky, and Rotics), that MSO $_2$ (resp. MSO $_1$ ) model checking on graphs with bounded tree-width (resp. bounded rank-width) is fixed-parameter tractable in the size of the input sentence. We then explore new avenues along the general theme of contraction sequences both in order to refine the landscape between bounded tree-width and bounded twin-width (via spanning twin-width) and to capture more general classes than bounded twin-width. To this end, we define an oriented version of twin-width, where appearing red edges are oriented away from the newly contracted vertex, and the mere red out-degree should remain bounded. Surprisingly, classes of bounded oriented twin-width coincide with those of bounded twin-width. Finally we examine, from an algorithmic standpoint, the concept of partial contraction sequences, where, instead of terminating on a single-vertex graph, the sequence ends when reaching a particular target class.

preprint2022arXiv

Twin-width VII: groups

Twin-width is a recently introduced graph parameter with applications in algorithmics, combinatorics, and finite model theory. For graphs of bounded degree, finiteness of twin-width is preserved by quasi-isometry. Thus, through Cayley graphs, it defines a group invariant. We prove that groups which are abelian, hyperbolic, ordered, solvable, or with polynomial growth, have finite twin-width. Twin-width can be characterised by excluding patterns in the self-action by product of the group elements. Based on this characterisation, we propose a strengthening called uniform twin-width, which is stable under constructions such as group extensions, direct products, and direct limits. The existence of finitely generated groups with infinite twin-width is not immediate. We construct one using a result of Osajda on embeddings of graphs into groups. This implies the existence of a class of finite graphs with unbounded twin-width but containing $2^{O(n)} \cdot n!$ graphs on vertex set $\{1,\dots,n\}$ , settling a question asked in a previous work.

preprint2022arXiv

Twin-width VIII: delineation and win-wins

We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$ , it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadically dependent. An effective strengthening of delineation for a class $\mathcal C$ implies that tractable FO model checking on $\mathcal C$ is perfectly understood: On hereditary closures $\mathcal D$ of subclasses of $\mathcal C$ , FO model checking is fixed-parameter tractable (FPT) exactly when $\mathcal D$ has bounded twin-width. Ordered graphs [BGOdMSTT, STOC '22] and permutation graphs [BKTW, JACM '22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we show that segment graphs, directed path graphs, and visibility graphs of simple polygons are not delineated. In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA '21]. We show that $K_{t,t}$ -free segment graphs, and axis-parallel $H_t$ -free unit segment graphs have bounded twin-width, where $H_t$ is the half-graph or ladder of height $t$ . In contrast, axis-parallel $H_4$ -free two-lengthed segment graphs have unbounded twin-width. Our new results, combined with the known FPT algorithm for FO model checking on graphs given with $O(1)$ -sequences, lead to win-win arguments. For instance, we derive FPT algorithms for $k$ -Ladder on visibility graphs of 1.5D terrains, and $k$ -Independent Set on visibility graphs of simple polygons.

preprint2021arXiv

Twin-width III: Max Independent Set, Min Dominating Set, and Coloring

We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$ -vertex graphs given with a witness that the twin-width is at most $d$ , called $d$ -contraction sequence or $d$ -sequence, and formulas of size $k$ [Bonnet et al., FOCS '20]. The inevitable price to pay for such a general result is that $f$ is a tower of exponentials of height roughly $k$ . In this paper, we show that algorithms based on twin-width need not be impractical. We present $2^{O(k)}n$ -time algorithms for $k$ -Independent Set, $r$ -Scattered Set, $k$ -Clique, and $k$ -Dominating Set when an $O(1)$ -sequence is provided. We further show how to solve weighted $k$ -Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time $2^{O(k \log k)}n$ . These algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example, we establish that bounded twin-width classes are $χ$ -bounded. This significantly extends the $χ$ -boundedness of bounded rank-width classes, and does so with a very concise proof. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time $O(n \log n)$ and time $O(n^2 \log n)$ , respectively. Finally we show that Min Dominating Set and related problems have constant integrality gaps on bounded twin-width classes, thereby getting constant approximations on these classes.

preprint2020arXiv

An algorithmic weakening of the Erdős-Hajnal conjecture

We study the approximability of the Maximum Independent Set (MIS) problem in $H$ -free graphs (that is, graphs which do not admit $H$ as an induced subgraph). As one motivation we investigate the following conjecture: for every fixed graph $H$ , there exists a constant $δ> 0$ such that MIS can be $n^{1 - δ}$ -approximated in $H$ -free graphs, where $n$ denotes the number of vertices of the input graph. We first prove that a constructive version of the celebrated Erdős-Hajnal conjecture implies ours. We then prove that the set of graphs $H$ satisfying our conjecture is closed under the so-called graph substitution. This, together with the known polynomial-time algorithms for MIS in $H$ -free graphs (e.g. $P_6$ -free and fork-free graphs), implies that our conjecture holds for many graphs $H$ for which the Erdős-Hajnal conjecture is still open. We then focus on improving the constant $δ$ for some graph classes: we prove that the classical Local Search algorithm provides an $OPT^{1-\frac{1}{t}}$ -approximation in $K_{t,t}$ -free graphs (hence a $\sqrt{OPT}$ -approximation in $C_4$ -free graphs), and, while there is a simple $\sqrt{n}$ -approximation in triangle-free graphs, it cannot be improved to $n^{\frac{1}{4}-\varepsilon}$ for any $\varepsilon > 0$ unless $NP \subseteq BPP$ . More generally, we show that there is a constant $c$ such that MIS in graphs of girth $γ$ cannot be $n^{\frac{c}γ}$ -approximated. Up to a constant factor in the exponent, this matches the ratio of a known approximation algorithm by Monien and Speckenmeyer, and by Murphy. To the best of our knowledge, this is the first strong (i.e., $Ω(n^δ)$ for some $δ> 0$ ) inapproximability result for Maximum Independent Set in a proper hereditary class.

preprint2020arXiv

Disproving the normal graph conjecture

A graph $G$ is called normal if there exist two coverings, $\mathbb{C}$ and $\mathbb{S}$ of its vertex set such that every member of $\mathbb{C}$ induces a clique in $G$ , every member of $\mathbb{S}$ induces an independent set in $G$ and $C \cap S \neq \emptyset$ for every $C \in \mathbb{C}$ and $S \in \mathbb{S}$ . It has been conjectured by De Simone and Körner in 1999 that a graph $G$ is normal if $G$ does not contain $C_5$ , $C_7$ and $\overline{C_7}$ as an induced subgraph. We disprove this conjecture.

preprint2020arXiv

On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five

A hole in a graph is an induced cycle of length at least $4$ , and an antihole is the complement of an induced cycle of length at least $4$ . A hole or antihole is long if its length is at least $5$ . For an integer $k$ , the $k$ -prism is the graph consisting of two cliques of size $k$ joined by a matching. The complexity of Maximum (Weight) Independent Set (MWIS) in long-hole-free graphs remains an important open problem. In this paper we give a polynomial time algorithm to solve MWIS in long-hole-free graphs with no $k$ -prism (for any fixed integer $k$ ), and a subexponential algorithm for MWIS in long-hole-free graphs in general. As a special case this gives a polynomial time algorithm to find a maximum weight clique in perfect graphs with no long antihole, and no hole of length $6$ . The algorithms use the framework of minimal chordal completions and potential maximal cliques.

preprint2020arXiv

Twin-width II: small classes

The 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$ . 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$ . First this 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]. 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. 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. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from $K_4$ ~[Bilu and Linial, Combinatorica '06] have bounded twin-width, too. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width and discuss how it compares with other sparse classes.

preprint2016arXiv

A Proof of the Barát-Thomassen Conjecture

The Barát-Thomassen conjecture asserts that for every tree $T$ on $m$ edges, there exists a constant $k_T$ such that every $k_T$ -edge-connected graph with size divisible by $m$ can be edge-decomposed into copies of $T$ . So far this conjecture has only been verified when $T$ is a path or when $T$ has diameter at most 4. Here we prove the full statement of the conjecture.

preprint2016arXiv

Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture

The Barát-Thomassen conjecture asserts that there is a function $f$ such that for every fixed tree $T$ with $t$ edges, every graph which is $f(t)$ -edge-connected with its number of edges divisible by $t$ has a partition of its edges into copies of $T$ . This has been proved in the case of paths of length $2^k$ by Thomassen, and recently shown to be true for all paths by Botler, Mota, Oshiro and Wakabayashi. Our goal in this paper is to propose an alternative proof of the path case with a weaker hypothesis: Namely, we prove that there is a function $f$ such that every $24$ -edge-connected graph with minimum degree $f(t)$ has an edge-partition into paths of length $t$ whenever $t$ divides the number of edges. We also show that $24$ can be dropped to $4$ when the graph is eulerian.

preprint2014arXiv

A note on the minimum distance of quantum LDPC codes

We provide a new lower bound on the minimum distance of a family of quantum LDPC codes based on Cayley graphs proposed by MacKay, Mitchison and Shokrollahi. Our bound is exponential, improving on the quadratic bound of Couvreur, Delfosse and Zémor. This result is obtained by examining a family of subsets of the hypercube which locally satisfy some parity conditions.

preprint2014arXiv

A tau-conjecture for Newton polygons

One can associate to any bivariate polynomial P(X,Y) its Newton polygon. This is the convex hull of the points (i,j) such that the monomial X^i Y^j appears in P with a nonzero coefficient. We conjecture that when P is expressed as a sum of products of sparse polynomials, the number of edges of its Newton polygon is polynomially bounded in the size of such an expression. We show that this "tau-conjecture for Newton polygons," even in a weak form, implies that the permanent polynomial is not computable by polynomial size arithmetic circuits. We make the same observation for a weak version of an earlier "real tau-conjecture." Finally, we make some progress toward the tau-conjecture for Newton polygons using recent results from combinatorial geometry.

preprint2014arXiv

Clique versus Independent Set

Yannakakis' Clique versus Independent Set problem (CL-IS) in communication complexity asks for the minimum number of cuts separating cliques from stable sets in a graph, called CS-separator. Yannakakis provides a quasi-polynomial CS-separator, i.e. of size $O(n^{\log n})$ , and addresses the problem of finding a polynomial CS-separator. This question is still open even for perfect graphs. We show that a polynomial CS-separator almost surely exists for random graphs. Besides, if H is a split graph (i.e. has a vertex-partition into a clique and a stable set) then there exists a constant $c_H$ for which we find a $O(n^{c_H})$ CS-separator on the class of H-free graphs. This generalizes a result of Yannakakis on comparability graphs. We also provide a $O(n^{c_k})$ CS-separator on the class of graphs without induced path of length k and its complement. Observe that on one side, $c_H$ is of order $O(|H| \log |H|)$ resulting from Vapnik-Chervonenkis dimension, and on the other side, $c_k$ is exponential. One of the main reason why Yannakakis' CL-IS problem is fascinating is that it admits equivalent formulations. Our main result in this respect is to show that a polynomial CS-separator is equivalent to the polynomial Alon-Saks-Seymour Conjecture, asserting that if a graph has an edge-partition into k complete bipartite graphs, then its chromatic number is polynomially bounded in terms of k. We also show that the classical approach to the stubborn problem (arising in CSP) which consists in covering the set of all solutions by $O(n^{\log n})$ instances of 2-SAT is again equivalent to the existence of a polynomial CS-separator.

preprint2014arXiv

Conflict Packing: an unifying technique to obtain polynomial kernels for editing problems on dense instances

We develop a technique that we call Conflict Packing in the context of kernelization, obtaining (and improving) several polynomial kernels for editing problems on dense instances. We apply this technique on several well-studied problems: Feedback Arc Set in (Bipartite) Tournaments, Dense Rooted Triplet Inconsistency and Betweenness in Tournaments. For the former, one is given a (bipartite) tournament $T = (V,A)$ and seeks a set of at most $k$ arcs whose reversal in $T$ results in an acyclic (bipartite) tournament. While a linear vertex-kernel is already known for the first problem, using the Conflict Packing allows us to find a so-called safe partition, the central tool of the kernelization algorithm in, with simpler arguments. For the case of bipartite tournaments, the same technique allows us to obtain a quadratic vertex-kernel. Again, such a kernel was already known to exist, using the concept of so-called bimodules. We believe however that providing an unifying technique to cope with such problems is interesting. Regarding Dense Rooted Triplet Inconsistency, one is given a set of vertices $V$ and a dense collection $\mathcal{R}$ of rooted binary trees over three vertices of $V$ and seeks a rooted tree over $V$ containing all but at most $k$ triplets from $\mathcal{R}$ . As a main consequence of our technique, we prove that the Dense Rooted Triplet Inconsistency problem admits a linear vertex-kernel. This result improves the best known bound of $O(k^2)$ vertices for this problem. Finally, we use this technique to obtain a linear vertex-kernel for Betweenness in Tournaments, where one is given a set of vertices $V$ and a dense collection $\mathcal{R}$ of so-called betweenness triplets and seeks a linear ordering of the vertices containing all but at most $k$ triplets from $\mathcal{R}$ .

preprint2014arXiv

Graphs with large chromatic number induce $3k$ -cycles

Answering a question of Kalai and Meshulam, we prove that graphs without induced cycles of length $3k$ have bounded chromatic number. This implies the very first case of a much broader question asserting that every graph with large chromatic number induces a graph $H$ such that the sum of the Betti numbers of the independence complex of $H$ is also large.

preprint2014arXiv

Isolating highly connected induced subgraphs

We prove that any graph $G$ of minimum degree greater than $2k^2-1$ has a $(k+1)$ -connected induced subgraph $H$ such that the number of vertices of $H$ that have neighbors outside of $H$ is at most $2k^2-1$ . This generalizes a classical result of Mader, which states that a high minimum degree implies the existence of a highly connected subgraph. We give several variants of our result, and for each of these variants, we give asymptotics for the bounds. We also we compute optimal values for the case when $k=2$ . Alon, Kleitman, Saks, Seymour, and Thomassen proved that in a graph of high chromatic number, there exists an induced subgraph of high connectivity and high chromatic number. We give a new proof of this theorem with a better bound.

preprint2014arXiv

Parameterized algorithm for weighted independent set problem in bull-free graphs

The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph has a stable set of size $k$ , when $k$ is part of the instance. Our main result in this paper is to show the existence of an FPT algorithm when we parameterize the problem by the solution size $k$ . A polynomial kernel is unlikely to exist for this problem. We show however that our problem has a polynomial size Turing-kernel. More precisely, the hard cases are instances of size $O(k^5)$ . As a byproduct, if we forbid odd holes in addition to the bull, we show the existence of a polynomial time algorithm for the stable set problem. We also prove that the chromatic number of a bull-free graph is bounded by a function of its clique number and the maximum chromatic number of its triangle-free induced subgraphs. All our results rely on a decomposition theorem of bull-free graphs due to Chudnovsky which is modified here, allowing us to provide extreme decompositions, adapted to our computational purpose.

preprint2014arXiv

The Erdős-Hajnal Conjecture for Long Holes and Anti-holes

Erdős and Hajnal conjectured that, for every graph $H$ , there exists a constant $c_H$ such that every graph $G$ on $n$ vertices which does not contain any induced copy of $H$ has a clique or a stable set of size $n^{c_H}$ . We prove that for every $k$ , there exists $c_k>0$ such that every graph $G$ on $n$ vertices not inducing a cycle of length at least $k$ nor its complement contains a clique or a stable set of size $n^{c_k}$ .

preprint2014arXiv

The Erdős-Hajnal Conjecture for Paths and Antipaths

We prove that for every k, there exists $c_k>0$ such that every graph G on n vertices not inducing a path $P_k$ and its complement contains a clique or a stable set of size $n^{c_k}$ .

preprint2014arXiv

VC-dimension and Erdős-Pósa property

Let $G=(V,E)$ be a graph. A $k$ -neighborhood in $G$ is a set of vertices consisting of all the vertices at distance at most $k$ from some vertex of $G$ . The hypergraph on vertex set $V$ which edge set consists of all the $k$ -neighborhoods of $G$ for all $k$ is the neighborhood hypergraph of $G$ . Our goal in this paper is to investigate the complexity of a graph in terms of its neighborhoods. Precisely, we define the distance VC-dimension of a graph $G$ as the maximum taken over all induced subgraphs $G'$ of $G$ of the VC-dimension of the neighborhood hypergraph of $G'$ . For a class of graphs, having bounded distance VC-dimension both generalizes minor closed classes and graphs with bounded clique-width. Our motivation is a result of Chepoi, Estellon and Vaxès asserting that every planar graph of diameter $2\ell$ can be covered by a bounded number of balls of radius $\ell$ . In fact, they obtained the existence of a function $f$ such that every set $\cal F$ of balls of radius $\ell$ in a planar graph admits a hitting set of size $f(ν)$ where $ν$ is the maximum number of pairwise disjoint elements of $\cal F$ . Our goal is to generalize the proof of Chepoi, Estellon and Vaxès with the unique assumption of bounded distance VC-dimension of neighborhoods. In other words, the set of balls of fixed radius in a graph with bounded distance VC-dimension has the Erdős-Pósa property.

preprint2013arXiv

Complements of nearly perfect graphs

A class of graphs closed under taking induced subgraphs is $χ$ -bounded if there exists a function $f$ such that for all graphs $G$ in the class, $χ(G) \leq f(ω(G))$ . We consider the following question initially studied in [A. Gy{á}rf{á}s, Problems from the world surrounding perfect graphs, {\em Zastowania Matematyki Applicationes Mathematicae}, 19:413--441, 1987]. For a $χ$ -bounded class $\cal C$ , is the class $\bar{C}$ $χ$ -bounded (where $\bar{\cal C}$ is the class of graphs formed by the complements of graphs from $\cal C$ )? We show that if $\cal C$ is $χ$ -bounded by the constant function $f(x)=3$ , then $\bar{\cal C}$ is $χ$ -bounded by $g(x)=\lfloor\frac{8}{5}x\rfloor$ and this is best possible. We show that for every constant $c>0$ , if $\cal C$ is $χ$ -bounded by a function $f$ such that $f(x)=x$ for $x \geq c$ , then $\bar{\cal C}$ is $χ$ -bounded. For every $j$ , we construct a class of graphs $χ$ -bounded by $f(x)=x+x/\log^j(x)$ whose complement is not $χ$ -bounded.

preprint2013arXiv

Hitting and Harvesting Pumpkins

The "c-pumpkin" is the graph with two vertices linked by c>0 parallel edges. A c-pumpkin-model in a graph G is a pair A,B of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on covering and packing c-pumpkin-models in a given graph: On the one hand, we provide an FPT algorithm running in time 2^O(k) n^O(1) deciding, for any fixed c>0, whether all c-pumpkin-models can be covered by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex Set, which correspond to the cases c=1,2 respectively. On the other hand, we present a O(log n)-approximation algorithm for both the problems of covering all c-pumpkin-models with a smallest number of vertices, and packing a maximum number of vertex-disjoint c-pumpkin-models.

preprint2013arXiv

Symmetric Determinantal Representations in Characteristic 2

This paper studies Symmetric Determinantal Representations (SDR) in characteristic 2, that is the representation of a multivariate polynomial P by a symmetric matrix M such that P=det(M), and where each entry of M is either a constant or a variable. We first give some sufficient conditions for a polynomial to have an SDR. We then give a non-trivial necessary condition, which implies that some polynomials have no SDR, answering a question of Grenet et al. A large part of the paper is then devoted to the case of multilinear polynomials. We prove that the existence of an SDR for a multilinear polynomial is equivalent to the existence of a factorization of the polynomial in certain quotient rings. We develop some algorithms to test the factorizability in these rings and use them to find SDRs when they exist. Altogether, this gives us polynomial-time algorithms to factorize the polynomials in the quotient rings and to build SDRs. We conclude by describing the case of Alternating Determinantal Representations in any characteristic.

preprint2012arXiv

A Linear Vertex Kernel for Maximum Internal Spanning Tree

We present a polynomial time algorithm that for any graph G and integer k >= 0, either finds a spanning tree with at least k internal vertices, or outputs a new graph G' on at most 3k vertices and an integer k' such that G has a spanning tree with at least k internal vertices if and only if G' has a spanning tree with at least k' internal vertices. In other words, we show that the Maximum Internal Spanning Tree problem parameterized by the number of internal vertices k, has a 3k-vertex kernel. Our result is based on an innovative application of a classical min-max result about hypertrees in hypergraphs which states that "a hypergraph H contains a hypertree if and only if H is partition connected."

preprint2012arXiv

Parameterized Domination in Circle Graphs

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: - Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. - Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. - If T is a given tree, deciding whether a circle graph has a dominating set isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by |V(T)|. We prove that the FPT algorithm is subexponential.

preprint2011arXiv

Cyclic Orderings and Cyclic Arboricity of Matroids

We prove a general result concerning cyclic orderings of the elements of a matroid. For each matroid $M$ , weight function $ω:E(M)\rightarrow\mathbb{N}$ , and positive integer $D$ , the following are equivalent. (1) For all $A\subseteq E(M)$ , we have $\sum_{a\in A}ω(a)\le D\cdot r(A)$ . (2) There is a map $ϕ$ that assigns to each element $e$ of $E(M)$ a set $ϕ(e)$ of $ω(e)$ cyclically consecutive elements in the cycle $(1,2,...,D)$ so that each set $\{e|i\inϕ(e)\}$ , for $i=1,...,D$ , is independent. As a first corollary we obtain the following. For each matroid $M$ so that $|E(M)|$ and $r(M)$ are coprime, the following are equivalent. (1) For all non-empty $A\subseteq E(M)$ , we have $|A|/r(A)\le|E(M)|/r(M)$ . (2) There is a cyclic permutation of $E(M)$ in which all sets of $r(M)$ cyclically consecutive elements are bases of $M$ . A second corollary is that the circular arboricity of a matroid is equal to its fractional arboricity. These results generalise classical results of Edmonds, Nash-Williams and Tutte on covering and packing matroids by bases and graphs by spanning trees.

preprint2011arXiv

Scott's induced subdivision conjecture for maximal triangle-free graphs

Scott conjectured that the class of graphs with no induced subdivision of a given graph is $χ$ -bounded. We verify his conjecture for maximal triangle-free graphs.

preprint2011arXiv

The Domination Number of Grids

In this paper, we conclude the calculation of the domination number of all $n\times m$ grid graphs. Indeed, we prove Chang's conjecture saying that for every $16\le n\le m$ , $γ(G_{n,m})=\lfloor\frac{(n+2)(m+2)}{5}\rfloor -4$ .

preprint2010arXiv

Coloring dense graphs via VC-dimension

The Vapnik-Červonenkis dimension is a complexity measure of set-systems, or hypergraphs. Its application to graphs is usually done by considering the sets of neighborhoods of the vertices (cf. Alon et al. (2006) and Chepoi, Estellon, and Vaxes (2007)), hence providing a set-system. But the graph structure is lost in the process. The aim of this paper is to introduce the notion of paired VC-dimension, a generalization of VC-dimension to set-systems endowed with a graph structure, hence a collection of pairs of subsets. The classical VC-theory is generally used in combinatorics to bound the transversality of a hypergraph in terms of its fractional transversality and its VC-dimension. Similarly, we bound the chromatic number in terms of fractional transversality and paired VC-dimension. This approach turns out to be very useful for a class of problems raised by Erdős and Simonovits (1973) asking for H-free graphs with minimum degree at least cn and arbitrarily high chromatic number, where H is a fixed graph and c a positive constant. We show how the usual VC-dimension gives a short proof of the fact that triangle-free graphs with minimum degree at least n/3 have bounded chromatic number, where $n$ is the number of vertices. Using paired VC-dimension, we prove that if the chromatic number of $H$ -free graphs with minimum degree at least cn is unbounded for some positive c, then it is unbounded for all c<1/3. In other words, one can find H-free graphs with unbounded chromatic number and minimum degree arbitrarily close to n/3. These H-free graphs are derived from a construction of Hajnal. The large chromatic number follows from the Borsuk-Ulam Theorem.

preprint2010arXiv

Edge Growth in Graph Cubes

We show that for every connected graph $G$ of diameter $\ge 3$ , the graph $G^3$ has average degree $\ge 7/4 δ(G)$ . We also provide an example showing that this bound is best possible. This resolves a question of Hegarty \cite{PH}.

preprint2010arXiv

Multicut is FPT

Let $G=(V,E)$ be a graph on $n$ vertices and $R$ be a set of pairs of vertices in $V$ called \emph{requests}. A \emph{multicut} is a subset $F$ of $E$ such that every request $xy$ of $R$ is cut by $F$ , ı.e. every $xy$ -path of $G$ intersects $F$ . We show that there exists an $O(f(k)n^c)$ algorithm which decides if there exists a multicut of size at most $k$ . In other words, the \M{} problem parameterized by the solution size $k$ is Fixed-Parameter Tractable. The proof extends to vertex multicuts.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Stéphan Thomassé

Research overview

Is this your work?

35 publications

Maximum Independent Set when excluding an induced minor: K1+tK2K_1 + tK_2K1​+tK2​ and tC3⊎C4tC_3 \uplus C_4tC3​⊎C4​

(P6, triangle)-free digraphs have bounded dichromatic number

Extremal Independent Set Reconfiguration

A quasi-quadratic vertex Kernel for Cograph edge editing

Twin-width VI: the lens of contraction sequences

Twin-width VII: groups

Twin-width VIII: delineation and win-wins

Twin-width III: Max Independent Set, Min Dominating Set, and Coloring

An algorithmic weakening of the Erdős-Hajnal conjecture

Disproving the normal graph conjecture

On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five

Twin-width II: small classes

A Proof of the Barát-Thomassen Conjecture

Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture

A note on the minimum distance of quantum LDPC codes

A tau-conjecture for Newton polygons

Clique versus Independent Set

Conflict Packing: an unifying technique to obtain polynomial kernels for editing problems on dense instances

Graphs with large chromatic number induce 3k3k3k-cycles

Isolating highly connected induced subgraphs

Parameterized algorithm for weighted independent set problem in bull-free graphs

The Erdős-Hajnal Conjecture for Long Holes and Anti-holes

The Erdős-Hajnal Conjecture for Paths and Antipaths

VC-dimension and Erdős-Pósa property

Complements of nearly perfect graphs

Hitting and Harvesting Pumpkins

Symmetric Determinantal Representations in Characteristic 2

A Linear Vertex Kernel for Maximum Internal Spanning Tree

Parameterized Domination in Circle Graphs

Cyclic Orderings and Cyclic Arboricity of Matroids

Scott's induced subdivision conjecture for maximal triangle-free graphs

The Domination Number of Grids

Coloring dense graphs via VC-dimension

Edge Growth in Graph Cubes

Multicut is FPT

See the researcher in context

Building this map preview

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$

Graphs with large chromatic number induce $3k$ -cycles