Explicit Linear Kernels for Packing Problems

Valentin Garnero 1 Christophe Paul 2 Ignasi Sau 2 Dimitrios Thilikos 2
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them constructive kernels with reasonably low explicit constants. To fill this gap, we recently presented [STACS 2014] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of vertices. In this article we enhance our framework to deal with packing problems, that is, problems whose solutions can be certified by collections of subgraphs of the input graph satisfying certain properties. F-Packing is a typical example: for a family F of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph G contains k vertex-disjoint sub-graphs such that each of them contains a graph in F as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of F-Packing: for an integer 1, one aims at finding either minor-models that are pairwise at distance at least in G (-F-Packing), or such that each vertex in G belongs to at most minors-models (F-Packing with-Membership). Finally, we also provide linear kernels for the versions of these problems where one wants to pack subgraphs instead of minors.
Complete list of metadatas

Cited literature [48 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02342736
Contributor : Dimitrios M. Thilikos <>
Submitted on : Friday, November 1, 2019 - 11:41:12 AM
Last modification on : Wednesday, November 6, 2019 - 1:37:53 AM

File

ALGO-D-16-00298-R1.pdf
Files produced by the author(s)

Identifiers

Citation

Valentin Garnero, Christophe Paul, Ignasi Sau, Dimitrios Thilikos. Explicit Linear Kernels for Packing Problems. Algorithmica, Springer Verlag, 2019, 81 (4), pp.1615-1656. ⟨10.1007/s00453-018-0495-5⟩. ⟨lirmm-02342736⟩

Share

Metrics

Record views

20

Files downloads

10