Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2009-012 (April 13, 2009)

Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems
by Kazumasa Okutomo, Takuro Fukunaga, Hiroshi Nagamochi

pdf File

The submodular system $k$-partition problem is a problem of partitioning a given finite set $V$ into $k$ non-empty subsets $V_1,V_2, \ldots,V_k$ so that $\sum_{i=1}^k f(V_i)$ is minimized where $f$ is a non-negative submodular function on $V$, and $k$ is a fixed constant. This problem contains the hypergraph $k$-cut problem. In this paper, we design the first exact algorithm for $k=3$, a 1.5-approximation algorithm for $k=4$, and a 2-approximation algorithm for $k=5$. We also show that the approximation algorithms achieve 4/3-approximation for the hypergraph 4-cut problem and 5/3-approximation for the hypergraph 5-cut problem.