  Backdoors of answer-set programs are sets of atoms that represent clever
reasoning shortcuts through the search space. Assignments to backdoor atoms
reduce the given program to several programs that belong to a tractable target
class. Previous research has considered target classes based on notions of
acyclicity where various types of cycles (good and bad cycles) are excluded
from graph representations of programs. We generalize the target classes by
taking the parity of the number of negative edges on bad cycles into account
and consider backdoors for such classes. We establish new hardness results and
non-uniform polynomial-time tractability relative to directed or undirected
cycles.
