On minimum average stretch spanning trees in polygonal 2-trees
A spanning tree of an unweighted graph is a minimum average stretch spanning tree if it minimizes the ratio of sum of the distances in the tree between the end vertices of the graph edges and the number of graph edges. We consider the problem of computing a minimum average stretch spanning tree in polygonal 2-trees, a super class of 2-connected outerplanar graphs. For a polygonal 2-tree on n vertices, we present an algorithm to compute a minimum average stretch spanning tree in O(n logn) time. This also finds a minimum fundamental cycle basis in polygonal 2-trees. © 2014 Springer International Publishing Switzerland.
Approximate distance oracle in o(N2) time and o(n) space for chordal graphs
We preprocess a given unweighted chordal graph G on n vertices in O(n2) time to build a data structure of O(n) size such that any subsequent distance query can be answered in constant time with a bounded constant factor error. In particular, for each pair of vertices ui, uj ∈ V (G), 1 ≤ i, j ≤ n, we take constant time to output a distance value dij ≤ 2dG(ui, uj) + 8 using our data structure, where dG is the distance between ui and uj in G. In contrast, for the closely related APSP problem on chordal graphs, the current best algorithm runs in O(n2.373) time. Our improvement comes from a relationship that we discover between the graph distance and minimum hitting sets of cliques on certain paths in a clique tree associated with a chordal graph. We design an efficient data structure which additively approximates (error of +3) these minimum hitting sets of cliques for all the paths in the clique tree. This data structure is then integrated with an efficient data structure which answers LCA queries in rooted trees to yield our distance oracle for the given chordal graph.
A refined analysis of online path coloring in trees
Our results are on the online version of path coloring in trees where each request is a path to be colored online, and two paths that share an edge must get different colors. For each T, we come up with a hierarchical partitioning of its edges with a minimum number of parts, denoted by h(T), and design an O(h(T))-competitive online algorithm. We then use the lower bound technique of Bartal and Leonardi [1] along with a structural property of the hierarchical partitioning, to show a lower bound of Ω(h(T)/log(4h(T))) for each tree T on the competitive ratio of any deterministic online algorithm for the problem. This gives us an insight into online coloring of paths on each tree T, whereas the current tight lower bound results are known only for special trees like paths and complete binary trees.
Approximability of Clique Transversal in Perfect Graphs
Given an undirected simple graph G, a set of vertices is an r-clique transversal if it has at least one vertex from every r-clique. Such sets generalize vertex covers as a vertex cover is a 2-clique transversal. Perfect graphs are a well-studied class of graphs on which a minimum weight vertex cover can be obtained in polynomial time. Further, an r-clique transversal in a perfect graph is also a set of vertices whose deletion results in an (r- 1) -colorable graph. In this work, we study the problem of finding a minimum weight r-clique transversal in a perfect graph. This problem is known to be NP-hard for r≥ 3 and admits a straightforward r-approximation algorithm. We describe two different r+12-approximation algorithms for the problem. Both the algorithms are based on (different) linear programming relaxations. The first algorithm employs the primal–dual method while the second uses rounding based on a threshold value. We also show that the problem is APX-hard and describe hardness results in the context of parameterized algorithms and kernelization.
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.
LP can be a cure for Parameterized Problems
We investigate the parameterized complexity of VERTEX COVER parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that even the most straightforward branching algorithm (after some preprocessing) results in an O*(2.6181r) algorithm for the problem where r is the excess of the vertex cover size over the LP optimum. We write O *(f(k)) for a time complexity of the form O(f(k)n O(1)), where f(k) grows exponentially with k. Then, using known and new reductions, we give O*(2.6181k) algorithms for the parameterized versions of ABOVE GUARANTEE VERTEX COVER, ODD CYCLE TRANSVERSAL, SPLIT VERTEX DELETION and ALMOST 2-SAT, and an O *(1.6181k) algorithm for KON̈IG VERTEX DELETION, VERTEX COVER PARAM BY OCT and VERTEX COVER PARAM BY KVD. These algorithms significantly improve the best known bounds for these problems. The notable improvement is the bound for ODD CYCLE TRANSVERSAL for which this is the first major improvement after the first algorithm that showed it fixed-parameter tractable in 2003. We also observe that using our algorithm, one can obtain a simple kernel for the classical vertex cover problem with at most 2k - O(log k) vertices. © N.S. Narayanaswamy, V. Raman, M.S. Ramanujan, and S. Saurabh.
Hitting set for hypergraphs of low VC-dimension
We study the complexity of the Hitting Set problem in set systems (hypergraphs) that avoid certain sub-structures. In particular, we characterize the classical and parameterized complexity of the problem when the Vapnik-Chervonenkis dimension (VC-dimension) of the input is small. VC-dimension is a natural measure of complexity of set systems. Several tractable instances of Hitting Set with a geometric or graph-theoretical flavor are known to have low VC-dimension. In set systems of bounded VC-dimension, Hitting Set is known to admit efficient and almost optimal approximation algorithms (Brönnimann and Goodrich, 1995; Even, Rawitz, and Shahar, 2005; Agarwal and Pan, 2014). In contrast to these approximation-results, a low VC-dimension does not necessarily imply tractability in the parameterized sense. In fact, we show that Hitting Set is W[1]-hard already on inputs with VC-dimension 2, even if the VC-dimension of the dual set system is also 2. Thus, Hitting Set is very unlikely to be fixed-parameter tractable even in this arguably simple case. This answers an open question raised by King in 2010. For set systems whose (primal or dual) VC-dimension is 1, we show that Hitting Set is solvable in polynomial time. To bridge the gap in complexity between the classes of inputs with VC-dimension 1 and 2, we use a measure that is more fine-grained than VC-dimension. In terms of this measure, we identify a sharp threshold where the complexity of Hitting Set transitions from polynomial-time-solvable to NP-hard. The tractable class that lies just under the threshold is a generalization of Edge Cover, and thus extends the domain of polynomial-time tractability of Hitting Set.
Approximation and exact algorithms for special cases of connected f-factors
Given an edge weighted undirected graph G = (V,E) with |V| = n, and a function f: V → N, we consider the problem of finding a connected f-factor in G. In particular, for each constant c ≥ 2, we consider the case when f(v) ≥ n/c, for all v in V. We characterize the set of graphs that have a connected f-factor for f(v) ≥ n/3, for every v in V, and this gives polynomial time algorithm for the decision version of the problem. Extending the techniques we solve the minimization version. On the class of instances where the edge weights in G form a metric and f(v) ≥ n/c, c is a fixed value greater than 3, we give a PTAS. For each c ≥ 3 and ϵ > 0, our algorithm takes as input a metric weighted undirected graph G and a function f: V → N such that f(v) ≥ n/c, for every v in V, and computes a (1 + ϵ)-approximation to the minimum weighted connected f-factor in polynomial time.
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.