As shown by Robertson and Seymour, deciding whether the complete graph K_t is a minor of an input graph G is a fixed parameter tractable problem when parameterized by t. From the approximation viewpoint, a substantial gap remains: there is no PTAS for finding the largest complete minor unless P = NP, whereas the best known result is a polytime O(√ n)-approximation algorithm by Alon, Lingas and Wahlén. We investigate the complexity of finding K_t as interval minor in ordered graphs (i.e. graphs with a linear order on the vertices, in which intervals are contracted to form minors). Our main result is a polytime f(t)-approximation algorithm, where f is triply exponential in t but independent of n. The algorithm is based on delayed decompositions and shows that ordered graphs without a K_t interval minor can be constructed via a bounded number of three operations: closure under substitutions, edge union, and concatenation of a stable set. As a byproduct, graphs avoiding K_t as an interval minor have bounded chromatic number.

In its Euclidean form, the Dense Neighborhood Lemma (DNL) asserts that if V is a finite set of points of $\mathbb{R}^{N}$ such that for each $v \in V$ the ball $B(v, 1)$ intersects V on at least $\delta|V|$ points, then for every $\varepsilon\gt0$, the points of V can be covered with $f(\delta, \varepsilon)$ balls $B(v, 1+\varepsilon)$ with $v \in V$. DNL also applies to other metric spaces and to abstract set systems, where elements are compared pairwise with respect to (near) disjointness. In its strongest form, DNL provides an $\varepsilon$-clustering with size exponential in $\varepsilon^{-1}$, which amounts to a Regularity Lemma with 0/1 densities of some trigraph. Trigraphs are graphs with additional red edges. They are natural instances of partial concept classes, introduced by Alon, Hanneke, Holzman and Moran [FOCS 2021]. This paper is mainly a combinatorial study of the generalization of VapnikCervonenkis dimension to partial concept classes. The main point is to show how trigraphs can sometimes explain the success of random sampling even though the VC-dimension of the underlying graph is unbounded. All the results presented here are effective in the sense of computation: they primarily rely on uniform sampling with the same success rate as in classical VC-dimension theory. Among some applications of DNL, we show that $\left(\frac{3 t-8}{3 t-5}+\varepsilon\right) \cdot n$-regular $K_{t}$-free graphs have bounded chromatic number. Similarly, triangle-free graphs with minimum degree $n / 3-n^{1-\varepsilon}$ have bounded chromatic number (this does not hold with $n / 3-n^{1-o(1)}$). For tournaments, DNL implies that the domination number is bounded in terms of the fractional chromatic number. Also, $(1 / 2-\varepsilon)$-majority digraphs have bounded domination, independently of the number of voters.

Positional games were introduced by Hales and Jewett in 1963, and their study became more popular when Erdős and Selfridge showed their connection to Ramsey theory and hypergraph coloring in 1973. Several conventions of these games exist, and the most popular one, Maker-Breaker was proved to be PSPACE-complete by Schaefer in 1978. The study of their complexity then stopped for decades, until 2017 when Bonnet, Jamain, and Saffidine proved that Maker-Breaker is W[1]-complete when parameterized by the number of moves. The study was then intensified when Rahman and Watson improved Schaefer’s result in 2021 by proving that the PSPACE-hardness holds for 6-uniform hypergraphs. More recently, Galliot, Gravier, and Sivignon proved that computing the winner on rank 3 hypergraphs is in P, and Keopke proved that the PSPACE-hardness also holds for 5-uniform hypergraphs. We focus here on the Client-Waiter and the Waiter-Client conventions. Both were proved to be NP-hard by Csernenszky, Martin, and Pluhár in 2011, but neither completeness nor positive results were known. In this paper, we complete the study of these conventions by proving that the former is PSPACE-complete, even restricted to 6-uniform hypergraphs, and by providing an FPT-algorithm for the latter, parameterized by the size of its largest edge. In particular, the winner of Waiter-Client can be computed in polynomial time in rank k hypergraphs for any fixed integer k. Finally, in search of the exact location of the complexity gap in the Client-Waiter convention, we focus on rank 3 hypergraphs. We provide an algorithm that runs in polynomial time with an oracle in NP.

