A Linear-Time Algorithm to Find a Separator in a Graph Excluding a Minor
Author
Reed, B; Wood, DRDate
2009-10-01Source Title
ACM Transactions on AlgorithmsPublisher
ASSOC COMPUTING MACHINERYUniversity of Melbourne Author/s
WOOD, DAVIDAffiliation
Mathematics and StatisticsMetadata
Show full item recordDocument Type
Journal ArticleCitations
Reed, B. & Wood, D. R. (2009). A Linear-Time Algorithm to Find a Separator in a Graph Excluding a Minor. ACM TRANSACTIONS ON ALGORITHMS, 5 (4), https://doi.org/10.1145/1597036.1597043.Access Status
This item is currently not available from this repositoryAbstract
<jats:p>
Let
<jats:italic>G</jats:italic>
be an
<jats:italic>n</jats:italic>
-vertex
<jats:italic>m</jats:italic>
-edge graph with weighted vertices. A pair of vertex sets
<jats:italic>A</jats:italic>
,
<jats:italic>B</jats:italic>
⊆
<jats:italic>V</jats:italic>
(
<jats:italic>G</jats:italic>
) is a 2/3
<jats:italic>-separation</jats:italic>
of
<jats:italic>order</jats:italic>
|
<jats:italic>A</jats:italic>
∩
<jats:italic>B</jats:italic>
| if
<jats:italic>A</jats:italic>
∪
<jats:italic>B</jats:italic>
=
<jats:italic>V</jats:italic>
(
<jats:italic>G</jats:italic>
), there is no edge between
<jats:italic>A</jats:italic>
−
<jats:italic>B</jats:italic>
and
<jats:italic>B</jats:italic>
−
<jats:italic>A</jats:italic>
, and both
<jats:italic>A</jats:italic>
−
<jats:italic>B</jats:italic>
and
<jats:italic>B</jats:italic>
−
<jats:italic>A</jats:italic>
have weight at most 2/3 the total weight of
<jats:italic>G</jats:italic>
. Let ℓ ∈ Z
<jats:sup>+</jats:sup>
be fixed. Alon et al. [1990] presented an algorithm that in
<jats:italic>O</jats:italic>
(
<jats:italic>n</jats:italic>
<jats:sup>1/2</jats:sup>
<jats:italic>m</jats:italic>
) time, outputs either a
<jats:italic>K</jats:italic>
<jats:sub>ℓ</jats:sub>
-minor of
<jats:italic>G</jats:italic>
, or a separation of
<jats:italic>G</jats:italic>
of order
<jats:italic>O</jats:italic>
(
<jats:italic>n</jats:italic>
<jats:sup>1/2</jats:sup>
). Whether there is a
<jats:italic>O</jats:italic>
(
<jats:italic>n</jats:italic>
+
<jats:italic>m</jats:italic>
)-time algorithm for this theorem was left as an open problem. In this article, we obtain a
<jats:italic>O</jats:italic>
(
<jats:italic>n</jats:italic>
+
<jats:italic>m</jats:italic>
)-time algorithm at the expense of a
<jats:italic>O</jats:italic>
(
<jats:italic>n</jats:italic>
<jats:sup>2/3</jats:sup>
) separator. Moreover, our algorithm exhibits a trade-off between time complexity and the order of the separator. In particular, for any given ϵ ∈ [0,1/2], our algorithm outputs either a
<jats:italic>K</jats:italic>
<jats:sub>ℓ</jats:sub>
-minor of
<jats:italic>G</jats:italic>
, or a separation of
<jats:italic>G</jats:italic>
with order
<jats:italic>O</jats:italic>
(
<jats:italic>n</jats:italic>
<jats:sup>(2−ϵ)/3</jats:sup>
in
<jats:italic>O</jats:italic>
(
<jats:italic>n</jats:italic>
<jats:sup>1 + ϵ</jats:sup>
+
<jats:italic>m</jats:italic>
) time. As an application we give a fast approximation algorithm for finding an independent set in a graph with no
<jats:italic>K</jats:italic>
ℓ-minor.
</jats:p>
Keywords
Computation Theory and MathematicsExport Reference in RIS Format
Endnote
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
Refworks
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References