Clique partitioning of interval graphs with submodular costs on the cliques
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 275-287.

Given a graph G=(V,E) and a “cost function” f:2 V →ℝ (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 χ ¯=α 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.

DOI : 10.1051/ro:2007024
Classification : 90C27, 05C15
Mots-clés : partition into cliques, interval graphs, circular arc graphs, max-coloring, probabilist coloring, chromatic entropy, partial $q$-coloring, batch-scheduling, submodular functions, bipartite matchings, split graphs 
@article{RO_2007__41_3_275_0,
     author = {Gijswijt, Dion and Jost, Vincent and Queyranne, Maurice},
     title = {Clique partitioning of interval graphs with submodular costs on the cliques},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {275--287},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {3},
     year = {2007},
     doi = {10.1051/ro:2007024},
     mrnumber = {2348002},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2007024/}
}
TY  - JOUR
AU  - Gijswijt, Dion
AU  - Jost, Vincent
AU  - Queyranne, Maurice
TI  - Clique partitioning of interval graphs with submodular costs on the cliques
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2007
SP  - 275
EP  - 287
VL  - 41
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2007024/
DO  - 10.1051/ro:2007024
LA  - en
ID  - RO_2007__41_3_275_0
ER  - 
%0 Journal Article
%A Gijswijt, Dion
%A Jost, Vincent
%A Queyranne, Maurice
%T Clique partitioning of interval graphs with submodular costs on the cliques
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2007
%P 275-287
%V 41
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2007024/
%R 10.1051/ro:2007024
%G en
%F RO_2007__41_3_275_0
Gijswijt, Dion; Jost, Vincent; Queyranne, Maurice. Clique partitioning of interval graphs with submodular costs on the cliques. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 275-287. doi : 10.1051/ro:2007024. http://www.numdam.org/articles/10.1051/ro:2007024/

[1] N. Alon and A. Orlitsky, Source coding and graph entropies. IEEE Trans Inform Theory 42 (1996) 1329-1339. | Zbl

[2] L. Becchetti, P. Korteweg, A. Marchetti-Spaccamela, M. Skutella, L. Stougie and A. Vitaletti, Latency contrained aggregation in sensor networks. Workshop of Combinatorial Optimization, Aussois (2006). | MR

[3] M. Boudhar, Dynamic Scheduling on a Single Batch Processing Machine with Split Compatibility Graphs. J. Math. Model. Algorithms 2 (2003) 17-35. | Zbl

[4] P. Brucker and S. Knust, Complexity results of scheduling problems. www.mathematik.uni-osnabrueck.de/research/OR/class/

[5] K. Cameron, A min-max relation for the partial q-colourings of a graph. II: Box perfection. Discrete Math. 74 (1989) 15-27. | Zbl

[6] J. Cardinal, S. Fiorini and G. Joret, Minimum entropy coloring. ISAAC, Lect. Notes Comput. Sci. 3827 (2005) 819-828.

[7] F. Della Croce, B. Escoffier, C. Murat and V. Th. Paschos, Probabilistic coloring of bipartite and split graphs. ICCSA'05, Lect. Notes Comput. Sci. 3483 (2005) 202-211 (see also Cahiers du Lamsade No. 218).

[8] M. Demange, D. De Werra, J. Monnot and V.T. Paschos, Time slot scheduling of compatible jobs. Cahiers du Lamsade No. 182, (2001), (accepted in J. Scheduling).

[9] E. Desgrippes, Coordination entre la production et la distribution dans une chaîne logistique. Laboratoire GILCO - Grenoble (2005).

[10] J. Edmonds and R. Giles, A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1 (1977) 185-204. | Zbl

[11] B. Escoffier, J. Monnot and V. Th. Paschos, Weighted Coloring: Further Complexity and Approximability Results. ICTCS (2005) 205-214.

[12] G. Finke, V. Jost, M. Queyranne and A. Sebő, Batch processing with interval graph compatibilities between tasks. Cahier du Leibniz No. 108, Laboratoire Leibniz-IMAG, Grenoble (2004) (accepted in Discrete Appl. Math.). | MR

[13] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press (1980). | MR | Zbl

[14] D.J. Guan and Xuding Zhu, A Coloring Problem for Weighted Graphs. Inf. Process. Lett. 61 (1997) 77-81.

[15] Y.T. Herer and M. Penn, Characterizations of natural submodular graphs: A polynomially solvable class of the TSP. Proc. Am. Math. Soc. 123 (1995) 673-679. | Zbl

[16] V. Jost, Ordonnancement chromatique: Polyèdres, Complexité et Classification. Ph.D. thesis, Laboratoire Leibniz-IMAG - UJF - Grenoble (2006).

[17] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Springer (2003). | Zbl

[18] M. Yannakakis and F. Gavril, The maximum k-colorable subgraph problem for chordal graphs. Inf. Process. Lett. 24 (1987) 133-137. | Zbl

Cité par Sources :