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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)
15 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 languageEnglish
Title of host publicationParameterized and Exact Computation
Subtitle of host publication6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers
EditorsDániel Marx, Peter Rossmanith
Place of PublicationLondon
PublisherSpringer
Pages207-218
Number of pages12
ISBN (Print)978-3-642-28049-8
DOIs
Publication statusPublished - 2012
Event6th International Symposium on Parameterized and Exact Computation, IPEC 2011 - Saarbrücken, Germany
Duration: 6 Sep 20118 Sep 2011
Conference number: 6

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7112
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Symposium on Parameterized and Exact Computation, IPEC 2011
Abbreviated titleIPEC
CountryGermany
CitySaarbrücken
Period6/09/118/09/11

Fingerprint

Clique-width
Subgraph
Induced Subgraph
Exponential time
Minimum Degree
Vertex Degree
Graph in graph theory
Upper and Lower Bounds
Arbitrary

Keywords

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

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). London: 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",

}

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 proceedingConference contributionAcademicpeer-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

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

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). https://doi.org/10.1007/978-3-642-28050-4_17