We study the notion of k-stabilizer universal quantum state, that is, an n-qubit quantum state, such that it is possible to induce any stabilizer state on any k qubits, by using only local operations and classical communications. These states generalize the notion of k-pairable states introduced by Bravyi et al., and can be studied from a combinatorial perspective using graph states and k-vertex-minor universal graphs. First, we demonstrate the existence of k-stabilizer universal graph states that are optimal in size with n = Θ(k²) qubits. We also provide parameters for which a random graph state on Θ(k²) qubits is k-stabilizer universal with high probability. Our second contribution consists of two explicit constructions of k-stabilizer universal graph states on n = O(k⁴) qubits. Both rely upon the incidence graph of the projective plane over a finite field 𝔽_q. This provides a major improvement over the previously known explicit construction of k-pairable graph states with n = O(2^{3k}), bringing forth a new and potentially powerful family of multipartite quantum resources.

We show that for any permutation π there exists an integer kπ such that every permutation avoiding π as a pattern factorises as the composition of at most kπ separable permutations. In other words, every strict class C of permutations is contained in a bounded power of the class of separable permutations. This factorisation can be computed in linear time, for any fixed π.

In a directed graph D on vertex set v₁,… ,v_n, a forward arc is an arc v_iv_j where i < j. A pair v_i,v_j is forward connected if there is a directed path from v_i to v_j consisting of forward arcs. In the Forward Connected Pairs Problem (FCPP), the input is a strongly connected digraph D, and the output is the maximum number of forward connected pairs in some vertex enumeration of D. We show that FCPP is in APX, as one can efficiently enumerate the vertices of D in order to achieve a quadratic number of forward connected pairs. For this, we construct a linear size balanced bi-tree T (an out-branching and an in-branching with same size and same root which are vertex disjoint in the sense that they share no vertex apart from their common root). The existence of such a T was left as an open problem (Brunelli, Crescenzi, Viennot, Networks 2023) motivated by the study of temporal paths in temporal networks. More precisely, T can be constructed in quadratic time (in the number of vertices) and has size at least n/3. The algorithm involves a particular depth-first search tree (Left-DFS) of independent interest, and shows that every strongly connected directed graph has a balanced separator which is a circuit. Remarkably, in the request version RFCPP of FCPP, where the input is a strong digraph D and a set of requests R consisting of pairs {x_i,y_i}, there is no constant c > 0 such that one can always find an enumeration realizing c.|R| forward connected pairs {x_i,y_i} (in either direction).

We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh et al. [ 5 ] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles the small conjecture [ 8 ] in the case of ordered graphs.

Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomass\'e, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been further extended to binary structures, in several (basically equivalent) ways. We prove that a class of binary relational structures (that is: edge-colored partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a~proper permutation class. As a by-product, we show that every class with bounded twin-width contains at most $2^{O(n)}$ pairwise non-isomorphic $n$-vertex graphs.

Abstract. We recently introduced the notion of twin-width, a novel graph invariant, and showed that first-order model checking can be solved in time [Formula: see text] for [Formula: see text]-vertex graphs given with a witness that the twin-width is at most [Formula: see text], called [Formula: see text]-contraction sequence or [Formula: see text]-sequence, and formulas of size [Formula: see text] [Bonnet et al., JACM ’22]. The inevitable price to pay for such a general result is that [Formula: see text] is a tower of exponentials of height roughly [Formula: see text]. In this paper, we show that algorithms based on twin-width need not be impractical. We present [Formula: see text]-time algorithms for [Formula: see text]-independent set, [Formula: see text]-scattered set, [Formula: see text]-clique, and [Formula: see text]-dominating set when an [Formula: see text]-sequence of the graph is given in input. We further show how to solve the weighted version of [Formula: see text]-independent set, subgraph isomorphism, and induced subgraph isomorphism in the slightly worse running time [Formula: see text]. Up to logarithmic factors in the exponent, all these running times are optimal unless the exponential time hypothesis fails. Like our first-order model checking algorithm, these new 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 of such a reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, thereby establishing that bounded twin-width classes are [Formula: see text]-bounded. This significantly extends the [Formula: see text]-boundedness of bounded rank-width classes and does so with a very concise proof. It readily yields a constant approximation for max independent set on [Formula: see text]-free graphs of bounded twin-width and a [Formula: see text]-approximation for min coloring on bounded twin-width graphs. We further observe that a constant approximation for max independent set on bounded twin-width graphs (but arbitrarily large clique number) would actually imply a polynomial-time approximation scheme. 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. This property is trivially shared with graphs of bounded average degree. Given that biclique edge-partition, we show how to solve the unweighted single-source shortest paths, and hence all-pairs shortest paths, in time [Formula: see text] and time [Formula: see text], respectively. In sharp contrast, even diameter does not admit a truly subquadratic algorithm on bounded twin-width graphs unless the strong exponential time hypothesis fails. The fourth algorithmic use of twin-width builds on the so-called versatile tree of contractions [Bonnet et al., Comb. Theory ’22], a branching and more robust witness of low twin-width. We present constant-approximation algorithms for min dominating set and related problems on bounded twin-width graphs by showing that the integrality gap is constant. This is done by going down the versatile tree and stopping according to a problem-dependent criterion. At the reached node, a greedy approach yields the desired approximation.

