Search

For an integer r ≥ 0 the r-th iterated line graph L r (G) of a graph G is defined by: (i) L 0 (G) = G and (ii) L r (G) = L (L (r − 1) (G)) for r > 0 , where L (G) denotes the line graph of G. The Hamiltonian Index h (G) of G is the smallest r such that L r (G) has a Hamiltonian cycle [Chartrand, 1968]. Checking if h (G) = k is NP -hard for any fixed integer k ≥ 0 even for subcubic graphs G [Ryjáček et al., 2011]. We study the parameterized complexity of this problem with the parameter treewidth, t w (G) , and show that we can find h (G) in time1 O ⋆ ((1 + 2 (ω + 3)) t w (G)) where ω is the matrix multiplication exponent. Prior work on computing h (G) includes various O ⋆ (2 O (t w (G))) -time algorithms for checking if h (G) = 0 holds; i.e., whether G has a Hamiltonian Cycle [Cygan et al., FOCS 2011; Bodlaender et al., Inform. Comput., 2015; Fomin et al., JACM 2016]; an O ⋆ (t w (G) O (t w (G))) -time algorithm for checking if h (G) = 1 holds; i.e., whether L (G) has a Hamiltonian Cycle [Lampis et al., Discrete Appl. Math., 2017]; and, most recently, an O ⋆ ((1 + 2 (ω + 3)) t w (G)) -time algorithm for checking if h (G) = 1 holds [Misra et al., CSR 2019]. Our algorithm for computing h (G) generalizes these results. The NP -hard Eulerian Steiner Subgraph problem takes as input a graph G and a specified subset K of terminal vertices of G and asks if G has an Eulerian2 subgraph H containing all the terminals. A key ingredient of our algorithm for finding h (G) is an algorithm which solves Eulerian Steiner Subgraph in O ⋆ ((1 + 2 (ω + 3)) t w (G)) time. To the best of our knowledge this is the first FPT algorithm for Eulerian Steiner Subgraph. Prior work on the special case of finding a spanning Eulerian subgraph (i.e., with K = V (G)) includes a polynomial-time algorithm for series-parallel graphs [Richey et al., 1985] and an O ⋆ (2 O (n)) -time algorithm for planar graphs on n vertices [Sau and Thilikos, 2010]. Our algorithm for Eulerian Steiner Subgraph generalizes both these results. [ABSTRACT FROM AUTHOR]

FEEDBACK VERTEX SET (FVS) is one of the most well-studied problems in the realm of parameterized complexity. In this problem we are given a graph G and a positive integer k and the objective is to test whether there exists S ⊆ V (G) of size at most k such that G - S is a forest. Thus, FVS is about deleting as few vertices as possible to get a forest. The main goal of this paper is to study the following interesting problem: How can we generalize the family of forests such that the nice structural properties of forests and the interesting algorithmic properties of FVS can be extended to problems on this class? Toward this we define a graph class, F1, that contains all graphs where each connected component can be transformed into a forest by deleting at most l edges. A graph in the class F1 is known as pseudoforest in the literature and we call a graph in Fl an l-pseudoforest. We study the problem of deleting k vertices to get into Fl, l-PSEUDOFOREST DELETION, in the realm of parameterized complexity. We show that l-PSEUDOFOREST DELETION admits an algorithm with running time clknO(1) and admits a kernel of size f(l)k2. Thus, for every fixed l we have a kernel of size O(k2). That is, we get a uniform polynomial kernel for l-pseudoforest Deletion. Our algorithms and uniform kernels involve the use of the expansion lemma and protrusion machinery. [ABSTRACT FROM AUTHOR]

The b-chromatic number of a graph G , χ b ( G ) , is the largest integer k such that G has a k -vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the b- Chromatic Number problem, the objective is to decide whether χ b ( G ) ≥ k . Testing whether χ b ( G ) = Δ ( G ) + 1 , where Δ ( G ) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvíl, Tuza and Voigt, WG 2002). We show that b- Chromatic Number is W[1]-hard when parameterized by k , resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k = Δ ( G ) + 1 , we design an algorithm for b- Chromatic Number running in time 2 O ( k 2 log ⁡ k ) n O ( 1 ) . Finally, we show that b- Chromatic Number for an n -vertex graph can be solved in time O ( 3 n n 4 log ⁡ n ) . [ABSTRACT FROM AUTHOR]

The input to the NP-hard POINT LINE COVER problem (PLC) consists of a set P of n points on the plane and a positive integer k; the question is whether there exists a set of at most k lines that pass through all points in P. By straightforward reduction rules, one can efficiently reduce any input to one with at most k2 points. We show that this easy reduction is already essentially tight under standard assumptions. More precisely, unless the polynomial hierarchy collapses to its third level, for any ε > 0, there is no polynomial-time algorithm that reduces every instance (P, k) of PLC to an equivalent instance with O(k2-ε) points. This answers, in the negative, an open problem posed by Lokshtanov [2009]. Our proof uses the notion of a kernel from parameterized complexity, and the machinery for deriving lower bounds on the size of kernels developed by Dell and van Melkebeek [2010, 2014]. It has two main ingredients: We first show, by reduction from VERTEX COVER, that--unless the polynomial hierarchy collapses--PLC has no kernel of total size O(k2-ε) bits. This does not directly imply the claimed lower bound on the number of points, since the best-known polynomialtime encoding of a PLC instance with n points requires ω(n²) bits. To get around this hurdle, we build on work of Alon [1986] and devise an oracle communication protocol of cost O(nlog n) for PLC. This protocol, together with the lower bound on the total size (which also holds for such protocols), yields the stated lower bound on the number of points. While a number of essentially tight polynomial lower bounds on total sizes of kernels are known, our result is--to the best of our knowledge--the first to show a nontrivial lower bound for structural/secondary parameters. It is also the first example of a lower bound for kernelization that makes use of the full power of the oracle communication protocol lower bounds that can be obtained from the work of Dell and van Melkebeek. We combine the main abstract ideas of our proof to derive a general recipe that could be used to obtain such lower bounds for other problems with unknown or insufficiently strong encodings. [ABSTRACT FROM AUTHOR]

We investigate the effect of certain natural connectivity constraints on the parameterized complexity of two fundamental graph covering problems, namely Vertex Cover and Edge Cover . Specifically, we impose the additional requirement that each connected component of a solution have at least t vertices (resp. edges from the solution) for a fixed positive integer t , and call the problem t - Total Vertex Cover (resp. t - Total Edge Cover ). In both cases the parameter k is the size of the solution. We show that • both problems remain fixed-parameter tractable with these restrictions, with running times of the form O ⋆ ( c k ) for some constant c > 0 in each case, where the O ⋆ notation hides polynomial factors; • for each fixed t ≥ 2 , t - Total Vertex Cover has no polynomial kernel unless CoNP ⊆ NP / poly ; • for each fixed t ≥ 2 , t - Total Edge Cover has a linear vertex kernel of size t + 1 t k . These results significantly improve earlier work on these problems. We illustrate the utility of the technique used to solve t - Total Vertex Cover , by applying it to derive an O ⋆ ( c k ) -time FPT algorithm for the t - Total Edge Dominating Set problem. Our no-poly-kernel result for t - Total Vertex Cover , and the known NP-hardness result for t - Total Edge Cover , are in stark contrast to the fact that Vertex Cover has a 2 k vertex kernel, and that Edge Cover is solvable in polynomial time. This illustrates how even the slightest connectivity requirement results in a drastic change in the tractability of problems—the curse of connectivity! [ABSTRACT FROM AUTHOR]