2026-07-25T21:48:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6934 2024-03-06T10:38:49Z ddc:004 open_access

A 2lk Kernel for l-Component Order Connectivity Kumar, Mithilesh Lokshtanov, Daniel Parameterized algorithms Kernel Component Order Connectivity Max-min allocation Weighted expansion 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mithilesh Kumar and Daniel Lokshtanov 2017 Is Part Of LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2016.20 urn:nbn:de:0030-drops-69345 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.20 eng https://creativecommons.org/licenses/by/3.0/legalcode