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)
22 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

Keywords

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

Fingerprint Dive into the research topics of 'Tight complexity bounds for FPT subgraph problems parameterized by clique-width'. Together they form a unique fingerprint.

Cite this