Parameterized and approximation complexity of \textsc{Partial VC Dimension}
DOI10.1016/j.tcs.2018.09.013zbMath1417.68059arXiv1609.05110OpenAlexW2562491834WikidataQ129204745 ScholiaQ129204745MaRDI QIDQ1731844
Florent Foucaud, Cristina Bazgan, Florian Sikora
Publication date: 14 March 2019
Published in: Theoretical Computer Science, Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1609.05110
VC dimensionhypergraphsparameterized complexityapproximation complexitydistinguishing transversalpartial problems
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (5)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterizations of test cover with bounded test sizes
- Fundamentals of parameterized complexity
- A survey of binary covering arrays
- Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
- On separating systems
- Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
- Optimization, approximation, and complexity classes
- A partial k-arboretum of graphs with bounded treewidth
- The hardness of approximation: Gap location
- The VC-dimension of set systems defined by graphs
- Approximation algorithms for the test cover problem
- Some APX-completeness results for cubic graphs
- Parameterized and approximation complexity of \textsc{Partial VC Dimension}
- On limited nondeterminism and the complexity of the V-C dimension
- The inapproximability of non-NP-hard optimization problems.
- Subexponential algorithms for partial cover problems
- Linear time solvable optimization problems on graphs of bounded clique-width
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Parameterized approximability of maximizing the spread of influence in networks
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- Parametrized complexity theory.
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- On the computational hardness based on linear fpt-reductions
- VC-dimension and Erdős-Pósa property
- Induced subsets
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
- Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs
- Approximating low-dimensional coverage problems
- Detecting high log-densities
- Parameterized Study of the Test Cover Problem
- A threshold of ln n for approximating set cover
- Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Identifying and Locating–Dominating Codes in (Random) Geometric Networks
- Approximation algorithms for NP-complete problems on planar graphs
- On a new class of codes for identifying vertices in graphs
- Hitting Set for hypergraphs of low VC-dimension
- Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs
- Partial vs. Complete Domination: t-Dominating Set
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
This page was built for publication: Parameterized and approximation complexity of \textsc{Partial VC Dimension}
