Tight complexity bounds for FPT subgraph problems parameterized by clique-width

Haitze J. Broersma; Petr A. Golovach; Viresh Patel

doi:10.1007/978-3-642-28050-4_17

Tight complexity bounds for FPT subgraph problems parameterized by clique-width

Haitze J. Broersma, Petr A. Golovach, Viresh Patel

Discrete Mathematics and Mathematical Programming

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

3 Citations (Scopus)

48 Downloads (Pure)

Abstract

We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove the following results. The Dense (Sparse) k -Subgraph problem, which asks whether there exists an induced subgraph of G with k vertices and at least q edges (at most q edges, respectively), can be solved in time k O(w)·n, but it cannot be solved in time 2 o(wlogk)·n O(1) unless the Exponential Time Hypothesis (ETH) fails. The d -Regular Induced Subgraph problem, which asks whether there exists a d-regular induced subgraph of G, and the Minimum Subgraph of Minimum Degree at least d problem, which asks whether there exists a subgraph of G with k vertices and minimum degree at least d, can be solved in time d O(w)·n, but they cannot be solved in time 2 o(wlogd)·n O(1) unless ETH fails.

Original language	English
Title of host publication	Parameterized and Exact Computation
Subtitle of host publication	6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers
Editors	Dániel Marx, Peter Rossmanith
Place of Publication	London
Publisher	Springer
Pages	207-218
Number of pages	12
ISBN (Print)	978-3-642-28049-8
DOIs	https://doi.org/10.1007/978-3-642-28050-4_17
Publication status	Published - 2012
Event	6th International Symposium on Parameterized and Exact Computation, IPEC 2011 - Saarbrücken, Germany Duration: 6 Sep 2011 → 8 Sep 2011 Conference number: 6

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	7112
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th International Symposium on Parameterized and Exact Computation, IPEC 2011
Abbreviated title	IPEC
Country/Territory	Germany
City	Saarbrücken
Period	6/09/11 → 8/09/11

Keywords

FPT
Exponential time hypothesis
FPT algorithm
MSC-68R10
MSC-05C85
EWI-22745
Clique-width
IR-83471
METIS-296438
Dense subgraph

Access to Document

10.1007/978-3-642-28050-4_17

ipec2011_submission_17

Cite this

Broersma, H. J., Golovach, P. A., & Patel, V. (2012). Tight complexity bounds for FPT subgraph problems parameterized by clique-width. In D. Marx, & P. Rossmanith (Eds.), Parameterized and Exact Computation: 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers (pp. 207-218). (Lecture Notes in Computer Science; Vol. 7112). Springer. https://doi.org/10.1007/978-3-642-28050-4_17

Broersma, Haitze J. ; Golovach, Petr A. ; Patel, Viresh. / Tight complexity bounds for FPT subgraph problems parameterized by clique-width. Parameterized and Exact Computation: 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers. editor / Dániel Marx ; Peter Rossmanith. London : Springer, 2012. pp. 207-218 (Lecture Notes in Computer Science).

@inproceedings{98de025ee7bd4f889dac741ca72de9aa,

title = "Tight complexity bounds for FPT subgraph problems parameterized by clique-width",

abstract = "We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove the following results. The Dense (Sparse) k -Subgraph problem, which asks whether there exists an induced subgraph of G with k vertices and at least q edges (at most q edges, respectively), can be solved in time k O(w)·n, but it cannot be solved in time 2 o(wlogk)·n O(1) unless the Exponential Time Hypothesis (ETH) fails. The d -Regular Induced Subgraph problem, which asks whether there exists a d-regular induced subgraph of G, and the Minimum Subgraph of Minimum Degree at least d problem, which asks whether there exists a subgraph of G with k vertices and minimum degree at least d, can be solved in time d O(w)·n, but they cannot be solved in time 2 o(wlogd)·n O(1) unless ETH fails.",

keywords = "FPT, Exponential time hypothesis, FPT algorithm, MSC-68R10, MSC-05C85, EWI-22745, Clique-width, IR-83471, METIS-296438, Dense subgraph",

author = "Broersma, {Haitze J.} and Golovach, {Petr A.} and Viresh Patel",

year = "2012",

doi = "10.1007/978-3-642-28050-4_17",

language = "English",

isbn = "978-3-642-28049-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "207--218",

editor = "D{\'a}niel Marx and Peter Rossmanith",

booktitle = "Parameterized and Exact Computation",

note = "6th International Symposium on Parameterized and Exact Computation, IPEC 2011, IPEC ; Conference date: 06-09-2011 Through 08-09-2011",

}

