On the complexity of edge-colored subgraph partitioning problems in network optimization

Abstract : Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization over colored graphs has been extensively studied. Given a (not necessarily properly) edge-colored graph $G=(V,E)$, a subgraph $H$ is said to be monochromatic if all its edges have the same color, and called multicolored if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition $V(G)$. We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph $G$ is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln $|V(G)|+1$.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.227-244
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01352853
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 16 août 2016 - 15:16:55
Dernière modification le : jeudi 7 septembre 2017 - 01:03:45
Document(s) archivé(s) le : jeudi 17 novembre 2016 - 10:55:16

Fichier

2549-9955-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01352853, version 1

Collections

Citation

Xiaoyan Zhang, Zan-Bo Zhang, Hajo Broersma, Xuelian Wen. On the complexity of edge-colored subgraph partitioning problems in network optimization. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.227-244. 〈hal-01352853〉

Partager

Métriques

Consultations de la notice

55

Téléchargements de fichiers

264