Algorithmic complexity of finding cross-cycles in flag complexes
Adamaszek, Michał and Stacho, Juraj (2012) Algorithmic complexity of finding cross-cycles in flag complexes. In: ACM Symposium on Computational Geometry 2012, North Carolina, USA, 17-20 Jun 2012. Published in: Proceedings of the 2012 symposuim on Computational Geometry pp. 51-60.Full text not available from this repository.
Official URL: http://dx.doi.org/10.1145/2261250.2261258
A cross-cycle in a flag simplicial complex K is an induced subcomplex that is isomorphic to the boundary of a cross-polytope and that contains a maximal face of K. A cross-cycle is an efficient way to define a non-zero class in the homology of K. For an independence complex of a graph G, a cross-cycle is equivalent to a combinatorial object: induced matching containing a maximal independent set. We study the complexity of finding cross-cycles in independence complexes. We show that in general this problem is NP-complete when input is a graph whose independence complex we consider. We then focus on the class of chordal graphs, where, as we show, cross-cycles detect all of homology of the independence complex. As our main result, we present a polynomial time algorithm for detecting a cross-cycle in the independence complex of a chordal graph. Our algorithm is based on the geometric intersection representation of chordal graphs and has an efficient implementation.
As a corollary, we obtain polynomial time algorithms for such topological properties as contractibility or simple-connectedness of independence complexes of chordal graphs. These problems are undecidable for general independence complexes.
We further prove that even for chordal graphs, it is NP-complete to decide if there is a cross-cycle of a given cardinality, and hence, if a particular homology group of the independence complex is nontrivial. As a corollary we obtain that computing homology groups of arbitrary simplicial complexes given as a list of facets is NP-hard.
|Item Type:||Conference Item (Paper)|
|Divisions:||Faculty of Science > Mathematics|
|Journal or Publication Title:||Proceedings of the 2012 symposuim on Computational Geometry|
|Book Title:||Proceedings of the 2012 symposuim on Computational Geometry - SoCG '12|
|Page Range:||pp. 51-60|
|Access rights to Published version:||Restricted or Subscription Access|
|Conference Paper Type:||Paper|
|Title of Event:||ACM Symposium on Computational Geometry 2012|
|Type of Event:||Conference|
|Location of Event:||North Carolina, USA|
|Date(s) of Event:||17-20 Jun 2012|
Actions (login required)