TY - GEN

T1 - Algorithms parameterized by vertex cover and modular width, through potential maximal cliques

AU - Fomin, Fedor V.

AU - Liedloff, Mathieu

AU - Montealegre, Pedro

AU - Todinca, Ioan

N1 - Funding Information:
Supported by the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 267959.

PY - 2014

Y1 - 2014

N2 - In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover (vc) and modular width (mw). We prove that for any graph, the number of minimal separators is O*(3vc and O*(1.6181mw), the number of potential maximal cliques is O*(4vc) and O*(1.7347mw), and these objects can be listed within the same running times. (The O* notation suppresses polynomial factors in the size of the input.) Combined with known results [3,12], we deduce that a large family of problems, e.g., Treewidth, Minimum Fill-in, Longest Induced Path, Feedback vertex set and many others, can be solved in time O*(4vc or O*(1.7347mw).

AB - In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover (vc) and modular width (mw). We prove that for any graph, the number of minimal separators is O*(3vc and O*(1.6181mw), the number of potential maximal cliques is O*(4vc) and O*(1.7347mw), and these objects can be listed within the same running times. (The O* notation suppresses polynomial factors in the size of the input.) Combined with known results [3,12], we deduce that a large family of problems, e.g., Treewidth, Minimum Fill-in, Longest Induced Path, Feedback vertex set and many others, can be solved in time O*(4vc or O*(1.7347mw).

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

U2 - 10.1007/978-3-319-08404-6_16

DO - 10.1007/978-3-319-08404-6_16

M3 - Conference contribution

AN - SCOPUS:84904167952

SN - 9783319084039

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

SP - 182

EP - 193

BT - Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings

PB - Springer Verlag

T2 - 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014

Y2 - 2 July 2014 through 4 July 2014

ER -