[Back]

F. Fomin, S. Gaspers, P. Golovach, K. Suchan, St. Szeider, E. van Leeuwen, M. Vatshelle, Y. Villanger:
"k-Gap Interval Graphs";
Talk: Latin American Theoretical Informatics Symposium, Arequipa, Peru; 2012-04-16 - 2012-04-20; in: "Proceedings of the 10th Latin American Theoretical Informatics Symposium (LATIN 2012)", D. Fernández-Baca (ed.); Lecture Notes in Computer Science / Springer, 7256 (2012), ISBN: 978-3-642-29343-6; 350 - 361.

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 -hard and we design an XP algorithm for the recognition problem.

Computer Science

http://dx.doi.org/10.1007/978-3-642-29344-3_30

Project Head Stefan Szeider:
The Parameterized Complexity of Reasoning Problems