|
 
|
[RS11] On the Maximum Affinity Coloring : Complexity in Bipartite Conflict Graphs and Links with Multiway Cut
Rapport Scientifique : Date de dépot: 2011/12/01, (Tech. Rep.: CEDRIC-11-2431)Mots clés: Coloring, multiway cut, bipartite graph, chordal graph, treewidth, partial k-trees, register allocation
Résumé:
The maximum affinity K-coloring problem is a generalization of the classical K- coloring problem that enables to model that two vertices should be, if possible, colored with the same color. Such vertices are linked with another kind of edges, called affinities. Almost all the algorithms used in practice use local criteria to determine whether an affinity can be satisfied (i.e. its endpoints can be colored with the same color) or not. These criteria only rely on the colorability of the graph and do not take care of the global configuration of affinities.
This paper has two objectives. First, highlight a problem that models many applications and on which much work has to be done. Second, point out that affinities have to be considered more globally than they currently are in the literature.
We first describe complexity results, mostly in 2-colorable graphs. In partic- ular, we show that the problem is NP-hard in these graphs for K = 2, meaning that the problem is hard even if coloring the graph is easy. Then we prove that any affinity of a graph can be satisfied while preserving the K-colorability in partial (K − 1)-trees. Finally, we prove that, in partial (K − 1)-trees, an optimal affinity coloring can be found by solving a minimum multiway cut instance and a classical K-coloring instance separately.
BibTeX
| @techreport { | |||
| RS11, | |||
| title | = | "{On the Maximum Affinity Coloring : Complexity in Bipartite Conflict Graphs and Links with Multiway Cut}", | |
| author | = | "B. Robillard and E. Soutil", | |
| number | = | "{CEDRIC-11-2431}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {01-12-2011}, | |
| } | |||
