Non total-unimodularity neutralized simplicial complexes

DOI10.1016/J.DAM.2016.01.004zbMATH Open1383.05311arXiv1304.4985OpenAlexW2963568911MaRDI QIDQ1707913FDOQ1707913

Authors: Bala Krishnamoorthy, Gavin W. Smith 

Publication date: 4 April 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1304.4985

Recommendations

• Complexity of simplicial homology and independence complexes of chordal graphs
• A computationally intractable problem on simplicial complexes
• Homological reconstruction and simplification in \(\mathbb{R}^3\)

zbMATH Keywords

simplicial complexhomologylinear optimizationtotal unimodularity

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• Title not available (Why is that?)
• Topological persistence and simplification
• Title not available (Why is that?)
• Decomposition of regular matroids
• Degeneracy in interior point methods for linear programming: A survey
• Homological sensor networks
• Combinatorial optimization. Packing and covering
• The complexity of recognizing linear systems with certain integrality properties
• Title not available (Why is that?)
• A polynomial-time test for total dual integrality in fixed dimension
• Balanced matrices
• Characterization of Totally Unimodular Matrices
• Minimum cuts and shortest homologous cycles
• Splitting (complicated) surfaces is hard
• Structural properties and recognition of restricted and strongly unimodular matrices
• Tightening non-simple paths and cycles on surfaces
• Distributed Coverage Verification in Sensor Networks Without Location Information
• Measuring and computing natural generators for homology groups
• Alternatives for testing total dual integrality
• From Totally Unimodular to Balanced 0, ±1 Matrices: A Family of Integer Polytopes
• Hardness results for homology localization
• A decomposition theory for matroids. VII: Analysis of minimal violation matrices
• The least spanning area of a knot and the optimal bounding chain problem

Cited In (1)

• Lexicographic optimal homologous chains and applications to point cloud triangulations

Uses Software

• Homology

This page was built for publication: Non total-unimodularity neutralized simplicial complexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1707913)