Search

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. [ABSTRACT FROM AUTHOR]

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 $\left| V(G) \right|-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 $\Theta(\left| V(G) \right|)$ pairwise disjoint pairs of vertices. This has two main consequences. First it permits to show that every bounded twin-width class is small, i.e., has at most $n!c^n$ graphs labeled by $[n]$, for some constant $c$. This unifies and extends the same result for bounded treewidth graphs [Beineke and Pippert, JCT '69], proper subclasses of permutations graphs [Marcus and Tardos, JCTA '04], and proper minor-free classes [Norine et al., JCTB '06]. It implies in turn that bounded-degree graphs, interval graphs, and unit disk graphs have unbounded twin-width. The second consequence is an $O(\log n)$-adjacency labeling scheme for bounded twin-width graphs, confirming several cases of the implicit graph conjecture. We then explore the small conjecture that, conversely, every small hereditary class has bounded twin-width. The conjecture passes many tests. Inspired by sorting networks of logarithmic depth, we show that $\log_{\Theta(\log \log d)}n$-subdivisions of $K_n$ (a small class when $d$ is constant) have twin-width at most $d$. We obtain a rather sharp converse with a surprisingly direct proof: the $\log_{d+1}n$-subdivision of $K_n$ has twin-width at least $d$. Secondly graphs with bounded stack or queue number (also small classes) have bounded twin-width. These sparse classes are surprisingly rich since they contain certain (small) classes of expanders. Thirdly we show that cubic expanders obtained by iterated random 2-lifts from $K_4$ [Bilu and Linial, Combinatorica '06] also have bounded twin-width. These graphs are related to so-called separable permutations and also form a small class. We suggest a promising connection between the small conjecture and group theory. Finally we define a robust notion of sparse twin-width. We show that for a hereditary class $\mathcal C$ of bounded twin-width the five following conditions are equivalent: every graph in $\mathcal C$ (1) has no $K_{t,t}$ subgraph for some fixed $t$, (2) has an adjacency matrix without a $d$-by-$d$ division with a 1 entry in each of the $d^2$ cells for some fixed $d$, (3) has at most linearly many edges, (4) the subgraph closure of $\mathcal C$ has bounded twin-width, and (5) $\mathcal C$ has bounded expansion. We discuss how sparse classes with similar behavior with respect to clique subdivisions compare to bounded sparse twin-width.Mathematics Subject Classifications: 68R10, 05C30, 05C48Keywords: Twin-width, small classes, expanders, clique subdivisions, sparsity

Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, 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 2O(n) pairwise non-isomorphic n-vertex graphs. [ABSTRACT FROM AUTHOR]

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 under 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]. [ABSTRACT FROM AUTHOR]

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over F2, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or, in other words, whether there is a nonzero vector x such that Ax has at most k nonzero coordinates. The question of whether k-Even Set is fixed parameter tractable (FPT) parameterized by the distance k has been repeatedly raised in the literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows [1999]. In this work, we show that k-Even Set is W[1]-hard under randomized reductions. We also consider the parameterized k-Shortest Vector Problem (SVP), in which we are given a latticewhose basis vectors are integral and an integer k, and the goal is to determine whether the norm of the shortest vector (in the ℓp norm for some fixed p) is at most k. Similar to k-Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any p > 1, k-SVP is W[1]-hard to approximate (under randomized reductions) to some constant factor. [ABSTRACT FROM AUTHOR]

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 Maximum Cliqe 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²/3 ) for Maximum Cliqe 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 Max Cliqe on disk and unit ball graphs. Max Cliqe on unit ball graphs is equivalent to finding, given a collection of points in R³, a maximum subset of pointswith diameter at most some fixed value. In stark contrast, Maximum Cliqe 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 showthat, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2n1-ε, unless the Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]

We show, assuming the Strong Exponential Time Hypothesis, that for every ε > 0, approximating undirected unweighted Diameter on n-vertexm-edge graphs within ratio 7/4-ε requiresm4/3-o(1) time, evenwhenm = ˜O (n). This is the first result that conditionally rules out a near-linear time 5/3-approximation for undirected Diameter. [ABSTRACT FROM AUTHOR]

Given a simple polygon P on n vertices, two points x,y in P are said to be visible to each other if the line segment between x and y is contained in P. The Point Guard Art Gallery problem asks for a minimum set S such that every point in P is visible from a point in S. The Vertex Guard Art Gallery problem asks for such a set S subset of the vertices of P. A point in the set S is referred to as a guard. For both variants, we rule out any f (k)no(k/log k) algorithm, where k := |S | is the number of guards, for any computable function f, unless the exponential time hypothesis fails. These lower bounds almost match the nO(k) algorithms that exist for both problems. [ABSTRACT FROM AUTHOR]

