21
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Non Total-Unimodularity Neutralized Simplicial Complexes

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Given a simplicial complex K with weights on its simplices and a chain on it, the Optimal Homologous Chain Problem (OHCP) is to find a chain with minimal weight that is homologous (over the integers) to the given chain. The OHCP is NP-complete, but if the boundary matrix of K is totally unimodular (TU), it becomes solvable in polynomial time when modeled as a linear program (LP). We define a condition on the simplicial complex called non total-unimodularity neutralized, or NTU neutralized, which ensures that even when the boundary matrix is not TU, the OHCP LP must contain an integral optimal vertex for every input chain. This condition is a property of K, and is independent of the input chain and the weights on the simplices. This condition is strictly weaker than the boundary matrix being TU. More interestingly, the polytope of the OHCP LP may not be integral under this condition. Still, an integral optimal vertex exists for every right-hand side, i.e., for every input chain. Hence a much larger class of OHCP instances can be solved in polynomial time than previously considered possible. As a special case, we show that 2-complexes with trivial first homology group are guaranteed to be NTU neutralized.

          Related collections

          Author and article information

          Journal
          2013-04-17
          2013-07-09
          Article
          1304.4985
          2062895b-970c-4a97-ba7a-06927b49a295

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          55U10, 55N99, 52B12, 90C10
          Identified a class of complexes that are guaranteed to be NTU neutralized (Theorem 8.1). Added one figure, and improved the presentation in several places
          math.AT cs.CG math.OC

          Numerical methods,Theoretical computer science,Geometry & Topology
          Numerical methods, Theoretical computer science, Geometry & Topology

          Comments

          Comment on this article

          Similar content313