2003/06/25 by Edith Hemaspaandra, Holger Spakowski, Hemaspaandra, Edith +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0306131
10 pages
arxiv created 2003/06/25 · arxiv updated 2009/11/30
The even cycle problem for both undirected and directed graphs has been the topic of intense research in the last decade. In this paper, we study the computational complexity of cycle length modularity problems. Roughly speaking, in a cycle length modularity problem, given an input (undirected or directed) graph, one has to determine whether the graph has a cycle C of a specific length (or one of several different lengths), modulo a fixed integer. We denote the two families (one for undirected graphs and one for directed graphs) of problems by (S,m)\hbox-\rm UC and (S,m)\hbox-\rm DC, where m ∈ N and S ⊆ \0,1, ..., m-1\. (S,m)\hbox-\rm UC (respectively, (S,m)\hbox-\rm DC) is defined as follows: Given an undirected (respectively, directed) graph G, is there a cycle in G whose length, modulo m, is a member of S? In this paper, we fully classify (i.e., as either polynomial-time solvable or as \rm NP-complete) each problem (S,m)\hbox-\rm UC such that 0 ∈ S and each problem (S,m)\hbox-\rm DC such that 0 ∉ S. We also give a sufficient condition on S and m for the following problem to be polynomial-time computable: (S,m)\hbox-\rm UC such that 0 ∉ S.