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]

In the Subset Feedback Vertex Set (Subset-FVS) problem the input is a graph G on n vertices, a subset T of vertices of G called the "terminal" vertices, and an integer k. The task is to determine whether there exists a subset of vertices of cardinality at most k which together intersect all cycles which pass through the terminals. Subset-FVS generalizes several well studied problems including Feedback Vertex Set and Multiway Cut. This problem is known to be NP-Complete, even in split graphs. Cygan et al. (SIAM J Discrete Math 27(1):290–309, 2013) proved that Subset-FVS is fixed parameter tractable (FPT ) in general graphs when parameterized by k. In split graphs a simple observation reduces the problem to an equivalent instance of the 3-Hitting Set problem with the same solution size. This directly implies, for Subset-FVSrestricted to split graphs, (i) an FPT algorithm which solves the problem in O ⋆ (2. 076 k) time (The O ⋆ () notation hides polynomial factors.) (Wahlström in Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. Thesis, Department of Computer and Information Science, Linköpings universitet, 2007), and (ii) a kernel of size O (k 3) . We improve both these results for Subset-FVS on split graphs; we derive (i) a kernel of size O (k 2) which is the best possible unless NP ⊆ coNP / poly , and (ii) an algorithm which solves the problem in time O ∗ (2 k) . Our algorithm, in fact, solves Subset-FVS on the more general class of chordal graphs, also in O ∗ (2 k) time. To the best of our knowledge, the fastest known exact algorithm for Subset-FVS on chordal graphs is based on the 3-Hitting Set algorithm of Fomin et al. (JACM 66(2):8, 2019) which runs in O ∗ (1. 5182 n) time. Applying the results of Fomin et al. (2019) to our FPT algorithm yields two exact exponential-time algorithms for Subset-FVS on chordal graphs: a randomized algorithm which runs in O ∗ (1. 5 n) time, and a deterministic algorithm which runs in O ∗ ((1.5 + ε) n) time for any fixed ε > 0 . [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 Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop kernelization algorithms for the problem on several classes of sparse graphs. We obtain linear kernels on planar graphs, and kernels of size $\mathcal {O}(k^{3/2})$ in graphs excluding some fixed graph as a minor and in graphs of bounded degeneracy. As a byproduct of our results, we obtain approximation algorithms with approximation ratios $\mathcal {O}(\log{k})$ on planar graphs and $\mathcal {O}(\sqrt{k}\log{k})$ on H-minor-free graphs. These results significantly improve the previously known kernelization and approximation results for Minimum Fill-in on sparse graphs. [ABSTRACT FROM AUTHOR]

Abstract: We define strong λ-extendibility as a variant of the notion of λ-extendible properties of graphs (Poljak and Turzík, Discrete Mathematics, 1986). We show that the parameterized APT(Π) problem — given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that and H has at least edges — is fixed-parameter tractable (FPT) for all , for all strongly λ-extendible graph properties Π for which the APT(Π) problem is FPT on graphs which are vertices away from being a graph in which each block is a clique. Our results hold for properties of oriented graphs and graphs with edge labels, generalize the recent result of Crowston et al. (ICALP 2012) on Max-Cut parameterized above the Edwards–Erdős bound, and yield FPT algorithms for several graph problems parameterized above lower bounds. [Copyright &y& Elsevier]

In the Parameterized Connected Dominating Set problem the input consists of a graph G and a positive integer k, and the question is whether there is a set S of at most k vertices in G-a connected dominating set of G-such that (i) S is a dominating set of G, and (ii) the subgraph G[ S] induced by S is connected; the parameter is k. The underlying decision problem is a basic connectivity problem which is long known to be NP-complete, and it has been extensively studied using several algorithmic approaches. Parameterized Connected Dominating Set is W[2]-hard, and therefore it is unlikely (Downey and Fellows, Parameterized Complexity, Springer, ) that the problem has fixed-parameter tractable (FPT) algorithms or polynomial kernels in graphs in general. We investigate the effect of excluding short cycles, as subgraphs, on the kernelization complexity of Parameterized Connected Dominating Set. The girth of a graph G is the length of a shortest cycle in G. It turns out that the Parameterized Connected Dominating Set problem is hard on graphs with small cycles, and becomes progressively easier as the girth increases. More precisely, we obtain the following kernelization landscape: Parameterized Connected Dominating Set While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs. [ABSTRACT FROM AUTHOR]

Abstract: We investigate a generalization of the classical Feedback Vertex Set (FVS) problem from the point of view of parameterized algorithms. Independent Feedback Vertex Set (IFVS) is the “independent” variant of the FVS problem and is defined as follows: given a graph and an integer , decide whether there exists , , such that is a forest and is an independent set; the parameter is . Note that the similarly parameterized version of the FVS problem–where there is no restriction on the graph –has been extensively studied in the literature. The connected variant CFVS–where is required to be connected–has received some attention as well. The FVS problem easily reduces to the IFVS problem in a manner that preserves the solution size, and so any algorithmic result for IFVS directly carries over to FVS. We show that IFVS can be solved in time, where is the number of vertices in the input graph , and obtain a cubic () kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless . [Copyright &y& Elsevier]

Abstract: We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses time and polynomial space to decide whether a claw-free graph on vertices has a dominating set of size at most . Note that this parameterization of Dominating Set is -hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general. The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of -free graphs, which exclude, for some fixed , the complete bipartite graph as a subgraph. For , the class of claw-free graphs and any class of -free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable. We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any , the Dominating Set problem parameterized by the solution size is -hard in graphs that exclude the -claw as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are -hard in these graph classes. Finally, we show that for any , the Clique problem parameterized by solution size, which is -hard on general graphs, is FPT in -claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors. [Copyright &y& Elsevier]

A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with q colors. For fixed q ≥ 2 , we give an O ⋆ (q tw) -time algorithm when the input graph is given together with one of its tree decompositions of width tw . We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is XP parameterized by clique-width. [ABSTRACT FROM AUTHOR]

We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP -complete on general graphs if k is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by k. We round off the work by showing that Diverse Pair of Matchings has a kernel on O (k 2) vertices. [ABSTRACT FROM AUTHOR]

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid M , a weight function ω : E (M) → N , and integers k ≥ 1 , d ≥ 1 . The task is to decide if there is a collection of k bases B 1 , ⋯ , B k of M such that the weight of the symmetric difference of any pair of these bases is at least d . The input to the Weighted Diverse Common Independent Sets problem consists of two matroids M 1 , M 2 defined on the same ground set E , a weight function ω : E → N , and integers k ≥ 1 , d ≥ 1 . The task is to decide if there is a collection of k common independent sets I 1 , ⋯ , I k of M 1 and M 2 such that the weight of the symmetric difference of any pair of these sets is at least d . The input to the Diverse Perfect Matchings problem consists of a graph G and integers k ≥ 1 , d ≥ 1 . The task is to decide if G contains k perfect matchings M 1 , ⋯ , M k such that the symmetric difference of any two of these matchings is at least d . We show that none of these problems can be solved in polynomial time unless P = NP . We derive fixed-parameter tractable ( FPT ) algorithms for all three problems with (k , d) as the parameter, and present a p o l y (k , d) -sized kernel for Weighted Diverse Bases. [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]

Given a graph G and a parameter k ∈ N , the parameterized K 4 - minor cover problem asks whether at most k vertices can be deleted to turn G into a K 4 -minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set , which can also be expressed as Treewidth - t Vertex Deletion problems: t = 0 for Vertex Cover and t = 1 for Feedback Vertex Set . While single-exponential FPT algorithms, i.e. running in 2 O ( k ) ⋅ n O ( 1 ) time, are known for these two latter problems, it was open whether the K 4 - minor cover problem could be solved in single-exponential FPT time. This paper answers this question in the affirmative. Observe that it is known to be unlikely that Treewidth - t Vertex Deletion can be solved in time 2 o ( k ) ⋅ n O ( 1 ) . [ABSTRACT FROM AUTHOR]

In the Undirected Eulerian Edge Deletion problem, we are given an undirected graph and an integer k , and the objective is to delete k edges such that the resultant graph is a connected graph in which all the vertices have even degrees. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion . In this paper, using the technique of computing representative families of co-graphic matroids we design algorithms which solve these problems in time 2 O ( k ) n O ( 1 ) , improving the algorithms by Cygan et al. [Algorithmica, 2014] and affirmatively answer the open problem posed by them. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. [ABSTRACT FROM AUTHOR]

We study a general class of problems called F-DELETION problems. In an F-DELETION problem, we are asked whether a subset of at most k vertices can be deleted from a graph G such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We study the problem parameterized by k, using p-F-DELETION to refer to the parameterized version of the problem. We obtain a number of algorithmic results on the p-F-DELETION problem when F contains a planar graph. We give a linear vertex kernel on graphs excluding t-claw K1,t, the star with t leaves, as an induced subgraph, where t is a fixed integer and an approximation algorithm achieving an approximation ratio of O(log3/2 OPT), where OPT is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F only contains graph θc as a minor for a fixed integer c. The graph θc consists of two vertices connected by c parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as VERTEX COVER, FEEDBACK VERTEX SET, and DIAMOND HITTING SET. The generic kernelization algorithm is based on a nontrivial application of protrusion techniques, previously used only for problems on topological graph classes. [ABSTRACT FROM AUTHOR]

Homogeneous team formation is the task of grouping individuals into teams, each of which consists of members who fulfill the same set of prespecified properties. In this theoretical work, we propose, motivate, and analyze a combinatorial model where, given a matrix over a finite alphabet whose rows correspond to individuals and columns correspond to attributes of individuals, the user specifies lower and upper bounds on team sizes as well as combinations of attributes that have to be homogeneous (that is, identical) for all members of the corresponding teams. Furthermore, the user can define a cost for assigning any individual to a certain team. We show that some special cases of our new model lead to NP-hard problems while others allow for (fixed-parameter) tractability results. For example, the problem is already NP-hard even if (i) there are no lower and upper bounds on the team sizes, (ii) all costs are zero, and (iii) the matrix has only two columns. In contrast, the problem becomes fixed-parameter tractable for the combined parameter 'number of possible teams' and 'number of different individuals', the latter being upper-bounded by the number of rows. [ABSTRACT FROM AUTHOR]

According to the classical Erdős-Pósa theorem, given a positive integer k, every graph G either contains k vertex disjoint cycles or a set of at most [ABSTRACT FROM AUTHOR]

• Parameterized analysis of a general notion of diversity of solutions that suits a large class of combinatorial problems. • Introduction of the notion of dynamic programming core. • Efficient dynamic cores for computing one solution yield efficient dynamic cores for computing a diverse set of solutions. • The notion of diversity of solutions is also compatible with certain notions of kernel. When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which – automatically – converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter. [ABSTRACT FROM AUTHOR]

In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in k + r for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of 'base' solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest. [ABSTRACT FROM AUTHOR]