Search

A graph is O k -free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) O k -free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of O 2 -free graphs without K 2 , 3 as a subgraph and whose treewidth is (at least) logarithmic. Using our result, we show that Maximum Independent Set and 3-Coloring in O k -free graphs can be solved in quasi-polynomial time. 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 O k -free graphs, and that deciding the O k -freeness of sparse graphs is polynomial time solvable. [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]

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]

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]

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]

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]