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.
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.
Sequences characterizing k-Trees
A non-decreasing sequence of n integers is the degree sequence of a 1-tree (i.e., an ordinary tree) on n vertices if and only if there are least two 1's in the sequence, and the sum of the elements is 2(n - 1). We generalize this result in the following ways. First, a natural generalization of this statement is a necessary condition for k-trees, and we show that it is not sufficient for any k > 1. Second, we identify non-trivial sufficient conditions for the degree sequences of 2-trees. We also show that these sufficient conditions are almost necessary using bounds on the partition function p(n) and probabilistic methods. Third, we generalize the characterization of degrees of 1-trees in an elegant and counter-intuitive way to yield integer sequences that characterize k-trees, for all k. © Springer-Verlag Berlin Heidelberg 2006.
On the arrangement of cliques in chordal graphs with respect to the cuts
A cut (A, B) (where B = V - A) in a graph G(V, E) is called internal, iff there exists a node x in A which is not adjacent to any node in B and there exists a node y ε B such that it is not adjacent to any node in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with κ(G) + 1 nodes (where κ(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, for each i, 0 ≤ i ≤ κ(G) + 1, there exists a clique Ki such that |Ki| = κ(G) + 1, |A ∩ Ki| = i and |B ∩ Ki| = κ(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Ω(k2), where κ(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least κ(G)(κ(G)+1)/2, where κ(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to κ(G). This result is tight. © Springer-Verlag Berlin Heidelberg 2004.
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.
Exact algorithms for allocation problems
We design new exact exponential time algorithms for the well known NP-hard allocation problems- Makespan minimization, the Santa Claus problem (with and without capacity constraints) and the Bin packing problem. These problems are very well-studied in the paradigm of approximation algorithms. However the best known exact, exponential-time algorithms for all of the above problems has complexity of O*(3m) [6], where m is the number of jobs except for Bin Packing which has a O*(2m) inclusion exclusion based algorithm (where m is the number of items) [8]. We introduce a new dynamic programming formulation which helps solve Makespan minimization and Santa Claus problem more efficiently in O*(2m) time and gives a completely different approach with the same time complexity in case of Bin Packing. In addition, Jansen et al. [6] showed that unless the ETH (exponential time hypothesis) is false, there is no exact algorithm that runs in time 2o(m).
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.
Data Structures for Incremental Interval Coloring
We consider the dynamic graph coloring problem restricted to the class of interval graphs. At each update step the algorithm is presented with an interval to be colored, or a previously colored interval to delete. The goal of the algorithm is to efficiently maintain a proper coloring of the intervals with as few colors as possible by an online algorithm. In the incremental model, each update step presents the algorithm with an interval to be colored. The problem is closely connected to the online vertex coloring problem of interval graphs for which the Kierstead-Trotter (KT) algorithm achieves the best possible competitive ratio. We first show that a sub-quadratic time direct implementation of the KT-algorithm is unlikely to exist conditioned on the correctness of the Online Boolean Matrix Vector multiplication conjecture due to Henzinger et al. [9]. We then design an incremental algorithm that is subtly different from the KT-algorithm and uses at most 3ω − 2 colors, where ω is the maximum clique in the interval graph associated with the set of intervals. Our incremental data structure maintains a proper coloring in amortized O(log n+Δ) update time where n is the total number of intervals inserted and Δ is the maximum degree of a vertex in the interval graph.
Facility location on planar graphs with unreliable links
Hassin et al. [9] consider the Max-Exp-Cover-R problem to study the facility location problem on a graph in the presence of unreliable links when the link failure is according to the Linear Reliability Order (LRO) model. They showed that for unbounded R the problem is polynomial time solvable and for R = 1 and planar graphs the problem is NP-Complete. In this paper, we study the Max-Exp-Cover-1 problem under the LRO edge failure model. We obtain a fixed parameter tractable algorithm for Max-Exp-Cover-1 problem for bounded treewidth graphs, parameterized by the treewidth. We extend the Baker’s technique (Baker, J. ACM 1994) to obtain PTAS for Max-Exp-Cover-1 problem under the LRO model on planar graphs. We observe that the coverage function of the Max-Exp-Cover-R problem is submodular and the problem admits a (1 - 1/e)-approximation for any failure model in which the expected coverage of a set by another set can be computed in polynomial time.