Advertisement
Published in:
2010 | OriginalPaper | Chapter
Unbalanced Graph Partitioning
Authors : Angsheng Li, Peng Zhang
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We investigate the unbalanced cut problems. A cut (
A
,
B
) is called
unbalanced
if the size of its smaller side is at most
k
(called
k
-size) or exactly
k
(called E
k
-size), where
k
is an input parameter. An
s
-
t
cut (
A
,
B
) is called unbalanced if its
s
-side is of
k
-size or E
k
-size. We consider three types of unbalanced cut problems, in which the quality of a cut is measured with respect to the capacity, the sparsity, and the conductance, respectively.
We show that even if the input graph is restricted to be a tree, the E
k
-Sparsest Cut problem (to find an E
k
-size cut with the minimum sparsity) is still
NP
-hard. We give a bicriteria approximation algorithm for the
k
-Sparsest Cut problem (to find a
k
-size cut with the minimum sparsity), which outputs a cut whose sparsity is at most
O
(log
n
) times the optimum and whose smaller side has size at most
O
(log
n
)
k
. As a consequence, this leads to a (
O
(log
n
),
O
(log
n
))-approximation algorithm for the Min
k
-Conductance problem (to find a
k
-size cut with the minimum conductance). We also prove that the Min
k
-Size
s
-
t
Cut problem is
NP
-hard and give an
O
(log
n
)-approximation algorithm for it.