1. On independent set in B1-EPG graphs
- Author
-
Christophe Paul, Marin Bougeret, Stéphane Bessy, Daniel Gonçalves, Steven Chaplick, DKE Scientific staff, RS: FSE DACS, RS: FSE DACS Mathematics Centre Maastricht, Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), University of Würzburg = Universität Würzburg, and ANR-12-JS02-0002,EGOS,Graphes Plongés et leurs Structures Orientées(2012)
- Subjects
FOS: Computer and information sciences ,FPT ,Independent set ,0211 other engineering and technologies ,PTAS ,0102 computer and information sciences ,02 engineering and technology ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,PLANAR ,B1 EPG graphs ,01 natural sciences ,Combinatorics ,PATHS ,Chordal graph ,Computer Science - Data Structures and Algorithms ,Discrete Mathematics and Combinatorics ,Data Structures and Algorithms (cs.DS) ,0101 mathematics ,Approximation ,Mathematics ,Discrete mathematics ,Polynomial (hyperelastic model) ,COMPLEXITY ,Intersection (set theory) ,Applied Mathematics ,010102 general mathematics ,EDGE-INTERSECTION GRAPHS ,021107 urban & regional planning ,Grid ,Longest path problem ,Graph ,Parameterized complexity ,APPROXIMATION ALGORITHMS ,010201 computation theory & mathematics ,OPTIMIZATION PROBLEMS ,Bounded function ,Path (graph theory) ,Maximal independent set ,InformationSystems_MISCELLANEOUS ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In this paper we consider the Maximum Independent Set problem (MIS) on B 1 -EPG graphs, that is the one-bend ( B 1 ) Edge intersection graphs of Paths on a Grid (EPG graphs). The graph class EPG was introduced in Golumbic et al. (2019) 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 B k -EPG denotes EPG-graphs where every path has at most k bends. The study of MIS on B 1 -EPG graphs has been initiated in Epstein et al. (2013) where authors prove that MIS is NP-complete on B 1 -EPG graphs, and provide a polynomial 4-approximation. In this article we study the approximability and the fixed parameter tractability of MIS on B 1 -EPG. We show that the class of k ≥ 4 subdivided graphs is a subclass of B 1 -EPG, even if there is only one shape of path and if each path has its vertical part or its horizontal part of length at most 1. This implies that there is no PTAS for MIS (and several other classical problems) on these particular B 1 -EPG graphs. On the positive side, we show that if the length of the horizontal part of every path is bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on B 1 -EPG restricted to only three shapes of path, and W [ 1 ] -hard on B 2 -EPG. The status for general B 1 -EPG (with the four shapes) is left open.
- Published
- 2020