Homology localization through the looking-glass of parameterized complexity theory
Let \(K\) be a weighted simplicial complex, where each simplex is assigned a real number. The weight of a \(d\)-chain \(U\) in \(K\) is defined as the sum of the weights of the constituent simplices of \(U\). The homology localization problem \(\mathrm{HL}_d\) determines, given a \(d\)-cycle \(V\) and a real number \(s\) (the solution size), whether or not there is a \(d\)-cycle \(U\) with weight at most \(s\) that is homologous to \(V\). More generally, the gap homology localization problem \(\mathrm{HL}_{d,\gamma}\) determines if there is a solution to the \(\mathrm{HL}_d\) problem with size at most \(s\), or if every \(d\)-cycle homologous to \(V\) weighs more than \(s\gamma\). The authors of the article show that in the unweighted case, where each simplex is assigned a weight of unity, the \(\mathrm{HL}_{d,\gamma}\) problem parameterized by solution size is \(W[1]\)-hard. In addition, two algorithms for computing the solution of the weighted \(\mathrm{HL}_d\) problem are presented. The first algorithm is parameterized by the treewidth of the \((d+1)\)-connectivity graph of \(K\), which has vertices given by the \((d+1)\)-simplices, and edges given by pairs of simplices that share a \(d\)-face. The second is parameterized by the treewidth of the subgraph of the Hasse diagram of \(K\) with vertices the \(d\) and \((d-1)\)-simplices. Both algorithms are shown to be fixed parameter tractable, and in fact fixed parameter linear. Numerical experiments performed indicate that the second algorithm outperforms the first in most cases.
- A c^k n 5-approximation algorithm for treewidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Annotating simplices with a homology basis and its applications
- Hardness results for homology localization
- scientific article; zbMATH DE number 1341905 (Why is no real title available?)
- scientific article; zbMATH DE number 6783432 (Why is no real title available?)
- Minimum cuts and shortest homologous cycles
- Parameterized algorithms
- The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
- Topological Data Analysis for Genomics and Evolution
- Topology and data
This page was built for publication: Homology localization through the looking-glass of parameterized complexity theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6956171)
