arXiv:2107.10339cs.CG
Finding minimum bounded and homologous chains in simplicial complexes with bounded-treewidth 1-skeleton
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
We consider two problems on simplicial complexes: the Optimal Bounded Chain Problem and the Optimal Homologous Chain Problem. The Optimal Bounded Chain Problem asks to find the minimum weight $d$-chain in a simplicial complex $K$ bounded by a given $(d{-}1)$-chain, if such a $d$-chain exists. The Optimal Homologous Chain problem asks to find the minimum weight $(d{-}1)$-chain in $K$ homologous to a given $(d{-}1)$-chain. Both of these problems are NP-hard and hard to approximate within any constant factor assuming the Unique Games Conjecture. We prove that these problems are fixed-parameter tractable with respect to the treewidth of the 1-skeleton of $K$.
The abstract problem absolutely has legitimate interpretations outside of phylogenetics, and there are other ways to formulate the problem that directly relate to linear algebra over GF(2). Reformulating the problem in those contexts also failed. It is a legitimate, pure CS…
rob-pView on HNParent context