Header menu link for other important links
Circuit complexity of properties of graphs with constant planar cutwidth
Published in Springer Verlag
Volume: 8635 LNCS
Issue: PART 2
Pages: 336 - 347
We study the complexity of several of the classical graph decision problems in the setting of bounded cutwidth and how imposing planarity affects the complexity. We show that for 2-coloring, for bipartite perfect matching, and for several variants of disjoint paths, the straightforward NC 1 upper bound may be improved to AC 0[2], ACC 0, and AC 0 respectively for bounded planar cutwidth graphs. We obtain our upper bounds using the characterization of these circuit classes in tems of finite monoids due to Barrington and Thérien. On the other hand we show that 3-coloring and Hamilton cycle remain hard for NC 1 under projection reductions, analogous to the NP-completeness for general planar graphs. We also show that 2-coloring and (non-bipartite) perfect matching are hard under projection reductions for certain subclasses of AC 0[2]. In particular this shows that our bounds for 2-coloring are quite close. © 2014 Springer-Verlag Berlin Heidelberg.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
Open AccessNo
Concepts (12)
  •  related image
    Artificial intelligence
  •  related image
    Computer science
  •  related image
  •  related image
    Circuit complexity
  •  related image
    Decision problems
  •  related image
  •  related image
  •  related image
  •  related image
    Perfect matchings
  •  related image
    Planar graph
  •  related image
    Upper bound
  •  related image
    Graph theory