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]

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]

Let G be an intersection graph of n geometric objects in the plane. We show that a maximum matching in G can be found in O (ρ 3 ω / 2 n ω / 2) time with high probability, where ρ is the density of the geometric objects and ω > 2 is a constant such that n × n matrices can be multiplied in O (n ω) time. The same result holds for any subgraph of G, as long as a geometric representation is at hand. For this, we combine algebraic methods, namely computing the rank of a matrix via Gaussian elimination, with the fact that geometric intersection graphs have small separators. We also show that in many interesting cases, the maximum matching problem in a general geometric intersection graph can be reduced to the case of bounded density. In particular, a maximum matching in the intersection graph of any family of translates of a convex object in the plane can be found in O (n ω / 2) time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in [ 1 , Ψ ] can be found in O (Ψ 6 log 11 n + Ψ 12 ω n ω / 2) time with high probability. [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]

The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order σ , the smallest available color. The problem Grundy Coloring asks how many colors are needed for the most adversarial vertex ordering σ , i.e., the maximum number of colors that the first-fit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, Grundy Coloring has been examined for its structural and algorithmic aspects. A brute-force f (k) n 2 k - 1 -time algorithm for Grundy Coloring on general graphs is not difficult to obtain, where k is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on k in the exponent of n can be avoided or reduced, and its answer seemed elusive until now. We prove that Grundy Coloring is W[1]-hard and the brute-force algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative. The key ingredient in our W[1]-hardness proof is to use so-called half-graphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b -Chromatic Core is W[1]-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS '17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on K t , t -free graphs for b -Chromatic Core and Partial Grundy Coloring, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest. [ABSTRACT FROM AUTHOR]

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 Connectedk-Dominating Set and Totalk-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 Connectedk-Vertex Cover and Capacitatedk-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 Connectedk-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. [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]

We investigate the parameterized complexity in a and b of determining whether a graph G has a subset of a vertices and b edges whose removal disconnects G, or disconnects two prescribed vertices s , t ∈ V (G) . [ABSTRACT FROM AUTHOR]

A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polynomial time algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension with respect to treewidth. We provide a first answer to the question. We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension in time f (pw) n o (pw) on n-vertex graphs of constant degree, with pw the pathwidth of the input graph, and f any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. (SIAM J Discrete Math 31(2):1217–1243, 2017) with respect to the combined parameter tl + Δ , where tl is the tree-length and Δ the maximum-degree of the input graph. [ABSTRACT FROM AUTHOR]

We consider the inverse Voronoi diagram problem in trees: given a tree T with positive edge-lengths and a collection U of subsets of vertices of V(T), decide whether U is a Voronoi diagram in T with respect to the shortest-path metric. We show that the problem can be solved in O (N + n log 2 n) time, where n is the number of vertices in T and N = n + ∑ U ∈ U | U | is the size of the description of the input. We also provide a lower bound of Ω (n log n) time for trees with n vertices. [ABSTRACT FROM AUTHOR]

We introduce the inverse Voronoi diagram problem in graphs: given a graph G with positive edge-lengths and a collection U of subsets of vertices of V(G), decide whether U is a Voronoi diagram in G with respect to the shortest-path metric. We show that the problem is NP-hard, even for planar graphs where all the edges have unit length. We also study the parameterized complexity of the problem and show that the problem is W[1]-hard when parameterized by the number of Voronoi cells or by the pathwidth of the graph. [ABSTRACT FROM AUTHOR]

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

It has long been known that Feedback Vertex Set can be solved in time 2 O (w log w) n O (1) on n-vertex graphs of treewidth w, but it was only recently that this running time was improved to 2 O (w) n O (1) , that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class P of graphs, the Bounded P -Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k vertices such that each block of G - S has at most d vertices and is in P . Assuming that P is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d: if P consists only of chordal graphs, then the problem can be solved in time 2 O (w d 2) n O (1) , if P contains a graph with an induced cycle of length ℓ ⩾ 4 , then the problem is not solvable in time 2 o (w log w) n O (1) even for fixed d = ℓ , unless the ETH fails. We also study a similar problem, called Bounded P -Component Vertex Deletion, where the target graphs have connected components of small size rather than blocks of small size, and we present analogous results. For this problem, we also show that if d is part of the input and P contains all chordal graphs, then it cannot be solved in time f (w) n o (w) for some function f, unless the ETH fails. [ABSTRACT FROM AUTHOR]

Planar graphs are known to allow subexponential algorithms running in time 2 O (n) or 2 O (n log n) for most of the paradigmatic problems, while the brute-force time 2 Θ (n) is very likely to be asymptotically best on general graphs. Intrigued by an algorithm packing curves in 2 O (n 2 / 3 log n) by Fox and Pach (SODA'11), we investigate which problems have subexponential algorithms on the intersection graphs of curves (string graphs) or segments (segment intersection graphs) and which problems have no such algorithms under the Exponential Time Hypothesis (ETH). Among our results, we show that, quite surprisingly, 3-Coloring can also be solved in time 2 O (n 2 / 3 log O (1) n) on string graphs while an algorithm running in time 2 o (n) for 4-Coloring even on axis-parallel segments (of unbounded length) would disprove the ETH. For 4-Coloring of unit segments, we show a weaker lower bound, excluding a 2 o (n 2 / 3) algorithm (under the ETH). The construction exploits the celebrated Erdős–Szekeres theorem. The subexponential running time also carries over to Min Feedback Vertex Set, but not to Min Dominating Set and Min Independent Dominating Set. [ABSTRACT FROM AUTHOR]

In the TOKEN SWAPPING problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that TOKEN SWAPPING is W[1]-hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time f(k)no(k/logk) where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial nO(k)-time algorithm. We also consider two generalizations of the TOKEN SWAPPING, namely COLORED TOKEN SWAPPING (where the tokens have colors and tokens of the same color are indistinguishable), and SUBSET TOKEN SWAPPING (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, SUBSET TOKEN SWAPPING, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases. [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]

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]

We study the parameterized complexity of a broad class of problems called 'local graph partitioning problems' that includes the classical fixed cardinality problems as max $$k$$ - vertex cover, $$k$$ - densest subgraph, etc. By developing a technique that we call 'greediness-for-parameterization', we obtain fixed parameter algorithms with respect to a pair of parameters $$k$$ , the size of the solution (but not its value) and $$\varDelta $$ , the maximum degree of the input graph. In particular, greediness-for-parameterization improves asymptotic running times for these problems upon random separation (that is a special case of color coding) and is more intuitive and simple. Then, we show how these results can be easily extended for getting standard-parameterization results (i.e., with parameter the value of the optimal solution) for a well known local graph partitioning problem. [ABSTRACT FROM AUTHOR]