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.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

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:	Date Event 2012 Published
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