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

Fedor V. Fomin; Mathieu Liedloff; Pedro Montealegre; Ioan Todinca

doi:10.1007/978-3-319-08404-6_16

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

Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre, Ioan Todinca

Faculty of Engineering and Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

13 Scopus citations

Abstract

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*(3^vc and O*(1.6181^mw), 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 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*(4^vc or O*(1.7347^mw).

Original language	English
Title of host publication	Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings
Publisher	Springer Verlag
Pages	182-193
Number of pages	12
ISBN (Print)	9783319084039
DOIs	https://doi.org/10.1007/978-3-319-08404-6_16
State	Published - 2014
Event	14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014 - Copenhagen, Denmark Duration: 2 Jul 2014 → 4 Jul 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8503 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014
Country/Territory	Denmark
City	Copenhagen
Period	2/07/14 → 4/07/14

Access to Document

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

Cite this

Fomin, F. V., Liedloff, M., Montealegre, P., & Todinca, I. (2014). Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. In Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings (pp. 182-193). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8503 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-08404-6_16

Fomin, Fedor V. ; Liedloff, Mathieu ; Montealegre, Pedro et al. / Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings. Springer Verlag, 2014. pp. 182-193 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{097cda8e536a4276952cdeafd40d2f51,

title = "Algorithms parameterized by vertex cover and modular width, through potential maximal cliques",

abstract = "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).",

author = "Fomin, {Fedor V.} and Mathieu Liedloff and Pedro Montealegre and Ioan Todinca",

note = "Funding Information: Supported by the European Research Council under the European Union{\textquoteright}s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 267959.; 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014 ; Conference date: 02-07-2014 Through 04-07-2014",

year = "2014",

doi = "10.1007/978-3-319-08404-6_16",

language = "English",

isbn = "9783319084039",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "182--193",

booktitle = "Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings",

}

Fomin, FV, Liedloff, M, Montealegre, P & Todinca, I 2014, Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. in Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8503 LNCS, Springer Verlag, pp. 182-193, 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014, Copenhagen, Denmark, 2/07/14. https://doi.org/10.1007/978-3-319-08404-6_16

Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. / Fomin, Fedor V.; Liedloff, Mathieu; Montealegre, Pedro et al.
Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings. Springer Verlag, 2014. p. 182-193 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8503 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Fomin FV, Liedloff M, Montealegre P, Todinca I. Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. In Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings. Springer Verlag. 2014. p. 182-193. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-08404-6_16

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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this