TY - GEN
T1 - Beyond classes of graphs with “few” minimal separators
T2 - 41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015
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 -