Clique partitioning of interval graphs with submodular costs on the cliques
Given a graph and a “cost function” (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of 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 is an interval graph and 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...