Clique partitioning of interval graphs with submodular costs on the cliques

Dion Gijswijt, Vincent Jost, Maurice Queyranne


Given a graph G=(V,E) and a "cost function" f: 2V -> R (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of V(G) of minimum cost. Here, the cost of a partition is the sum of the costs of the cliques in the partition. We provide a polynomial time dynamic program for the case where G is an interval graph and f belongs to a subclass of submodular set functions, which we call "value-polymatroidal". This provides a common solution for various generalizations of the coloring problem in co-interval graphs such as max-coloring, "Greene-Kleitman's dual", probabilist coloring and chromatic entropy. In the last two cases, this is the first polytime algorithm for co-interval graphs. In contrast, NP-hardness of related problems is discussed. We also describe an ILP formulation for [PCliqW] which gives a common polyhedral framework to express min-max relations such as \bchrom=\alpha for perfect graphs and the polymatroid intersection theorem. This approach allows to provide a min-max formula for [PCliqW] if G is the line-graph of a bipartite graph and f is submodular. However, this approach fails to provide a min-max relation for [PCliqW] if G is an interval graph and f is value-polymatroidal.

Bibtex entry:

AUTHOR = {Gijswijt, Dion and Jost, Vincent and Queyranne, Maurice},
TITLE = {Clique partitioning of interval graphs with submodular costs on the cliques},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2006},
NUMBER = {TR-2006-14}

Last modification: 29.12.2020. Please email your comments to Tamás Király!