The minimum k-way cut problem
- Series
- Graph Theory Seminar
- Time
- Friday, June 11, 2010 - 15:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 254
- Speaker
- Ken-ichi Kawarabayashi – National Institute of Informatics, Tokyo
We consider a the minimum k-way cut problem for unweighted graphs
with a bound $s$ on the number of cut edges allowed. Thus we seek to remove as
few
edges as possible so as to split a graph into k components, or
report that this requires cutting more than s edges. We show that this
problem is fixed-parameter tractable (FPT) in s.
More precisely, for s=O(1), our algorithm runs in quadratic time
while we have a different linear time algorithm
for planar graphs and bounded genus graphs.
Our result solves some open problems and contrasts W[1] hardness (no
FPT unless P=NP) of related formulations of the k-way cut
problem. Without the size bound, Downey et al.~[2003] proved that
the minimum k-way cut problem is W[1] hard in k even for simple
unweighted graphs.
A simple reduction shows that vertex cuts are at least as hard as edge cuts,
so the minimum k-way vertex cut is also W[1] hard in terms of
k. Marx [2004] proved that finding a minimum
k-way vertex cut of size s is also W[1] hard in s. Marx asked about
FPT status with edge cuts, which is what we resolve here.
We also survey approximation results for the minimum k-way cut problem, and
conclude
some open problems. Joint work with Mikkel Thorup (AT&T Research).