A unified framework for bi(tri)connectivity and chordal augmentation
For a connected non-complete graph, a vertex separator is a subset of vertices whose deletion increases the number of connected components and the vertex connectivity of the graph refers to the size of a minimum vertex separator. A graph with the vertex connectivity k is said to be k-vertex connected. Given a k-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (k + 1)-vertex connected. In this paper, we report our study on connectivity augmentation in 1-connected graphs, 2-connected graphs, and k-connected chordal graphs. We first represent the graph under consideration using a "tree-like" graph. This tree is unique and explicitly captures the connectivity information of the graph. Using this tree, our proposed data structure maintains the set of equivalence classes based on an equivalence relation on the set of leaves of the tree. This partition determines a set of edges to be augmented to increase the connectivity of the graph by one. Based on our data structure, we present a new combinatorial analysis and an elegant proof of correctness of our linear-time algorithm for an optimum connectivity augmentation. The novelty is in the data structure which is a unified framework for all three augmentations. As far as the run-time analysis is concerned, given the associated tree, our approach yields an augmentation set in linear time. © 2013 World Scientific Publishing Company.
Connected (s; t)-vertex separator parameterized by chordality
We investigate the complexity of _nding a minimum connected (s; t)-vertex separator ((s; t)-CVS) and present an interesting chordality di-chotomy: we show that (s; t)-CVS is NP-complete on graphs of chordal-ity at least 5 and present a polynomial-time algorithm for (s; t)-CVS on chordality 4 graphs. Further, we show that (s; t)-CVS is unlikely to have δlog2-∊n-approximation algorithm, for any ∊ > 0 and for some δ > 0, unless NP has quasi-polynomial Las Vegas algorithms. On the positive-side of approximation, we present a [c/2]-approximation algorithm for (s; t)-CVS on graphs with chordality c ≥ 3. Finally, in the parameterized setting, we show that (s; t)-CVS parameterized above the (s; t)-vertex connectivity is W[2]-hard.
A Dirac-type characterization of k-chordal graphs
A graph is k-chordal if it has no induced cycle of length greater than k. We give a new characterization of k-chordal graphs that generalizes the well-known characterization of chordal graphs by Dirac in terms of simplicial vertices and simplicial orderings. © 2013 Elsevier B.V. All rights reserved.
A novel data structure for biconnectivity, triconnectivity, and κ-tree augmentation
For a connected graph, a subset of vertices of least size whose deletion increases the number of connected components is the vertex connectivity of the graph. A graph with vertex connectivity κ is said to be κ-vertex connected. Given a k-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (κ + 1)-vertex connected. In this paper, we report our study of connectivity augmentation in 1-connected graphs, 2-connected graphs, and κ- trees. For a graph, our data structure maintains the set of equivalence classes based on an equivalence relation on the set of leaves of an associated tree. This partition determines a set of edges to be augmented to increase the connectivity of the graph by one. Based on our data structure we present a new combinatorial analysis and an elegant proof of correctness of our linear time algorithm for optimum connectivity augmentation. While this is the first attempt on the study of k-tree augmentation, the study on other two augmentations is reported in the literature. Compared to other augmentations reported in the literature, we avoid recomputation of the associated tree by maintaining the data structure under edge additions. Copyright © 2011, Australian Computer Society, Inc.