k-gap interval graphs

DOI10.1007/978-3-642-29344-3_30zbMATH Open1353.68124DBLPconf/latin/FominGGSSLVV12arXiv1112.3244OpenAlexW2117562847WikidataQ60488535 ScholiaQ60488535MaRDI QIDQ2894479FDOQ2894479

Authors: Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger

Publication date: 29 June 2012

Published in: LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Abstract: We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real line, with an edge between two vertices if and only if an interval associated to one vertex has a nonempty intersection with an interval associated to the other vertex. A graph on n vertices is a k-gap interval graph if it has a multiple interval representation with at most n+k intervals in total. In order to scale up the nice algorithmic properties of interval graphs (where k=0), we parameterize graph problems by k, and find FPT algorithms for several problems, including Feedback Vertex Set, Dominating Set, Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The Coloring problem turns out to be W[1]-hard and we design an XP algorithm for the recognition problem.

Full work available at URL: https://arxiv.org/abs/1112.3244

Recommendations

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (2)

This page was built for publication: \(k\)-gap interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2894479)