Parameterized complexity of computing maximum minimal blocking and hitting sets
DOI10.1007/s00453-022-01036-5OpenAlexW3127978156MaRDI QIDQ2684484
Marin Bougeret, Ignasi Sau, Victor A. Campos, Julio Araujo
Publication date: 16 February 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2102.03404
treewidthvertex coverupper dominationparameterized complexitykernelizationmaximum minimal blocking setmaximum minimal hitting set
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Fundamentals of parameterized complexity
- Weighted maximum-clique transversal sets of graphs
- Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
- On the max min vertex cover problem
- Strong computational lower bounds via parameterized complexity
- Treewidth. Computations and approximations
- Which problems have strongly exponential complexity?
- The many facets of upper domination
- Note on sunflowers
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Myhill-Nerode Methods for Hypergraphs
- Maximum Minimal Vertex Cover Parameterized by Vertex Cover
- Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
- Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
- Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- What Is Known About Vertex Cover Kernelization?
This page was built for publication: Parameterized complexity of computing maximum minimal blocking and hitting sets
