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.
Dynamic data structures for interval coloring
We consider the dynamic graph coloring problem restricted to the class of interval graphs in the incremental and fully dynamic setting. The input consists of a sequence of intervals that are to be either colored, or deleted, if previously colored. For the incremental setting, we consider the well studied optimal online algorithm (KT-algorithm) for interval coloring due to Kierstead and Trotter [1]. We present the following results on the dynamic interval coloring problem. ■ Any direct implementation of the KT-algorithm requires Ω(Δ2) time per interval in the worst case. ■ There exists an incremental algorithm which supports insertion of an interval in amortized O(logn+Δ) time per update and maintains a proper coloring using at most 3ω−2 colors. ■ There exists a fully dynamic algorithm which supports insertion of an interval in O(logn+Δlogω) update time and deletion of an interval in O(Δ2logn) update time in the worst case and maintains a proper coloring using at most 3ω−2 colors. The KT-algorithm crucially uses the maximum clique size in an induced subgraph in the neighborhood of a given vertex. We show that the problem of computing the induced subgraph among the neighbors of a given vertex has the same hardness as the online boolean matrix vector multiplication problem [2]. We show that ■ Any algorithm that computes the induced subgraph among the neighbors of a given vertex requires at least quadratic time unless the OMv conjecture [2] is false. Finally, we obtain the following result on the OMv conjecture. ■ If the matrix and the vectors in the online sequence have the consecutive ones property, then the OMv conjecture [2] is false.
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.
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.
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.
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.
An Invitation to Dynamic Graph Problems: Basics — I
In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. “Classroom” is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part article comprising a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. This article presents the first part of the survey outlining the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part of the survey, we will present a set of techniques to prove upper bounds for dynamic graph problems. In the third part of the survey, we will present a set of techniques to prove lower bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Though classic problems like coloring, matching, independent set, and many more are extensively studied for static graphs, we are still far from obtaining a complete set of lower bounds and upper bounds results for their dynamic graph counterparts. Along with theoretical advances, the techniques used in dynamic graphs need attention from an implementation perspective. The practical potential of these techniques is yet to be explored. We invite undergraduate researchers and programmers to consider an efficient implementation of these techniques through this three-part survey. The survey can also be used to understand the first algorithms for several recent dynamic graph algorithms.
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.
Trade-Offs in Dynamic Coloring for Bipartite and General Graphs
The dynamic coloring problem has gained attention in the recent past. The focus has largely been on obtaining efficient update time algorithms using Δ + 1 or more colors and the trade-offs between update time and query time. Another important parameter in dynamic coloring is the number of recolorings per update which is addressed by the works of Barba et al. in WADS’17, and Solomon and Wein in ESA’18. In SODA’18, Bhattacharya et al. presented a randomized algorithm that uses Δ + 1 colors and achieves amortized O(log Δ) update time. In STACS’20, Henzinger and Peng presented a randomized (Δ + 1) -coloring algorithm with amortized O(1) update time. Independently on arXiv, Bhattacharya et al. also presented a randomized (Δ + 1) -coloring algorithm with amortized O(1) update time. While works of Bhattacharya et al., and Henzinger and Peng are very efficient in terms of update time, they do not address the number of recolorings per update. We bridge this gap by providing efficient update time algorithms with constant number of recolorings. Moreover our algorithm is deterministic as opposed to the works of Bhattacharya et al. in SODA’18, and Henzinger and Peng in STACS’20. Next, we study bipartite graphs which can be optimally colored in the static setting. We show that even in the incremental setting (where edges are added to the graph and no edge can be deleted), there is a bad update sequence which forces the update time to be at least Ω (log n) in the amortized setting and Ω (n) in the worst case. This possibly explains the lack of any results on dynamic coloring specific to bipartite graphs. We circumvent this lower bound by proposing two approaches. Firstly, we allow the use of more than two colors and obtain significantly better update time. Second, we introduce the idea of implicit coloring. If the color of a vertex is explicitly stored in a data structure and updated at end of every update then we call such an algorithm as explicit coloring algorithm. All prior work on dynamic coloring uses explicit coloring algorithms. We show that using implicit coloring we can obtain near constant update time and query time for incremental coloring for bipartite case. We also bound the number of recolorings to near constant. We also show an efficient implicit fully dynamic algorithm for bipartite graphs. All our algorithms are deterministic and use simple data structures. Hence, we believe that our algorithms are of practical importance.
An Invitation to Dynamic Graph Problems: Upper Bounds — II
In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. “Classroom” is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part article consisting of a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. This article presents the second part of the survey consisting of a set of techniques to prove upper bounds for dynamic graph problems. In the first part of the survey, we presented motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the third part of the survey, we will present a set of techniques to prove lower bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Though classic problems like coloring, matching, independent set, and many more are extensively studied for static graphs, we are still far from obtaining a complete set of upper bound results for their dynamic graph counterparts. The upper bound techniques used in dynamic graphs need attention from an implementation perspective, along with theoretical advances. The practical potential of these techniques is yet to be explored. We invite undergraduate researchers and programmers to consider an efficient implementation of these techniques through this three-part survey.