Broersma, HJ, Golovach, PA & Patel, V 2012, Tight complexity bounds for FPT subgraph problems parameterized by clique-width. in D Marx & P Rossmanith (eds), Parameterized and Exact Computation: 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers. Lecture Notes in Computer Science, vol. 7112, Springer, London, pp. 207-218, 6th International Symposium on Parameterized and Exact Computation, IPEC 2011, Saarbrücken, Germany, 6/09/11. https://doi.org/10.1007/978-3-642-28050-4_17

Tight complexity bounds for FPT subgraph problems parameterized by clique-width. / Broersma, Haitze J.; Golovach, Petr A.; Patel, Viresh.

Parameterized and Exact Computation: 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers. ed. / Dániel Marx; Peter Rossmanith. London : Springer, 2012. p. 207-218 (Lecture Notes in Computer Science; Vol. 7112).

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

TY - GEN

T1 - Tight complexity bounds for FPT subgraph problems parameterized by clique-width

AU - Broersma, Haitze J.

AU - Golovach, Petr A.

AU - Patel, Viresh

N1 - Conference code: 6

PY - 2012

Y1 - 2012

N2 - We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove the following results. The Dense (Sparse) k -Subgraph problem, which asks whether there exists an induced subgraph of G with k vertices and at least q edges (at most q edges, respectively), can be solved in time k O(w)·n, but it cannot be solved in time 2 o(wlogk)·n O(1) unless the Exponential Time Hypothesis (ETH) fails. The d -Regular Induced Subgraph problem, which asks whether there exists a d-regular induced subgraph of G, and the Minimum Subgraph of Minimum Degree at least d problem, which asks whether there exists a subgraph of G with k vertices and minimum degree at least d, can be solved in time d O(w)·n, but they cannot be solved in time 2 o(wlogd)·n O(1) unless ETH fails.

AB - We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove the following results. The Dense (Sparse) k -Subgraph problem, which asks whether there exists an induced subgraph of G with k vertices and at least q edges (at most q edges, respectively), can be solved in time k O(w)·n, but it cannot be solved in time 2 o(wlogk)·n O(1) unless the Exponential Time Hypothesis (ETH) fails. The d -Regular Induced Subgraph problem, which asks whether there exists a d-regular induced subgraph of G, and the Minimum Subgraph of Minimum Degree at least d problem, which asks whether there exists a subgraph of G with k vertices and minimum degree at least d, can be solved in time d O(w)·n, but they cannot be solved in time 2 o(wlogd)·n O(1) unless ETH fails.

KW - FPT

KW - Exponential time hypothesis

KW - FPT algorithm

KW - MSC-68R10

KW - MSC-05C85

KW - EWI-22745

KW - Clique-width

KW - IR-83471

KW - METIS-296438

KW - Dense subgraph

U2 - 10.1007/978-3-642-28050-4_17

DO - 10.1007/978-3-642-28050-4_17

M3 - Conference contribution

SN - 978-3-642-28049-8

T3 - Lecture Notes in Computer Science

SP - 207

EP - 218

BT - Parameterized and Exact Computation

A2 - Marx, Dániel

A2 - Rossmanith, Peter

PB - Springer

CY - London

T2 - 6th International Symposium on Parameterized and Exact Computation, IPEC 2011

Y2 - 6 September 2011 through 8 September 2011

ER -

Broersma HJ, Golovach PA, Patel V. Tight complexity bounds for FPT subgraph problems parameterized by clique-width. In Marx D, Rossmanith P, editors, Parameterized and Exact Computation: 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers. London: Springer. 2012. p. 207-218. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-28050-4_17

Tight complexity bounds for FPT subgraph problems parameterized by clique-width

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this