Explicit linear kernels for packing problems

DOI10.1007/S00453-018-0495-5MaRDI QIDQ1739112zbMATH OpenOpenAlexWikidataFDO

Authors Valentin Garnero, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos

Publication date 25 April 2019

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.06131

zbMATH Keywords

dynamic programminggraph minorsparameterized complexitypacking problemslinear kernelsprotrusion replacement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

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. $mathcalF$-Packing is a typical example: for a family $mathcalF$ 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 subgraphs such that each of them contains a graph in $mathcalF$ as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of $mathcalF$-Packing: for an integer $ellgeq1$, one aims at finding either minor-models that are pairwise at distance at least $ell$ in $G$ ($ell$-$mathcalF$-Packing), or such that each vertex in $G$ belongs to at most $ell$ minors-models ($mathcalF$-Packing with $ell$-Membership). Finally, we also provide linear kernels for the versions of these problems where one wants to pack subgraphs instead of minors.

Recommendations

• Explicit linear kernels via dynamic programming
• Explicit linear kernels via dynamic programming
• A Problem Kernelization for Graph Packing
• Bidimensionality and kernels
• Kernelization of packing problems

Cites work

• scientific article; zbMATH DE number 475614 (Why is no real title available?)
• scientific article; zbMATH DE number 6783430 (Why is no real title available?)
• (Meta) kernelization
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Problem Kernelization for Graph Packing
• A parameterized algorithm for packing overlapping subgraphs
• A simpler algorithm and shorter proof for the graph minor decomposition
• An algebraic theory of graph reduction
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Bidimensionality and kernels
• Contraction obstructions for treewidth
• Explicit linear kernels via dynamic programming
• Faster parameterized algorithms for minor containment
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XVI: Excluding a non-planar graph
• Graph theory
• Graph-based data clustering with overlaps
• Irrelevant vertices for the planar disjoint paths problem
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization algorithms for packing problems allowing overlaps
• Large-treewidth graph decompositions and applications
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid
• Linearity of grid minors in treewidth with applications through bidimensionality
• Lower bounds based on the exponential time hypothesis
• On Independent Circuits Contained in a Graph
• On search, decision, and the efficiency of polynomial-time algorithms
• Parameterized algorithms
• Polynomial bounds for the grid-minor theorem
• Polynomial-time data reduction for dominating set
• Reduction algorithms for graphs of small treewidth
• Scattered packings of cycles
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Strengthening Erdős -- Pósa property for minor-closed graph classes
• The \({\mathcal{G}}\)-packing with \(t\)-overlap problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth. Computations and approximations
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(11)

• Explicit linear kernels via dynamic programming
• Stronger bounds and faster algorithms for packing in generalized kernel systems
• Explicit linear kernels via dynamic programming
• On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Dynamic programming on bipartite tree decompositions
• Kernels for packing and covering problems
• Dynamic programming on bipartite tree decompositions
• Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
• Bidimensionality and kernels
• Kernels for Packing and Covering Problems

This page was built for publication: Explicit linear kernels for packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1739112)