Clique partitioning of interval graphs with submodular costs on the cliques

Dion Gijswijt; Vincent Jost; Maurice Queyranne

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 3, page 275-287
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Gijswijt, Dion, Jost, Vincent, and Queyranne, Maurice. "Clique partitioning of interval graphs with submodular costs on the cliques." RAIRO - Operations Research 41.3 (2007): 275-287. <http://eudml.org/doc/250125>.

@article{Gijswijt2007,
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 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 $\{\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. },
author = {Gijswijt, Dion, Jost, Vincent, Queyranne, Maurice},
journal = {RAIRO - Operations Research},
keywords = {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; partition into cliques; interval graphs; circular arc graphs; probabilist coloring; chromatic entropy; partial -coloring; batch-scheduling; submodular functions; bipartite matchings},
language = {eng},
month = {8},
number = {3},
pages = {275-287},
publisher = {EDP Sciences},
title = {Clique partitioning of interval graphs with submodular costs on the cliques},
url = {http://eudml.org/doc/250125},
volume = {41},
year = {2007},
}

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
DA - 2007/8//
PB - EDP Sciences
VL - 41
IS - 3
SP - 275
EP - 287
AB - 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 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 ${\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.
LA - eng
KW - 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; partition into cliques; interval graphs; circular arc graphs; probabilist coloring; chromatic entropy; partial -coloring; batch-scheduling; submodular functions; bipartite matchings
UR - http://eudml.org/doc/250125
ER -

References

top
  1. N. Alon and A. Orlitsky, Source coding and graph entropies. IEEE Trans Inform Theory42 (1996) 1329–1339.  
  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).  
  3. M. Boudhar, Dynamic Scheduling on a Single Batch Processing Machine with Split Compatibility Graphs. J. Math. Model. Algorithms2 (2003) 17–35.  
  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.  
  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.  
  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.).  
  13. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press (1980).  
  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.  
  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).  
  18. M. Yannakakis and F. Gavril, The maximum k-colorable subgraph problem for chordal graphs. Inf. Process. Lett.24 (1987) 133–137.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.