Parameterized complexity of computing maximum minimal blocking and hitting sets

DOI10.1007/S00453-022-01036-5MaRDI QIDQ2684484zbMATH OpenOpenAlexFDO

Authors Marin Bougeret, Ignasi Sau, Júlio Araújo, Victor Campos

Publication date 16 February 2023

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

kernelizationmaximum minimal blocking setmaximum minimal hitting setparameterized complexitytreewidthupper dominationvertex cover

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) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Maximum minimal vertex cover parameterized by vertex cover
• The parameterized complexity of maximality and minimality problems
• The Parameterized Complexity of Maximality and Minimality Problems
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• Blocker size via matching minors

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
• Fundamentals of parameterized complexity
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• Maximum minimal vertex cover parameterized by vertex cover
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• Note on sunflowers
• On the max min vertex cover problem
• Parameterized algorithms
• Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
• Strong computational lower bounds via parameterized complexity
• The many facets of upper domination
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth. Computations and approximations
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Weighted maximum-clique transversal sets of graphs
• What Is Known About Vertex Cover Kernelization?
• Which problems have strongly exponential complexity?

Cited in

(4)

• The Complexity of Deciding Strictly Non-Blocking Concentration and Generalized-Concentration Properties
• Kernelization dichotomies for hitting subgraphs under structural parameterizations
• Parameterized max min feedback vertex set
• MaxMin separation problems: FPT algorithms for st-separator and odd cycle transversal

This page was built for publication: Parameterized complexity of computing maximum minimal blocking and hitting sets

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