Identifying codes in hereditary classes of graphs and VC-dimension
From MaRDI portal
Abstract: An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We show a dichotomy for the size of the smallest identifying code in classes of graphs closed under induced subgraphs. Our dichotomy is derived from the VC-dimension of the considered class C, that is the maximum VC-dimension over the hypergraphs formed by the closed neighbourhoods of elements of C. We show that hereditary classes with infinite VC-dimension have infinitely many graphs with an identifying code of size logarithmic in the number of vertices while classes with finite VC-dimension have a polynomial lower bound. We then turn to approximation algorithms. We show that the problem of finding a smallest identifying code in a given graph from some class is log-APX-hard for any hereditary class of infinite VC-dimension. For hereditary classes of finite VC-dimension, the only known previous results show that we can approximate the identifying code problem within a constant factor in some particular classes, e.g. line graphs, planar graphs and unit interval graphs. We prove that it can be approximate within a factor 6 for interval graphs. In contrast, we show that on C_4-free bipartite graphs (a class of finite VC-dimension) it cannot be approximated to within a factor of c.log(|V|) for some c>0.
Recommendations
- The complexity of the identifying code problem in restricted graph classes
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Extremal graphs for the identifying code problem
- Minimal identifying codes in trees and planar graphs with large girth
- Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
Cites work
- scientific article; zbMATH DE number 1670858 (Why is no real title available?)
- scientific article; zbMATH DE number 3906528 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1349588 (Why is no real title available?)
- scientific article; zbMATH DE number 1552836 (Why is no real title available?)
- A combinatorial problem; stability and order for models and theories in infinitary languages
- Approximability of identifying codes and locating-dominating codes
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Complexity results for identifying codes in planar graphs
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Discriminating codes in bipartite graphs
- Dominating sets in \(k\)-majority tournaments.
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- Identifying Codes and Covering Problems
- Identifying codes in line graphs
- Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- On a new class of codes for identifying vertices in graphs
- On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)
- On the density of families of sets
- Ramsey-type theorems
- Scott's induced subdivision conjecture for maximal triangle-free graphs
- Structure in Approximation Classes
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Transversals of d-intervals
Cited in
(21)- On three domination-based identification problems in block graphs
- Discriminating Codes in Geometric Setups
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension
- Revisiting and improving upper bounds for identifying codes
- A story of diameter, radius, and (almost) Helly property
- Identification of points using disks
- Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
- On three domination-based identification problems in block graphs
- The \textsc{Red-Blue Separation} problem on graphs
- Neighbourhood complexity of graphs of bounded twin-width
- The \textsc{red-blue separation} problem on graphs
- On a conjecture regarding identification in Hamming graphs
- Fast diameter computation within split graphs
- Induced subgraph density. VI: Bounded VC-dimension
- Computing diameter+2 in truly-subquadratic time for unit-disk graphs
- Complexity and approximation for discriminating and identifying code problems in geometric setups
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- The binary locating-dominating number of some convex polytopes
- Bounding the trace function of a hypergraph with applications
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
This page was built for publication: Identifying codes in hereditary classes of graphs and VC-dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449863)