A ribonucleic acid (RNA) sequence is a word over an alphabet on four elements { A , C , G , U } called bases. RNA sequences fold into secondary structures where some bases pair with one another, while others remain unpaired. The two fundamental problems in RNA algorithmic are to predict how sequences fold within some models of energy and to design sequences of bases that will fold into targeted secondary structures. Predicting how a given RNA sequence folds into a pseudoknot-free secondary structure is known to be solvable in cubic time since the eighties and in truly subcubic time by a recent result of Bringmann et al. (FOCS, 2016), whereas Lyngsø has shown it is computationally hard if pseudoknots are allowed (ICALP, 2004). As a stark contrast, it is unknown whether or not designing a given RNA secondary structure is a tractable task; this has been raised as a challenging open question by Condon (ICALP, 2003). Because of its crucial importance in a number of fields such as pharmaceutical research and biochemistry, there are dozens of heuristics and software libraries dedicated to the RNA secondary structure design. It is therefore rather surprising that the computational complexity of this central problem in bioinformatics has been unsettled for decades. In this article, we show that in the simplest model of energy, which is the Watson–Crick model, the design of secondary structures is computationally hard if one adds natural constraints of the form: indexiof the sequence has to be labeled by baseb. This negative result suggests that the same lower bound holds for more realistic models of energy. It is noteworthy that the additional constraints are by no means artificial: they are provided by all the RNA design pieces of software and they do correspond to the actual practice (e.g., the instances of the EteRNA project). [ABSTRACT FROM AUTHOR]

In this paper we focus on problems inapproximable in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For Min Independent Dominating Set , Max Induced Path , Forest and Tree , for any r ( n ) , a simple, known scheme gives an approximation ratio of r in time roughly r n / r . We show that, if this running time could be significantly improved, the ETH would fail. For Max Minimal Vertex Cover we give a r -approximation in time 2 n / r . We match this with a similarly tight result. We also give a log ⁡ r -approximation for Min ATSP in time 2 n / r and an r -approximation for Max Grundy Coloring in time r n / r . Finally, we investigate the approximability of Min Set Cover , when measuring the running time as a function of the number of sets in the input. [ABSTRACT FROM AUTHOR]

Instance sparsification is well-known in the world of exact computation since it is very closely linked to the Exponential Time Hypothesis. In this paper, we extend the concept of sparsification in order to capture subexponential time approximation. We develop a new tool for inapproximability, called approximation preserving sparsification, and use it in order to get strong inapproximability results in subexponential time for several fundamental optimization problems such as min dominating set, min feedback vertex set, min set cover, min feedback arc set, and others. [ABSTRACT FROM AUTHOR]

In the Maximum Common Induced Subgraph problem (henceforth MCIS), given two graphs G 1 and G 2 , one looks for a graph with the maximum number of vertices being both an induced subgraph of G 1 and G 2 . MCIS is among the most studied classical NP -hard problems. It remains NP -hard on many graph classes including forests. In this paper, we study the parameterized complexity of MCIS. As a generalization of Clique , it is W [ 1 ] -hard parameterized by the size of the solution. Being NP -hard even on forests, most structural parameterizations are intractable. One has to go as far as parameterizing by the size of the minimum vertex cover to get some tractability. Indeed, when parameterized by k : = vc ( G 1 ) + vc ( G 2 ) the sum of the vertex cover number of the two input graphs, the problem was shown to be fixed-parameter tractable, with an algorithm running in time 2 O ( k log ⁡ k ) . We complement this result by showing that, unless the ETH fails, it cannot be solved in time 2 o ( k log ⁡ k ) . This kind of tight lower bound has been shown for a few problems and parameters but, to the best of our knowledge, not for the vertex cover number. We also show that MCIS does not have a polynomial kernel when parameterized by k , unless NP ⊆ coNP / poly . Finally, we study MCIS and its connected variant MCCIS on some special graph classes and with respect to other structural parameters. [ABSTRACT FROM AUTHOR]

In this paper, we study three connection games among the most widely played: havannah , twixt , and slither . We show that determining the outcome of an arbitrary input position is PSPACE -complete in all three cases. Our reductions are based on the popular graph problem generalized geography and on hex itself. We also consider the complexity of generalizations of hex parameterized by the length of the solution and establish that while short generalized hex is W[1] -hard, short hex is FPT . Finally, we prove that the ultra-weak solution to the empty starting position in hex cannot be fully adapted to any of these three games. [ABSTRACT FROM AUTHOR]

This note resolves an open problem asked by Bezrukov in the open problem session of IWOCA 2014. It shows an equivalence between regular graphs and graphs for which a sequence of invariants presents some symmetric property. We extend this result to a few other sequences. [ABSTRACT FROM AUTHOR]

Given a family of subsets S over a set of elements X and two integers p and k, max k-set cover consists of finding a subfamilyT ⊆S of cardinality at most k, covering at least p elements of X. This problem is W[2]-hard when parameterized by k, and FPT when parameterized by p. We investigate the parameterized approximability of the problem with respect to parameters k and p. Then, we show that max sat-k, a satisfiability problem generalizing max k-set cover, is also FPT with respect to parameter p. [ABSTRACT FROM AUTHOR]