On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT

DOI10.7155/JGAA.00413zbMath1358.05281arXiv1507.05890OpenAlexW2574162147MaRDI QIDQ5892359

Bart M. P. Jansen

Publication date: 5 April 2017

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

2-SAT problem in multiple valued logiccomplexity of Hitting Set

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

On Covering Segments with Unit Intervals

Cites Work

• Unnamed Item
• Two-layer planarization parameterized by feedback edge set
• Exact algorithms and applications for tree-like Weighted Set Cover
• A kernelization algorithm for \(d\)-hitting set
• Solving NP-hard problems in 'almost trees': vertex cover
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Which problems have strongly exponential complexity?
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Parametrized complexity theory.
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Incompressibility through Colors and IDs
• Set Cover, Set Packing and Hitting Set for Tree Convex and Tree-Like Set Systems
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT
• Fixed-parameter complexity of \(\lambda\)-labelings

This page was built for publication: On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT