Parameterized algorithms for (r, l)-Partization
We consider the (r, l)-Partization problem of finding a set of at most k vertices whose deletion results in a graph that can be partitioned into r independent sets and l cliques. Restricted to perfect graphs and split graphs, we describe sequacious fixed-parameter tractability results for (r, 0)-Partization, parameterized by k and r. For (r, l)-Partization where r+l = 2, we describe an O*(2k) algorithm for perfect graphs. We then study the parameterized complexity hardness of a generalization of the Above Guarantee Vertex Cover by a reduction from (r, l)-Partization.
Generalized above guarantee vertex cover and r-partization
Vertex cover and odd cycle transversal are minimum cardinality sets of vertices of a graph whose deletion makes the resultant graph 1-colorable and 2-colorable, respectively. As a natural generalization of these well-studied problems, we consider the Graph r-Partization problem of finding a minimum cardinality set of vertices whose deletion makes the graph r-colorable. We explore further connections to Vertex Cover by introducing Generalized Above Guarantee Vertex Cover, a variant of Vertex Cover defined as: Given a graph G, a clique cover K of G and a non-negative integer k, does G have a vertex cover of size at most k +Σ CεK(
FPT algorithms for consecutive ones submatrix problems
A binary matrix M has the Consecutive Ones Property (COP) if there exists a permutation of columns that arranges the ones consecutively in all the rows. We consider the parameterized complexity of d-COS-R (Consecutive Ones Submatrix by Row deletions) problem [8]: Given a matrix M and a positive integer d, decide whether there exists a set of at most d rows of M whose deletion results in a matrix with the COP. The closely related Interval Deletion problem has recently been shown to be FPT [5]. In this work, we describe a recursive depth-bounded search tree algorithm in which the problems at the leaf-level of the recursion tree are solved as instances of Interval Deletion. Therefore, we show that d-COS-R is fixed-parameter tractable and has the current best run-time of O*(10d), which is associated with the Interval Deletion problem. We then consider a closely related optimization problem, called Min-ICPIA, and prove that it is computationally equivalent to the Vertex Cover problem. © 2013 Springer International Publishing.
Another disjoint compression algorithm for odd cycle transversal
Given a graph G and an odd cycle transversal T, we describe an elegant O* (2|T|) algorithm for determining whether G has a smaller odd cycle transversal that is disjoint from T. We believe that our algorithm, based on a reduction to VERTEX Cover, is conceptually simpler than the known algorithms for the problem and refines the understanding of the relationship between ODD CYCLE TRANSVERSAL and VERTEX COVER. © 2013 Elsevierc B.V. All rights reserved.
Solving min ones 2-sat as fast as vertex cover
The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem min ones 2-sat. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from min ones 2-sat to vertex cover without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k-clogk-variable kernel subsuming (or, in the case of kernels, improving) the results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover. Finally we show that the optimum value of the LP relaxation of the min ones 2-sat and that of the corresponding vertex cover are the same. This implies that the (recent) results of vertex cover version parameterized above the optimum value of the LP relaxation of vertex cover carry over to the min ones 2-sat version parameterized above the optimum of the LP relaxation of min ones 2-sat. © 2013 Elsevier B.V.
Obtaining Matrices with the Consecutive Ones Property by Row Deletions
A binary matrix M has the Consecutive Ones Property (COP) if there exists a permutation of columns that arranges the ones consecutively in all the rows. We consider the parameterized complexity of d-COS-R (Consecutive Ones Submatrix by Row deletions) problem [9]: Given a matrix M and a positive integer d, decide whether there exists a set of at most d rows of M whose deletion results in a matrix with the COP. The closely related Interval Deletion problem has recently been shown to be FPT [6]. We show that d-COS-R is fixed-parameter tractable and has the current best run-time of O∗(10d), which is associated with the Interval Deletion problem. We also introduce a closely related optimization problem called Min-ICPSA: For a finite sized universe U the input consists of a family of n pairs of sets S = {(Ai, Bi) | Ai, Bi ⊆ u, 1 ≤ i ≤ n}; the aim is to find a minimum number of pairs of sets to discard from S such that for each one of the remaining pairs, say (Ak, BAk), |A|k= |B|k and for any two of the remaining pairs, indexed by 1 ≤ j ≠ k ≤ n, |Aj ∩ Ak| = |Bj ∩ Bk|. We show that Min-ICPSA is computationally equivalent to the Vertex Cover problem. We also show that it is at least as hard as the Hamilton Path problem in undirected graphs, even when each |A|.k = 2, 1 ≤ k ≤ n.
Hardness of subgraph and supergraph problems in c-tournaments
Problems like the directed feedback vertex set problem have much better algorithms in tournaments when compared to general graphs. This motivates us to study a natural generalization of tournaments, named c-tournaments, and see if the structural properties of these graphs are helpful in obtaining similar algorithms. c-tournaments are simple digraphs which have directed paths of length at most c≥1 between all pairs of vertices. We study the complexity of feedback vertex set and r-dominating set in c-tournaments. We also present hardness results on some graph editing problems involving c-tournaments. © 2011 Elsevier B.V. All rights reserved.