Graphpartitioning: Complexity and Algorithms
Anand Srivastav (Uni Kiel)
Graphpartitioning is the problem, where we wish to partition the set of
nodes of a fitnite graph into a fixed number k of sets such that the
number of crossing edges is minimum. This is a classical problem in
combinatorial optimization with many applications in computer science
and numerical mathematics. The problem is NP-hard, already for k=2 (this
special case is the so called graph bisection problem). The present complexity
status of the problem is on the one hand side that polynomial time
approximation algorithms achieving a constant factor approximation
of the optimum are not known, while on the other hand very efficient
heuristics are used in practise, but proofs ar missing.
We will survey the known facts about algorithms and complexity
of the problem, and will present recent algorithmic progress.
This talk presents joint work with Gerold Jäger.