The Library
Algorithmic complexity of finding cross-cycles in flag complexes
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. doi:10.1145/2261250.2261258 ISSN 9781450312998.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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, Engineering and Medicine > 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 |