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]

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]

For any small positive real ε and integer t > 1 ε , we build a graph with a vertex deletion set of size t to a tree, and twin-width greater than 2 (1 − ε) t. In particular, this shows that the twin-width is sometimes exponential in the treewidth, in the so-called oriented twin-width and grid number, and that adding an apex may multiply the twin-width by at least 2 − ε. Except for the one in oriented twin-width, these lower bounds are essentially tight. [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 give essentially tight bounds for, ν (d , k) , the maximum number of distinct neighbourhoods on a set X of k vertices in a graph with twin-width at most d. Using the celebrated Marcus–Tardos theorem, two independent works (Bonnet et al., 2022; Przybyszewski, 2022) have shown the upper bound ν (d , k) ⩽ exp (exp (O (d))) k , with a double-exponential dependence in the twin-width. The work of Gajarsky et al. (2022), using the framework of local types, implies the existence of a single-exponential bound (without explicitly stating such a bound). We give such an explicit bound, and prove that it is essentially tight. Indeed, we give a short self-contained proof that for every d and k ν (d , k) ⩽ (d + 2) 2 d + 1 k = 2 d + log d + Θ (1) k , and build a bipartite graph implying ν (d , k) ⩾ 2 d + log d + Θ (1) k , in the regime when k is large enough compared to d. [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]

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]

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]

The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of Grundy Coloring , the problem of determining whether a given graph has Grundy number at least k . We also study the variants Weak Grundy Coloring (where the coloring is not necessarily proper) and Connected Grundy Coloring (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that Grundy Coloring can be solved in time O ∗ ( 2 . 44 3 n ) and Weak Grundy Coloring in time O ∗ ( 2 . 71 6 n ) on graphs of order n . While Grundy Coloring and Weak Grundy Coloring are known to be solvable in time O ∗ ( 2 O ( w k ) ) for graphs of treewidth w (where k is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time O ∗ ( 2 o ( w log w ) ) . We also describe an O ∗ ( 2 2 O ( k ) ) algorithm for Weak Grundy Coloring , which is therefore FPT for the parameter k . Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for Grundy Coloring ). Although we do not know whether Grundy Coloring is in FPT , we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for Grundy Coloring and Weak Grundy Coloring on apex-minor graphs. In stark contrast with the two other problems, we show that Connected Grundy Coloring is NP -complete already for k = 7 colors. [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]

The Graph Motif problem was introduced in 2006 in the context of biological networks. It consists of deciding whether or not a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Graph Motif has been mostly analyzed from the standpoint of parameterized complexity. The main parameters which came into consideration were the size of the multiset and the number of colors. In the many utilizations of Graph Motif , however, the input graph originates from real-life applications and has structure. Motivated by this prosaic observation, we systematically study its complexity relatively to graph structural parameters. For a wide range of parameters, we give new or improved FPT algorithms, or show that the problem remains intractable. For the FPT cases, we also give some kernelization lower bounds as well as some ETH-based lower bounds on the worst case running time. Interestingly, we establish that Graph Motif is W[1] -hard (while in W[P] ) for parameter max leaf number, which is, to the best of our knowledge, the first problem to behave this way. [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]

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]