On the complexity of the representation of simplicial complexes by trees

Description

In this paper, we investigate the problem of the representation of simplicial complexes by trees.We introduce and analyze local and global tree representations.We prove that the global tree representation is more efficient in terms of time complexity for searching a given simplex and we show that the local tree representation is more efficient in terms of size of the structure.The simplicial complexes are modeled by hypergraphs.We then prove that the associated combinatorial optimization problems are very difficult to solve and to approximate even if the set of maximal simplices induces a planar graph of maximum degree at most three or a bounded degree hypergraph.However, we prove polynomial time algorithms that compute constant factor approximations and optimal solutions for some classes of instances.

Abstract

International audience

Additional details