Computer Science – Computational Complexity
Scientific paper
2003-06-25
Computer Science
Computational Complexity
10 pages
Scientific paper
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 \emph{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 \in \mathcal{N}$ and $S \subseteq \{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 \in S$ and each problem $(S,m)\hbox{-}{\rm DC}$ such that $0 \notin 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 \notin S$.
Hemaspaandra Edith
Spakowski Holger
Thakur Mayur
No associations
LandOfFree
Complexity of Cycle Length Modularity Problems in Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complexity of Cycle Length Modularity Problems in Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Cycle Length Modularity Problems in Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-68020