Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs

DOI10.1016/j.ejc.2021.103309zbMath1506.05162arXiv1809.05675OpenAlexW3123770256MaRDI QIDQ2662795

Sebastian Siebertz, Michał Pilipczuk

Publication date: 14 April 2021

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Sample Compression Schemes for Balls in Graphs ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ Unnamed Item ⋮ 1-extendability of independent sets ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Vertex cover at distance on \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Covering planar graphs with a fixed number of balls
• Hitting sets when the VC-dimension is small
• Colouring graphs with bounded generalized colouring number
• The asymptotic distribution of short cycles in random regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Some simplified NP-complete graph problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Almost optimal set covers in finite VC-dimension
• Constant-factor approximation of the domination number in sparse graphs
• Grad and classes with bounded expansion. I: Decompositions
• On nowhere dense graphs
• Interpreting nowhere dense graph classes as a classical notion of model theory
• VC-dimension and Erdős-Pósa property
• Theory of uniform convergence of frequencies of events to their probabilities and problems of search for an optimal solution from empirical data
• Graph Theory
• Domination Problems in Nowhere-Dense Classes
• High degree graphs contain large-star factors
• (Meta) Kernelization
• Polynomial-time data reduction for dominating set
• Some problems in the enumeration of labelled graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors
• Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Kernelization and Sparseness: the case of Dominating Set
• Deciding First-Order Properties of Nowhere Dense Graphs
• Reducibility among Combinatorial Problems
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• On the number of types in sparse graphs
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• On distance ‐dominating and ‐independent sets in sparse graphs
• Bidimensionality and Geometric Graphs

This page was built for publication: Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs