Approximation Algorithm for
Graph Augmentation
Samir Khuller
Ramakrishna Thurimella
報告人：蕭志宣 鄭智懷
Outline
Introduction
Related Work
2-approximation
Related Work (History)
Tarjan solve 2 edge-connected augmentation
problem in linear time (1976).
But the graph must be
complete graph.
Related Work (History)
Somebody modified Tarjan’s algorithm which
solves triconnected subgraph in linear time.
In a paper’s conference, it holds for k-
connected.
Minimum k-connected
K connected problem
Minimum subgraph augmentation
weighted unweighted weighted unweighted
Related Work - Guideline
Related Word - Approximation
Edge connectivity augment
1993
Samir Khuller, Ramakrishna Thurimella 2-approximation
2003
Anna Galluccio and Guido Proietti faster 2-approximation
Related Word - Approximation
Vertex connectivity subgraph
1994(2-connected)
Samir Khuller, Uzi Vishkin 5/3-approximation
1994(2-connected)
Garg, Santosh and Singla 3/2-approximation
2001(2-connected)
S. Vempala and A. Vetta 4/3-approximation
Related Word - Approximation
Edge connectivity subgraph
1994(2-connected)
Samir Khuller, Uzi Vishkin 3/2-approximation
1995(k-connected)
Samir Khuller, Balaji Raghavachari 1.85-approximation
2001(2-connected)
J. Cheriyan, A. SebS, Z. Szigeti 17/12-approximation
2001(2-connected)
S. Vempala and A. Vetta 4/3-approximation
2003(2-connected)
Raja Jothi Balaji Raghavachari Subramanian Varadarajan
5/4-approximation
2003(k-connected)
Harold N. Gabow 1.61-approximation
Related Word – Special Case
符合三角不等式
1995 (k vertex connectivity)
Samir Khuller, Balaji Raghavachari some approximation with k
Related Word – Special Case
已知道至少有6k2個vertices求k vertex
connectivity
O(pn=)-approximation algorithm for any > 0 and
k (1 - )n
Related Word – Special Case
已知G是planar graph
1998 (2 edge connected augment problem)
Sergej Fialko, Petra Mutzel 5/3-approximation
2004(2 edge,2 vertex subgraph)
Artur Czumaj, Michelangelo Grigni, Papa Sissokho, Hairong Zhao
PTAS
Related Word – Special Case
已知G是bipartite graph
1998(k-connectivity augment problem)
Jørgen Bang-Jensen, Harold N. Gabow, Tibor Jordán, Zoltán Szigeti
Polynomial time solvable
Related Word – Special Case
Augment problem已知tree是depth first
search tree
2003(2 edge connected augment problem)
Anna Galluccio and Guido Proietti polynomial solvable
Related Word - Randomized
1998
András A. Benczúr, David R. Karger
K-connectivity
K-edge connected
K-vertex connected
Graph Augmentation
Input:
G0=(V,E0), a set Feasible of m weighted
edges on V
Output:
A subset Aug of edges whose addition make
G0 2-connected
The minimum branching
A branching of a directed graph G rooted at a
vertex r is a spanning tree of G such that
each vertex except r has indegree exactly
one and r has indegree zero
The minimum weight branching is a
branching with the least weight.
1
r
2
5
2
3
3 6
6
Algorithm
Step1: pick an arbitrary leaf r and root the
tree G0 at r, and directing all tree edges
toward the root r. Set all tree edges weight to
0.
(undirected tree G0 directed tree T)
Step1
r
Algorithm
Step2: Consider the edges that belong to
G=(V,E) but not belong to G0, for each such
edge (u,v) do
If (u,v) is a back edge
add one directed edge to Ed
If (u,v) is a cross edge
add two directed edges to Ed
Step2
r
Algorithm
Step3: find a minimum weight branching in
Gd rooted at r. For each edge in Ed picked ,
add corresponding edge in E-E0 to Aug.
Step4: Output Aug.
Lemma 1 & Lemma 2
If G is two-edge connected, then directed
graph GD is strongly connected.
If G is two-edge connected, then the edge
connectivity of G0 U Aug is at least 2.
(G0+ Aug is two-edge connected)
Lemma 3
The weight of Aug is less than twice the
optimal augmentation. That is, the algorithm
is a 2-approximation algorithm for
augmentation problem.
Time complexity
O(m+nlogn) (for finding the minimum weight
branching)