Abstract. In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of [Formula: see text] for any [Formula: see text]. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In [Formula: see text]-free graphs, that is, graphs not containing a fixed graph [Formula: see text] as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever [Formula: see text] contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of [Formula: see text] is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs [Formula: see text] such as [Formula: see text], [Formula: see text], the claw, or the fork. We prove that for every such “possibly tractable” graph [Formula: see text] there exists an algorithm that, given an [Formula: see text]-free graph [Formula: see text] and an accuracy parameter [Formula: see text], finds an independent set in [Formula: see text] of cardinality within a factor of [Formula: see text] of the optimum in time exponential in a polynomial of [Formula: see text] and [Formula: see text]. Furthermore, an independent set of maximum size can be found in subexponential time [Formula: see text]. That is, we show that for every graph [Formula: see text] for which Maximum Independent Set is not known to be APX-hard and SUBEXP-hard in [Formula: see text]-free graphs, the problem admits a quasi-polynomial time approximation scheme and a subexponential-time exact algorithm in this graph class. Our algorithms also work in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.

We re-visit the complexity of polynomial time pre-processing (kernelization) for the d-Hitting Set problem. This is one of the most classic problems in Parameterized Complexity by itself, and, furthermore, it encompasses several other of the most well-studied problems in this field, such as Vertex Cover, Feedback Vertex Set in Tournaments (FVST) and Cluster Vertex Deletion (CVD). In fact, d-Hitting Set encompasses any deletion problem to a hereditary property that can be characterized by a finite set of forbidden induced subgraphs. With respect to bit size, the kernelization complexity of d-Hitting Set is essentially settled: there exists a kernel with 𝒪(k^d) bits (𝒪(k^d) sets and 𝒪(k^{d-1}) elements) and this it tight by the result of Dell and van Melkebeek [STOC 2010, JACM 2014]. Still, the question of whether there exists a kernel for d-Hitting Set with fewer elements has remained one of the most major open problems in Kernelization. In this paper, we first show that if we allow the kernelization to be lossy with a qualitatively better loss than the best possible approximation ratio of polynomial time approximation algorithms, then one can obtain kernels where the number of elements is linear for every fixed d. Further, based on this, we present our main result: we show that there exist approximate Turing kernelizations for d-Hitting Set that even beat the established bit-size lower bounds for exact kernelizations - in fact, we use a constant number of oracle calls, each with "near linear" (𝒪(k^{1+ε})) bit size, that is, almost the best one could hope for. Lastly, for two special cases of implicit 3-Hitting set, namely, FVST and CVD, we obtain the "best of both worlds" type of results - (1+ε)-approximate kernelizations with a linear number of vertices. In terms of size, this substantially improves the exact kernels of Fomin et al. [SODA 2018, TALG 2019], with simpler arguments.

International audience

