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]

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]

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]

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]