Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

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 > 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:
DateEvent
2012Published
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 View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us