Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.20
URN: urn:nbn:de:0030-drops-69345
URL: https://drops.dagstuhl.de/opus/volltexte/2017/6934/
Kumar, Mithilesh ; Lokshtanov, Daniel
A 2lk Kernel for l-Component Order Connectivity
| pdf-format: |
|
Abstract
In the l-Component Order Connectivity problem (l in N), we are given a graph G on n vertices, m edges and a non-negative integer k and asks whether there exists a set of vertices S subseteq V(G) such that |S| <= k and the size of the largest connected component in G-S is at most l. In this paper, we give a kernel for l-Component Order Connectivity with at most 2*l*k vertices that takes n^{O(l)} time for every constant l. On the way to obtaining our kernel, we prove a generalization of the q-Expansion Lemma to weighted graphs. This generalization may be of independent interest.
BibTeX - Entry
@InProceedings{kumar_et_al:LIPIcs:2017:6934,
author = {Mithilesh Kumar and Daniel Lokshtanov},
title = {{A 2lk Kernel for l-Component Order Connectivity}},
booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages = {20:1--20:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-023-1},
ISSN = {1868-8969},
year = {2017},
volume = {63},
editor = {Jiong Guo and Danny Hermelin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6934},
URN = {urn:nbn:de:0030-drops-69345},
doi = {10.4230/LIPIcs.IPEC.2016.20},
annote = {Keywords: Parameterized algorithms, Kernel, Component Order Connectivity, Max-min allocation, Weighted expansion}
}
| Keywords: | Parameterized algorithms, Kernel, Component Order Connectivity, Max-min allocation, Weighted expansion | |
| Seminar: | 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) | |
| Issue date: | 2017 | |
| Date of publication: | 09.02.2017 |
