Search

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]

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]

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T - S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here, the input is a tournament T and a weight function w: V (T) → N, and the task is to find a feedback vertex set S in T minimizing w(S) = Σ ν ∈S w(ν). Rounding optimal solutions to the natural LPrelaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2.5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this article, we give the first polynomial time factor 2-approximation algorithm for this problem. Assuming the Unique Games Conjecture, this is the best possible approximation ratio achievable in polynomial time. [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 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 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]

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]

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]

A matrix M is said to be k-anonymous if for each row r in M there are at least k − 1 other rows in M which are identical to r. The NP-hard k- Anonymity problem asks, given an n × m-matrix M over a fixed alphabet and an integer s > 0, whether M can be made k-anonymous by suppressing (blanking out) at most s entries. Complementing previous work, we introduce two new 'data-driven' parameterizations for k- Anonymity-the number t of different input rows and the number t of different output rows-both modeling aspects of data homogeneity. We show that k- Anonymity is fixed-parameter tractable for the parameter t, and that it is NP-hard even for t = 2 and alphabet size four. Notably, our fixed-parameter tractability result implies that k- Anonymity can be solved in linear time when t is a constant. Our computational hardness results also extend to the related privacy problems p- Sensitivity and ℓ- Diversity, while our fixed-parameter tractability results extend to p- Sensitivity and the usage of domain generalization hierarchies, where the entries are replaced by more general data instead of being completely suppressed. [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]

We show that for every fixed j ≥ i ≥ 1, the k-DOMINATING SET problem restricted to graphs that do not have Ki,j (the complete bipartite graph on (i + j) vertices, where the two parts have i and j vertices, respectively) as a subgraph is fixed parameter tractable (FPT) and has a polynomial kernel. We describe a polynomial-time algorithm that, given a Ki,j-free graph G and a nonnegative integer k, constructs a graph H (the "kernel") and an integer k' such that (1) G has a dominating set of size at most k if and only if H has a dominating set of size at most k', (2) H has O((j+1)i+1ki2) vertices, and (3) k' = O((j+1)i+1ki2). Since d-degenerate graphs do not have Kd+1,d+1 as a subgraph, this immediately yields a polynomial kernel on O((d+2)d+2k(d+1)2) vertices for the k-DOMINATING SET problem on d-degenerate graphs, solving an open problem posed by Alon and Gutner [Alon and Gutner 2008; Gutner 2009]. The most general class of graphs for which a polynomial kernel was previously known for κ-DOMINATING SET is the class of Kh-topological-minor-free graphs [Gutner 2009]. Graphs of bounded degeneracy are the most general class of graphs for which an FPT algorithm was previously known for this problem. Kh-topologicalminor- free graphs are Ki,j-free for suitable values of i, j (but not vice-versa), and so our results show that κ-DOMINATING SET has both FPT algorithms and polynomial kernels in strictly more general classes of graphs. Using the same techniques, we also obtain an O(jki) vertex-kernel for the k-INDEPENDENT DOMINATING SET problem on Ki,j-free graphs. [ABSTRACT FROM AUTHOR]

We study the recently introduced Connected Feedback Vertex Set ( CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=( V, E) and an integer k, decide whether there exists F⊆ V, | F|≤ k, such that G[ V∖ F] is a forest and G[ F] is connected. We show that Connected Feedback Vertex Set can be solved in time O(2 n) on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems. [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]