The parameterized complexity of finding minimum bounded chains

Abstract

Finding the smallest d-chain with a specific (d − 1)-boundary in a simplicial complex is known as the Minimum Bounded Chain problem (MBCd). MBCd is NP-hard for all d ≥2. In this paper, we prove that it is also W[1]-hard for all d ≥ 2, if we parameterize the problem by solution size. We also give an algorithm solving MBC1 in polynomial time and introduce and implement two fixed parameter tractable (FPT) algorithms solving MBCd for all d. The first algorithm uses a shortest path approach and is parameterized by solution size and coface degree. The second algorithm is a dynamic programming approach based on treewidth, which has the same runtime as a lower bound we prove under the exponential time hypothesis.