Clique partitioning of interval graphs with submodular costs on the cliques

Gijswijt, Dion; Jost, Vincent; Queyranne, Maurice

doi:10.1051/ro:2007024

Gijswijt, Dion ; Jost, Vincent ; Queyranne, Maurice

RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 3, pp. 275-287.

Résumé

Given a graph $G = (V, E)$ and a “cost function” $f : 2^{V} \to ℝ$ (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 $\bar{χ} = α$ 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/

Bibliographie
Cité par

[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

Hu, Qiaolin; Gu, Weihua; Wu, Lingxiao; Zhang, Le Optimal autonomous truck platooning with detours, nonlinear costs, and a platoon size constraint, Transportation Research Part E: Logistics and Transportation Review, Volume 186 (2024), p. 103545 | DOI:10.1016/j.tre.2024.103545
Muir, Christopher; Toriello, Alejandro Interval scheduling with economies of scale, Computers Operations Research, Volume 150 (2023), p. 9 (Id/No 106056) | DOI:10.1016/j.cor.2022.106056 | Zbl:1520.90117
Pandit, Supantha Covering and packing of triangles intersecting a straight line, Discrete Applied Mathematics, Volume 319 (2022), pp. 92-110 | DOI:10.1016/j.dam.2021.11.017 | Zbl:1496.90080
Levin, M. Sh. On the Clique Partitioning of a Graph, Journal of Communications Technology and Electronics, Volume 67 (2022) no. S2, p. S267 | DOI:10.1134/s1064226922140042
Porretta, Luciano; Catanzaro, Daniele; Halldórsson, Bjarni V.; Fortz, Bernard A branch price algorithm for the minimum cost clique cover problem in max-point tolerance graphs, 4OR, Volume 17 (2019) no. 1, pp. 75-96 | DOI:10.1007/s10288-018-0377-3 | Zbl:1426.90221
Boysen, Nils; Briskorn, Dirk; Schwerdfeger, Stefan The identical-path truck platooning problem, Transportation Research Part B: Methodological, Volume 109 (2018), p. 26 | DOI:10.1016/j.trb.2018.01.006
Catanzaro, Daniele; Chaplick, Steven; Felsner, Stefan; Halldórsson, Bjarni V.; Halldórsson, Magnús M.; Hixon, Thomas; Stacho, Juraj Max point-tolerance graphs, Discrete Applied Mathematics, Volume 216 (2017), pp. 84-97 | DOI:10.1016/j.dam.2015.08.019 | Zbl:1350.05118
Abdallah, Yara; Zheng, Zizhan; Shroff, Ness B.; El Gamal, Hesham; El-Fouly, Tarek M. The Impact of Stealthy Attacks on Smart Grid Performance: Tradeoffs and Implications, IEEE Transactions on Control of Network Systems, Volume 4 (2017) no. 4, p. 886 | DOI:10.1109/tcns.2016.2615158
Nonner, Tim Capacitated max-batching with interval graph compatibilities, Theoretical Computer Science, Volume 613 (2016), pp. 79-93 | DOI:10.1016/j.tcs.2015.10.047 | Zbl:1333.05246
Correa, José R.; Megow, Nicole Clique partitioning with value-monotone submodular cost, Discrete Optimization, Volume 15 (2015), pp. 26-36 | DOI:10.1016/j.disopt.2014.11.001 | Zbl:1308.90187
Catanzaro, Daniele; Labbe, Martine; Halldorsson, Bjarni V. An Integer Programming Formulation of the Parsimonious Loss of Heterozygosity Problem, IEEE/ACM Transactions on Computational Biology and Bioinformatics, Volume 10 (2013) no. 6, p. 1391 | DOI:10.1109/tcbb.2012.138
Abdallah, Yara; Zheng, Zizhan; Shroff, Ness B.; El Gamal, Hesham, 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) (2012), p. 1954 | DOI:10.1109/cdc.2012.6425909
Kaiqian Ou; Yinlong Xu; Shengli Fu, 2012 IEEE Global Communications Conference (GLOBECOM) (2012), p. 4707 | DOI:10.1109/glocom.2012.6503862
Pirwani, Imran A.; Salavatipour, Mohammad R. A weakly robust PTAS for minimum clique partition in unit disk graphs, Algorithmica, Volume 62 (2012) no. 3-4, pp. 1050-1072 | DOI:10.1007/s00453-011-9503-8 | Zbl:1236.68299
Catanzaro, Daniele; Labbé, Martine; Halldórsson, Bjarni V. A Mixed Integer Programming Model for the Parsimonious Loss of Heterozygosity Problem, Bioinformatics Research and Applications, Volume 7292 (2012), p. 24 | DOI:10.1007/978-3-642-30191-9_3
Cardinal, Jean; Fiorini, Samuel; Joret, Gwenaël Minimum entropy combinatorial optimization problems, Theory of Computing Systems, Volume 51 (2012) no. 1, pp. 4-21 | DOI:10.1007/s00224-011-9371-2 | Zbl:1259.90109
Nonner, Tim Capacitated max -Batching with Interval Graph Compatibilities, Algorithm Theory - SWAT 2010, Volume 6139 (2010), p. 176 | DOI:10.1007/978-3-642-13731-0_18
Flammini, Michele; Monaco, Gianpiero; Moscardelli, Luca; Shachnai, Hadas; Shalom, Mordechai; Tamir, Tami; Zaks, Shmuel Minimizing total busy time in parallel scheduling with application to optical networks, Theoretical Computer Science, Volume 411 (2010) no. 40-42, pp. 3553-3562 | DOI:10.1016/j.tcs.2010.05.011 | Zbl:1207.68110
Flammini, Michele; Monaco, Gianpiero; Moscardelli, Luca; Shachnai, Hadas; Shalom, Mordechai; Tamir, Tami; Zaks, Shmuel, 2009 IEEE International Symposium on Parallel Distributed Processing (2009), p. 1 | DOI:10.1109/ipdps.2009.5161017
Nonner, Tim; Souza, Alexander Latency constrained aggregation in chain networks admits a PTAS, Algorithmic aspects in information and management. 5th international conference, AAIM 2009, San Francisco, CA, USA, June 15–17, 2009. Proceedings, Berlin: Springer, 2009, pp. 279-291 | DOI:10.1007/978-3-642-02158-9_24 | Zbl:1246.90033
Nonner, Tim; Souza, Alexander Approximating the joint replenishment problem with deadlines, Discrete Mathematics, Algorithms and Applications, Volume 1 (2009) no. 2, pp. 153-173 | DOI:10.1142/s1793830909000130 | Zbl:1186.68565
Cardinal, Jean; Fiorini, Samuel; Joret, Gwenaël Minimum entropy combinatorial optimization problems, Mathematical theory and computational practice. 5th conference on computability in Europe, CiE 2009, Heidelberg, Germany, July 19–24, 2009. Proceedings, Berlin: Springer, 2009, pp. 79-88 | DOI:10.1007/978-3-642-03073-4_9 | Zbl:1268.90059
Fukunaga, Takuro; Halldórsson, Magnús M.; Nagamochi, Hiroshi “Rent-or-buy” scheduling and cost coloring problems, FSTTCS 2007: Foundations of software technology and theoretical computer science. 27th international conference, New Delhi, India, December 12–14, 2007. Proceedings, Berlin: Springer, 2007, pp. 84-95 | DOI:10.1007/978-3-540-77050-3_7 | Zbl:1135.90344

Cité par 23 documents. Sources : Crossref, zbMATH