### Abstract

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

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 | Germany |

City | Saarbrücken |

Period | 6/09/11 → 8/09/11 |

### Fingerprint

### Keywords

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

### Cite this

*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

}

*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.

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

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 -