Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T19:25:52.083Z Has data issue: false hasContentIssue false

Clique partitioning of interval graphswith submodular costs on the cliques

Published online by Cambridge University Press:  21 August 2007

Dion Gijswijt
Affiliation:
Dep. of Operations Research, EGRES, Eötvös Lorand University, Pázmány Peter Setany. 1/C, 1117 Budapest, Hungary; dion.gijswijt@gmail.com
Vincent Jost
Affiliation:
CNRS, laboratoire Leibniz-IMAG, 46 avenue Félix Viallet, 38031 Grenoble Cedex, France; vincent.jost@imag.fr
Maurice Queyranne
Affiliation:
CNRS, laboratoire Leibniz-IMAG, 46 avenue Félix Viallet, 38031 Grenoble Cedex, France; vincent.jost@imag.fr
Get access

Abstract

Given a graph G = (V,E) and a “cost function” $f: 2^V\rightarrow\mathbb{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 coloringproblem 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 ${\overline{\chi}}=\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 graphs and f is value-polymatroidal.

Information

Type
Research Article
Copyright
© EDP Sciences, ROADEF, SMAI, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable