Search

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]

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]

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]

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]