A graph is Ok-free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We show that MAXIMUM INDEPENDENT SET and 3-COLORING in Ok-free graphs can be solved in quasi-polynomial time. As a main technical result, we establish that “sparse” (here, not containing large complete bipartite graphs as subgraphs) Ok-free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is proven sharp as there is an infinite family of O2-free graphs without K3,3-subgraph and whose treewidth is (at least) logarithmic. Other consequences include that most of the central NP-complete problems (such as MAXIMUM INDEPENDENT SET, MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM COLORING) can be solved in polynomial time in sparse Ok-free graphs, and that deciding the Ok-freeness of sparse graphs is polynomial time solvable. * This work was supported by the ANR projects DISTANCIA (ANR-17-CE40-0015), DIGRAPHS (ANR-19-CE48-0013-01), and TWIN-WIDTH (ANR-21-CE48-0014-01), by the LabEx PERSYVAL-lab (ANR-11-LABX-0025), and by the Vanier Canada Graduate Scholarships program. † The full version of the paper can be accessed at https://arxiv.org/abs/2206.00594

We continue developing the theory around the twin-width of totally ordered binary structures, initiated in the previous paper of the series. We first introduce the notion of parity and linear minors of a matrix, which consists of iteratively replacing consecutive rows or consecutive columns with a linear combination of them. We show that a matrix class has bounded twin-width if and only if its linear-minor closure does not contain all matrices. We observe that the fixed-parameter tractable algorithm for first-order model checking on structures given with an $O(1)$-sequence (certificate of bounded twin-width) and the fact that first-order transductions of bounded twin-width classes have bounded twin-width, both established in Twin-width I, extend to first-order logic with modular counting quantifiers. We make explicit a win-win argument obtained as a by-product of Twin-width IV, and somewhat similar to bidimensionality, that we call rank-bidimensionality. Armed with the above-mentioned extension to modular counting, we show that the twin-width of the product of two conformal matrices $A, B$ over a finite field is bounded by a function of the twin-width of $A$, of $B$, and of the size of the field. Furthermore, if $A$ and $B$ are $n \times n$ matrices of twin-width $d$ over $\mathbb F_q$, we show that $AB$ can be computed in time $O_{d,q}(n^2 \log n)$. We finally present an ad hoc algorithm to efficiently multiply two matrices of bounded twin-width, with a single-exponential dependence in the twin-width bound: If the inputs are given in a compact tree-like form, called twin-decomposition (of width $d$), then two $n \times n$ matrices $A, B$ over $\mathbb F_2$, a twin-decomposition of $AB$ with width $2^{d+o(d)}$ can be computed in time $4^{d+o(d)}n$ (resp. $4^{d+o(d)}n^{1+\varepsilon}$), and entries queried in doubly-logarithmic (resp. constant) time.

