On Independent Set on B1-EPG Graphs

Marin Bougeret 1 Stéphane Bessy 1 Daniel Gonçalves 1 Christophe Paul 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this paper we consider the Maximum Independent Set problem (MIS) on B1-EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) was introduced in [8] as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class Bk-EPG denotes EPG-graphs where every path has at most k bends. The study of MIS on B1-EPG graphs has been initiated in [6] where authors prove that MIS is NP-complete on B1-EPG graphs, and provide a polynomial 4-approximation. In this article we study the approximability and the fixed parameter tractability of MIS on B1-EPG. We show that there is no PTAS for MIS on B1-EPG unless P=NP, even if there is only one shape of path, and even if each path has its vertical part or its horizontal part of length at most 3. This is optimal, as we show that if all paths have their horizontal part bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on B1-EPG restricted to only three shapes of path, and W1-hard on B2-EPG. The status for general B1-EPG (with the four shapes) is left open.
Type de document :
Communication dans un congrès
WAOA: International Workshop on Approximation and Online Algorithms, 2015, Patras, Greece. 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers, LNCS (9499), pp.158-169, 2016, Approximation and Online Algorithms. 〈10.1007/978-3-319-28684-6_14〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01264022
Contributeur : Christophe Paul <>
Soumis le : jeudi 28 janvier 2016 - 15:32:36
Dernière modification le : jeudi 19 juillet 2018 - 11:54:04

Lien texte intégral

Identifiants

Collections

Citation

Marin Bougeret, Stéphane Bessy, Daniel Gonçalves, Christophe Paul. On Independent Set on B1-EPG Graphs. WAOA: International Workshop on Approximation and Online Algorithms, 2015, Patras, Greece. 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers, LNCS (9499), pp.158-169, 2016, Approximation and Online Algorithms. 〈10.1007/978-3-319-28684-6_14〉. 〈lirmm-01264022〉

Partager

Métriques

Consultations de la notice

79