TY - JOUR

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 - Publisher Copyright:
© 2017, Springer Science+Business Media New York.

PY - 2018/4/1

Y1 - 2018/4/1

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 its minimal separators is O∗(3 vc) and O∗(1. 6181 mw) , and the number of potential maximal cliques is O∗(4 vc) and O∗(1. 7347 mw) , 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 applications of potential maximal cliques, 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∗(4 vc) or O∗(1. 7347 mw). With slightly different techniques, we prove that the Treedepth problem can be also solved in single-exponential time, for both parameters.

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 its minimal separators is O∗(3 vc) and O∗(1. 6181 mw) , and the number of potential maximal cliques is O∗(4 vc) and O∗(1. 7347 mw) , 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 applications of potential maximal cliques, 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∗(4 vc) or O∗(1. 7347 mw). With slightly different techniques, we prove that the Treedepth problem can be also solved in single-exponential time, for both parameters.

KW - Parametrized algorithms

KW - Potential maximal cliques

KW - Treewidth

KW - Vertex cover

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

U2 - 10.1007/s00453-017-0297-1

DO - 10.1007/s00453-017-0297-1

M3 - Article

AN - SCOPUS:85014030548

SN - 0178-4617

VL - 80

SP - 1146

EP - 1169

JO - Algorithmica

JF - Algorithmica

IS - 4

ER -