An approximability-related parameter on graphs―-properties and applications

Abstract : We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results for other problems. Our main application is the problem (weighted) maximum H-colourable subgraph (Max H-Col), which is a restriction of the general maximum constraint satisfaction problem (Max CSP) to a single, binary, and symmetric relation. Using known approximation ratios for Max k-cut, we obtain general asymptotic approximability results for Max H-Col for an arbitrary graph H. For several classes of graphs, we provide near-optimal results under the unique games conjecture. We also investigate separation as a graph parameter. In this vein, we study its properties on circular complete graphs. Furthermore, we establish a close connection to work by Šámal on cubical colourings of graphs. This connection shows that our parameter is closely related to a special type of chromatic number. We believe that this insight may turn out to be crucial for understanding the behaviour of the parameter, and in the longer term, for understanding the approximability of optimisation problems such as Max H-Col.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.33--66
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01196862
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 10 septembre 2015 - 15:17:26
Dernière modification le : mercredi 11 avril 2018 - 12:12:03
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:02:45

Fichier

dmtcs-17-1-3.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01196862, version 1

Collections

Citation

Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper. An approximability-related parameter on graphs―-properties and applications. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.33--66. 〈hal-01196862〉

Partager

Métriques

Consultations de la notice

218

Téléchargements de fichiers

185