The Library
Algorithmic complexity of finding cross-cycles in flag complexes
Tools
Tools
Tools
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. ISSN 9781450312998. doi:10.1145/2261250.2261258
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1145/2261250.2261258
Abstract
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 | ||||
| Publisher: | ACM | ||||
| ISSN: | 9781450312998 | ||||
| Book Title: | Proceedings of the 2012 symposuim on Computational Geometry - SoCG '12 | ||||
| Official Date: | 2012 | ||||
| Dates: |
|
||||
| Page Range: | pp. 51-60 | ||||
| DOI: | 10.1145/2261250.2261258 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| 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 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