We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures of subclasses D of C, FO model checking on D is fixed-parameter tractable (FPT) exactly when 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 observe or show that segment graphs, directed path graphs (with arbitrarily many roots), 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₄-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated. More broadly, we explore which structures (large bicliques, half-graphs, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for first-order model checking on graphs given with O(1)-sequences [BKTW, JACM '22], give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If p is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C, then p(G) ⩾ k can be decided in FPT time f(k) ⋅ |V(G)|^O(1). For instance, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width.

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 error edges, henceforth red edges, between two vertices representing non-homogeneous subsets, the twin-width is the minimum integer d such that a contraction sequence exists that 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 –usually defined in the framework of branch-decompositions–, and proper minor-closed classes by means of contraction sequences. Contraction sequences hold a crucial advantage over branch-decompositions: While one can scale down contraction sequences to capture classical width notions, the more general bounded twin-width goes beyond their scope, as it contains planar graphs in particular, a class with unbounded rank-width. 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 MSO2 (resp. MSO1) model checking on graphs with bounded tree-width (resp. bounded rank-width) is fixed-parameter tractable in the size of the input sentence. We are hopeful that our characterizations can help in other contexts. 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. This greatly simplifies the task of showing that a class has bounded twin-width. As an example, using a lemma by Norine, Seymour, Thomas, and Wollan, we give a 5-line proof that Kt-minor free graphs have bounded twin-width. Without oriented twin-width, this fact was shown by a somewhat intricate 4-page proof in the first paper of the series. Finally we explore the concept of partial contraction sequences, instead of terminating on a single-vertex graph, the sequence ends when reaching a particular target class. We show that FO model checking (resp. ∃FO model checking) is fixed-parameter tractable on classes with partial contraction sequences to a class of bounded degree (resp. bounded expansion), provided such a sequence is given. Efficiently finding such partial sequences could turn out simpler than finding a (complete) sequence.

We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory.

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 of this reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, establishing that bounded twin-width classes are $\chi$-bounded. This significantly extends the $\chi$-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.

We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main result is that a polynomial kernel for $k$-Dominating Set on graphs of twin-width at most 4 would contradict a standard complexity-theoretic assumption. The reduction is quite involved, especially to get the twin-width upper bound down to 4, and can be tweaked to work for Connected $k$-Dominating Set and Total $k$-Dominating Set (albeit with a worse upper bound on the twin-width). The $k$-Independent Set problem admits the same lower bound by a much simpler argument, previously observed [ICALP '21], which extends to $k$-Independent Dominating Set, $k$-Path, $k$-Induced Path, $k$-Induced Matching, etc. On the positive side, we obtain a simple quadratic vertex kernel for Connected $k$-Vertex Cover and Capacitated $k$-Vertex Cover on graphs of bounded twin-width. Interestingly the kernel applies to graphs of Vapnik-Chervonenkis density 1, and does not require a witness sequence. We also present a more intricate $O(k^{1.5})$ vertex kernel for Connected $k$-Vertex Cover. Finally we show that deciding if a graph has twin-width at most 1 can be done in polynomial time, and observe that most optimization/decision graph problems can be solved in polynomial time on graphs of twin-width at most 1.

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!cn 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 Kn (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 logd+1 n-subdivision of Kn 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 K4 [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 Kt,t-free for some fixed t, (2) has an adjacency matrix without a d-by-d division with a 1 entry in each d2 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.

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for M AXIMUM C LIQUE on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics ’90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2 Õ( n 2/3 ) for M AXIMUM C LIQUE on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for M AX C LIQUE on disk and unit ball graphs. M AX C LIQUE on unit ball graphs is equivalent to finding, given a collection of points in R 3 , a maximum subset of points with diameter at most some fixed value. In stark contrast, M AXIMUM C LIQUE on ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2 n 1−ɛ , unless the Exponential Time Hypothesis fails.

In the classic Maximum Weight Independent Set problem we are given a graph $G$ with a nonnegative weight function on vertices, and the goal is to find an independent set in $G$ of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any $P_6$-free graph, that is, a graph that has no path on $6$ vertices as an induced subgraph. This improves the polynomial-time algorithm on $P_5$-free graphs of Lokshtanov et al. (SODA 2014), and the quasipolynomial-time algorithm on $P_6$-free graphs of Lokshtanov et al (SODA 2016). The main technical contribution leading to our main result is enumeration of a polynomial-size family $\mathcal{F}$ of vertex subsets with the following property: for every maximal independent set $I$ in the graph, $\mathcal{F}$ contains all maximal cliques of some minimal chordal completion of $G$ that does not add any edge incident to a vertex of $I$.

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].

In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In H-free graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter ε > 0, finds an independent set in G of cardinality within a factor of (1 – ε) of the optimum in time exponential in a polynomial of log | V(G) | and ε−1. That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.

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.

Maximum Independent Set (MIS for short) is in general graphs the paradigmatic $W[1]$-hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restricted to structured graph classes such as, for instance, perfect graphs (which includes bipartite graphs, chordal graphs, co-graphs, etc.) or claw-free graphs. In this paper, we introduce some variants of co-graphs with parameterized noise, that is, graphs that can be made into disjoint unions or complete sums by the removal of a certain number of vertices and the addition/deletion of a certain number of edges per incident vertex, both controlled by the parameter. We give a series of FPT Turing-reductions on these classes and use them to make some progress on the parameterized complexity of MIS in $H$-free graphs. We show that for every fixed $t \geqslant 1$, MIS is FPT in $P(1,t,t,t)$-free graphs, where $P(1,t,t,t)$ is the graph obtained by substituting all the vertices of a four-vertex path but one end of the path by cliques of size $t$. We also provide randomized FPT algorithms in dart-free graphs and in cricket-free graphs. This settles the FPT/W[1]-hard dichotomy for five-vertex graphs $H$.

The class of even-hole-free graphs is very similar to the class of perfect graphs, and was indeed a cornerstone in the tools leading to the proof of the Strong Perfect Graph Theorem. However, the complexity of computing a maximum independent set (MIS) is a long-standing open question in even-hole-free graphs. From the hardness point of view, MIS is W[1]-hard in the class of graphs without induced 4-cycle (when parameterized by the solution size). Halfway of these, we show in this paper that MIS is FPT when parameterized by the solution size in the class of even-hole-free graphs. The main idea is to apply twice the well-known technique of augmenting graphs to extend some initial independent set.

We consider four well-studied NP-complete packing/covering problems on graphs: F eedback V ertex S et in T ournaments (FVST), C luster V ertex D eletion (CVD), T riangle P acking in T ournaments (TPT) and I nduced P 3 -P acking . For these four problems, kernels with O ( k 2 ) vertices have been known for a long time. In fact, such kernels can be obtained by interpreting these problems as finding either a packing of k pairwise disjoint sets of size 3 (3-S et P acking ) or a hitting set of size at most k for a family of sets of size at most 3 (3-H itting S et ). In this article, we give the first kernels for FVST, CVD, TPT, and I nduced P 3 -P acking with a subquadratic number of vertices. Specifically, we obtain the following results. • FVST admits a kernel with O ( k 3/2 ) vertices. • CVD admits a kernel with O ( k 5/3 ) vertices. • TPT admits a kernel with O ( k 3/2 ) vertices. • I nduced P 3 -P acking admits a kernel with O ( k 5/3 ) vertices. Our results resolve an open problem from WorKer 2010 on the existence of kernels with O( k 2−ϵ ) vertices for FVST and CVD. All of our results are based on novel uses of old and new “expansion lemmas” and a weak form of crown decomposition where (i) almost all of the head is used by the solution (as opposed to all ), (ii) almost none of the crown is used by the solution (as opposed to none ), and (iii) if H is removed from G , then there is almost no interaction between the head and the rest (as opposed to no interaction at all).

We propose a polynomial-time algorithm which takes as input a finite set of points of R^3 and computes, up to arbitrary precision, a maximum subset with diameter at most 1. More precisely, we give the first randomized EPTAS and deterministic PTAS for Maximum Clique in unit ball graphs. Our approximation algorithm also works on disk graphs with arbitrary radii, in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Clique on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. Recently, it was shown that the disjoint union of two odd cycles is never the complement of a disk graph [Bonnet, Giannopoulos, Kim, Rzazewski, Sikora; SoCG '18]. This enabled the authors to derive a QPTAS and a subexponential algorithm for Max Clique on disk graphs. In this paper, we improve the approximability to a randomized EPTAS (and a deterministic PTAS). More precisely, we obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. We then address the question of computing Max Clique for disks in higher dimensions. We show that intersection graphs of unit balls, like disk graphs, do not admit the complement of two odd cycles as an induced subgraph. This, in combination with the first result, straightforwardly yields a randomized EPTAS for Max Clique on unit ball graphs. In stark contrast, we show that on ball graphs and unit 4-dimensional disk graphs, Max Clique is NP-hard and does not admit an approximation scheme even in subexponential-time, unless the Exponential Time Hypothesis fails.

In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains NP-hard for most graphs H, we study its fixed-parameter tractability and make progress towards a dichotomy between FPT and W[1]-hard cases. We first show that MIS remains W[1]-hard in graphs forbidding simultaneously K_{1, 4}, any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning C_4-free graphs. Then we extend the polynomial algorithm of Alekseev when H is a disjoint union of edges to an FPT algorithm when H is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of iterative expansion accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called iterative compression. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs H.

We consider four well-studied NP-complete packing/covering problems on graphs: Feedback Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P3-Packing. For these four problems kernels with O(k2) vertices have been known for a long time. In fact, such kernels can be obtained by interpreting these problems as finding either a packing of k pairwise disjoint sets of size 3 (3-Set Packing) or a hitting set of size at most k for a family of sets of size at most 3 (3-Hitting Set). In this paper, we give the first kernels for FVST, CVD, TPT and Induced P3-Packing with a subquadratic number of vertices. Specifically, we obtain the following results. • FVST admits a kernel with vertices. • CVD admits a kernel with vertices. • TPT admits a kernel with vertices. • Induced P3-Packing admits a kernel with vertices. Our results resolve an open problem from WorKer 2010 on the existence of kernels with

Let $G=(V,E)$ be a graph on $n$ vertices and $R$ be a set of pairs of vertices in $V$ called requests. A multicut is a subset $F$ of $E$ such that every request $xy$ of $R$ is separated by $F$, i.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 Multicut problem parameterized by the solution size $k$ is fixed-parameter tractable (FPT).

It was conjectured by Jaeger et al. in 1992 that for any prime number $p$, there is a constant $c$ such that for any $n$, the union (with repetition) of the vectors of any family of $c$ linear bases of $\mathbb{Z}_p^n$ forms an additive basis of $\mathbb{Z}_p^n$ (i.e., any element of $\mathbb{Z}_p^n$ can be expressed as the sum of a subset of these vectors). In this note, we prove this conjecture when each vector contains at most two nonzero entries. As an application, we prove several results on flows in highly edge-connected graphs, extending known results. For instance, assume that $p\geqslant 3$ is a prime number and $\vec{G}$ is a directed, highly edge-connected graph in which each arc is given a list of two distinct values in $\mathbb{Z}_p$. Then $\vec{G}$ has a $\mathbb{Z}_p$-flow in which each arc is assigned a value of its own list.

The method of partial derivatives is one of the most successful lower bound methods for arithmetic circuits. It uses as a complexity measure the dimension of the span of the partial derivatives of a polynomial. In this paper, we consider this complexity measure as a computational problem: for an input polynomial given as the sum of its nonzero monomials, what is the complexity of computing the dimension of its space of partial derivatives? We show that this problem is #P-hard and we ask whether it belongs to #P. We analyze the "trace method", recently used in combinatorics and in algebraic complexity to lower bound the rank of certain matrices. We show that this method provides a polynomial-time computable lower bound on the dimension of the span of partial derivatives, and from this method we derive closed-form lower bounds. We leave as an open problem the existence of an approximation algorithm with reasonable performance guarantees.A slightly shorter version of this paper was presented at STACS'17. In this new version we have corrected a typo in Section 4.1, and added a reference to Shitov's work on tensor rank.

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 an 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 at least $n^{c_k}$.

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 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.

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We show a dichotomy for the size of the smallest identifying code in classes of graphs closed under induced subgraphs. Our dichotomy is derived from the VC-dimension of the considered class $\mathcal{C}$, that is, the maximum VC-dimension over the hypergraphs formed by the closed neighborhoods of elements of $\mathcal{C}$. We show that hereditary classes with infinite VC-dimension have infinitely many graphs with an identifying code of size logarithmic in the number of vertices, while classes with finite VC-dimension have a polynomial lower bound. We then turn to approximation algorithms. We show that Min Id Code (the problem of finding a smallest identifying code in a given graph from some class $\mathcal{C}$) is log-APX-hard for any hereditary class of infinite VC-dimension. For hereditary classes of finite VC-dimension, the only known previous results show that we can approximate Min Id Code within a constant factor in some particular classes, e.g., line graphs, planar graphs, and unit interval graphs. We prove that Min Id Code can be approximate within a factor 6 for interval graphs. In contrast, we show that Min Id Code on $C_4$-free bipartite graphs (a class of finite VC-dimension) cannot be approximated to within a factor of $c \log(|V|)$ for some $c>0$.

The $c$-pumpkin is the graph with two vertices linked by $c \geq 1$ 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 hitting and packing $c$-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time $2^{\mathcal{O}(k)} n^{\mathcal{O}(1)}$ deciding, for any fixed $c \geq 1$, whether all $c$-pumpkin-models can be hit 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. Finally, we present an $\mathcal{O}(\log n)$-approximation algorithm for both the problems of hitting all $c$-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint $c$-pumpkin-models.

We discuss three equivalent forms of the same problem arising in communication complexity, constraint satisfaction problems, and graph coloring. Some partial results are discussed.

In the parameterized problem MaxLin2-AA[$k$], we are given a system with variables x_1,...,x_n consisting of equations of the form Product_{i in I}x_i = b, where x_i,b in {-1, 1} and I is a nonempty subset of {1,...,n}, each equation has a positive integral weight, and we are to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2+k, where W is the total weight of all equations and k is the parameter (if k=0, the possibility is assured). We show that MaxLin2-AA[k] has a kernel with at most O(k^2 log k) variables and can be solved in time 2^{O(k log k)}(nm)^{O(1)}. This solves an open problem of Mahajan et al. (2006). The problem Max-r-Lin2-AA[k,r] is the same as MaxLin2-AA[k] with two differences: each equation has at most r variables and r is the second parameter. We prove a theorem on Max-$r$-Lin2-AA[k,r] which implies that Max-r-Lin2-AA[k,r] has a kernel with at most (2k-1)r variables, improving a number of results including one by Kim and Williams (2010). The theorem also implies a lower bound on the maximum of a function f that maps {-1,1}^n to the set of reals and whose Fourier expansion (which is a multilinear polynomial) is of degree r. We show applicability of the lower bound by giving a new proof of the Edwards-Erdös bound (each connected graph on n vertices and m edges has a bipartite subgraph with at least m/2 +(n-1)/4 edges) and obtaining a generalization.

Let G=(V,E) be a graph on n vertices and R be a set of pairs of vertices in V called requests. A multicut is a subset F of E such that every request xy of R is cut by F, i.e. every xy-path of G intersects F. We show that there exists an O(f(k)nc) algorithm which decides if there exists a multicut of size at most k. In other words, the Multicut problem parameterized by the solution size k is Fixed-Parameter Tractable.

In this paper, we conclude the calculation of the domination number of all [Formula: see text] grid graphs. Indeed, we prove Chang’s conjecture saying that for every [Formula: see text], [Formula: see text].

We prove that given an undirected graph G on n vertices and an integer k , one can compute, in polynomial time in n , a graph G′ with at most 4 k 2 vertices and an integer k′ such that G has a feedback vertex set of size at most k iff G′ has a feedback vertex set of size at most k′ . This result improves a previous O ( k 11 ) kernel of Burrage et al., and a more recent cubic kernel of Bodlaender. This problem was communicated by Fellows.

A tournament $T = (V,A)$ is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on $n$ vertices and an integer parameter $k$, the {\sc Feedback Arc Set} problem asks whether thegiven digraph has a set of $k$ arcs whose removal results in an acyclicdigraph. The {\sc Feedback Arc Set} problem restricted to tournaments is knownas the {\sc $k$-Feedback Arc Set in Tournaments ($k$-FAST)} problem. In thispaper we obtain a linear vertex kernel for \FAST{}. That is, we give apolynomial time algorithm which given an input instance $T$ to \FAST{} obtains an equivalent instance $T'$ on $O(k)$ vertices. In fact, given any fixed $\epsilon > 0$, the kernelized instance has at most $(2 + \epsilon)k$ vertices.Our result improves the previous known bound of $O(k^2)$ on the kernel size for\FAST{}. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for \FAST.

We prove that given an undirected graph G on n vertices and an integer k, one can compute in polynomial time in n a graph G′ with at most 5k2 +k vertices and an integer k′ such that G has a feedback vertex set of size at most k iff G′ has a feedback vertex set of size at most k′. This result improves a previous O(k11) kernel of Burrage et al. [6], and a more recent cubic kernel of Bodlaender [3]. This problem was communicated by Fellows in [5].

The {\sc Multicut In Trees} problem consists in deciding, given a tree, a set of requests (i.e. paths in the tree) and an integer $k$, whether there exists a set of $k$ edges cutting all the requests. This problem was shown to be FPT by Guo and Niedermeyer (2005). They also provided an exponential kernel. They asked whether this problem has a polynomial kernel. This question was also raised by Fellows (2006). We show that {\sc Multicut In Trees} has a polynomial kernel.