VC-dimension and Erdős-Pósa property

DOI10.1016/J.DISC.2015.05.026MaRDI QIDQ2515568zbMATH OpenOpenAlexFDO

Authors Nicolas Bousquet, Stéphan Thomassé

Publication date 5 August 2015

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

clique-minordistance VC-dimensiondominating setErdős-Pósa propertyrankwidth

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $G=(V,E)$ be a graph. A $k$-neighborhood in $G$ is a set of vertices consisting of all the vertices at distance at most $k$ from some vertex of $G$. The hypergraph on vertex set $V$ which edge set consists of all the $k$-neighborhoods of $G$ for all $k$ is the neighborhood hypergraph of $G$. Our goal in this paper is to investigate the complexity of a graph in terms of its neighborhoods. Precisely, we define the distance VC-dimension of a graph $G$ as the maximum taken over all induced subgraphs $G^{\prime }$ of $G$ of the VC-dimension of the neighborhood hypergraph of $G^{\prime }$. For a class of graphs, having bounded distance VC-dimension both generalizes minor closed classes and graphs with bounded clique-width. Our motivation is a result of Chepoi, Estellon and Vax`es asserting that every planar graph of diameter $2ell$ can be covered by a bounded number of balls of radius $ell$. In fact, they obtained the existence of a function $f$ such that every set $calF$ of balls of radius $ell$ in a planar graph admits a hitting set of size $f(u)$ where $u$ is the maximum number of pairwise disjoint elements of $calF$. Our goal is to generalize the proof of Chepoi, Estellon and Vax`es with the unique assumption of bounded distance VC-dimension of neighborhoods. In other words, the set of balls of fixed radius in a graph with bounded distance VC-dimension has the ErdH{o}s-P'osa property.

Recommendations

• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• Erdos-Hajnal conjecture for graphs with bounded VC-dimension
• Packing and covering balls in graphs excluding a minor
• The VC-dimension of set systems defined by graphs
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension

Cites work

• Approximating clique-width and branch-width
• Bounded VC-dimension implies a fractional Helly theorem
• Bounding the vertex cover number of a hypergraph
• Classes of graphs with small rank decompositions are \(\chi \)-bounded
• Constant-factor approximation of the domination number in sparse graphs
• Covering planar graphs with a fixed number of balls
• Density and dimension
• Dominating sets in \(k\)-majority tournaments.
• Domination in planar graphs with small diameter*
• Domination numbers of planar graphs
• Graph Theory and Probability
• scientific article; zbMATH DE number 2044937 (Why is no real title available?)
• On Independent Circuits Contained in a Graph
• On the density of families of sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Quasi-optimal range searching in spaces of finite VC-dimension

Cited in

(19)

• Packing and covering balls in graphs excluding a minor
• On density of subgraphs of halved cubes
• Packing and covering with balls on Busemann surfaces
• Recent techniques and results on the Erdős-Pósa property
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• Beyond Helly graphs: the diameter problem on absolute retracts
• Erdös-Pósa Property of Obstructions to Interval Graphs
• Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• On the VC-dimension‎, ‎covering and separating properties of the cycle and spanning tree hypergraphs of graphs
• Sample Compression Schemes for Balls in Graphs
• A story of diameter, radius, and (almost) Helly property
• Erdős–Pósa property of obstructions to interval graphs
• Computing diameter+2 in truly-subquadratic time for unit-disk graphs
• Obstructions to faster diameter computation: asteroidal sets
• Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
• Going beyond surfaces in diameter approximation
• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs

This page was built for publication: VC-dimension and Erdős-Pósa property

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