On computing homological hitting sets
summary
Defines the minimum homological hitting set problem and gives three concrete results: a polynomial‑time algorithm on triangulated closed surfaces that finds an optimal solution by computing a minimum cohomology basis and selecting the lightest cocycle evaluating to 1 on the input cycle; a proof that the problem is W[1]-hard (hence NP‑hard) for general complexes via an FPT reduction from Multicolor Clique; and an FPT algorithm when solution size plus vertex‑degree of the feasible set is the parameter.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:09Simplication of marching
- 3:55Example
- 5:00Surfaces
- 6:26Midcut
- 7:17Boundary nontributalization
- 8:52Homologous problem
- 10:08Parameterized version
- 15:20chromology
- 17:59chromology example
- 18:56evaluation map
- 20:08chromology basis
- 21:13chromology basis example
- 23:51conclusion
related talks
01h 02mFine-Grained Counting Complexity II
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
19mComputing Cohomology Rings in Cubical Agda
A Formal Disproof of Hirsch Conjecture
01h 02mFine-Grained Counting Complexity I
30mParameterized Inapproximability of Max k-Subset Intersection under ETH
29mSubexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds
33mDense Subset Sum May Be the Hardest