TY - GEN

T1 - Beyond classes of graphs with “few” minimal separators

AU - Liedloff, Mathieu

AU - Montealegre, Pedro

AU - Todinca, Ioan

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2016.

PY - 2016

Y1 - 2016

N2 - In many graph problems, like Longest Induced Path, Maximum Induced Forest, etc., we are given as input a graph G and the goal is to compute a largest induced subgraph G[F], of treewidth at most a constant t, and satisfying some property P. Fomin et al. [12] proved that this generic problem is polynomial on the class of graphs Gpoly, i.e., the graphs having at most poly(n) minimal separators for some polynomial poly, when property P is expressible in counting monadic second order logic (CMSO). Here we consider the class Gpoly + kv, formed by graphs of Gpoly to which we may add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly + kv, with parameter k, if the modulator is also part of the input. The running time is of type O(f(k + t, P) · nt+5 · (poly(n)2)), for some function f.

AB - In many graph problems, like Longest Induced Path, Maximum Induced Forest, etc., we are given as input a graph G and the goal is to compute a largest induced subgraph G[F], of treewidth at most a constant t, and satisfying some property P. Fomin et al. [12] proved that this generic problem is polynomial on the class of graphs Gpoly, i.e., the graphs having at most poly(n) minimal separators for some polynomial poly, when property P is expressible in counting monadic second order logic (CMSO). Here we consider the class Gpoly + kv, formed by graphs of Gpoly to which we may add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly + kv, with parameter k, if the modulator is also part of the input. The running time is of type O(f(k + t, P) · nt+5 · (poly(n)2)), for some function f.

UR - http://www.scopus.com/inward/record.url?scp=84981510251&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-53174-7_35

DO - 10.1007/978-3-662-53174-7_35

M3 - Conference contribution

AN - SCOPUS:84981510251

SN - 9783662531730

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 499

EP - 512

BT - Graph-Theoretic Concepts in Computer Science - 41st International Workshop, WG 2015, Revised Papers

A2 - Mayr, Ernst W.

PB - Springer Verlag

Y2 - 17 June 2015 through 19 June 2015

ER -