Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time

Authors Ken-ichi Kawarabayashi, Zhentao Li, Bruce Reed

Publication date 25 September 2015

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: In this paper we show how to combine two algorithmic techniques to obtain linear time algorithms for various optimization problems on graphs, and present a subroutine which will be useful in doing so. The first technique is iterative shrinking. In the first phase of an iterative shrinking algorithm, we construct a sequence of graphs of decreasing size

G_{1}, l d o t s, G_{e} l l

where

G_{1}

is the initial input,

G_{e} l l

is a graph on which the problem is easy, and

G_{i}

is obtained from

G_{i + 1}

via some shrinking algorithm. In the second phase we work through the sequence in reverse, repeatedly constructing a solution for a graph from the solution for its successor. In an iterative compaction algorithm, we insist that the graphs decrease by a constant fraction of the entire graph. Another approach to solving optimization problems is to exploit the structural properties implied by the connectivity of the input graph. This approach can be used on graphs which are not highly connected by decomposing an input graph into its highly connected pieces, solving subproblems on these specially structured pieces and then combining their solutions. We combine these two techniques by developing compaction algorithms which when applied to the highly connected pieces preserve their connectivity properties. The structural properties this connectivity implies can be helpful both in finding further compactions in later iterations and when we are manipulating solutions in the second phase of an iterative compaction algorithm. To illustrate how this compaction algorithm can be used as a subroutine, we present a linear time algorithm that given four vertices

s_{1}, s_{2}, t_{1}, t_{2}

of a graph

G

, either finds a pair of disjoint paths

P_{1}

and

P_{2}

of

G

such that

P_{i}

has endpoints

s_{i}

and

t_{i}

, or returns a planar embedding of an auxiliary graph which shows that no such pair exists.

This page was built for publication: Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6265801)