From the Even Cycle Mystery to the L-Matrix Problem and Beyond

by Michael Brundage
( brundage@ipac.caltech.edu )

Appendix C: Relatives of the Even Cycle Problem

References are provided when possible, as well as the name used in the literature to describe the problem. We first list those problems whose complexity is known, and conclude the section with those problems which are equivalent to the Even Cycle Problem, but whose complexity remains unknown. See Appendix A for details on the meaning of "equivalent" and the format of the decision problems presented here.

When convenient, several problems with similar wordings are grouped together by putting the alternate wordings in square brackets. Unless explicitly stated otherwise, all graphs and digraphs are finite and simple, and all matrices are real.

Polynomial-Time (P) Problems

Odd Cycle [Walk, Trail]: Instance: A directed graph G.; Question: Does G have an odd cycle [walk, trail] ?; (Klee, Ladner, and Manber, 1984)
Local Odd [Even] Walk: Instance: A directed graph G and one of its vertices v.; Question: Does G have an odd [even] walk through v?; (Klee, Ladner, and Manber, 1984)
S[*]-Matrix: Instance: A matrix A.; Question: Is A an S[*]-Matrix?; (Klee, 1987)
Undirected Even [Odd] Cycle: Instance: An undirected graph G.; Question: Does G have an even [odd] cycle?; (LaPaugh and Papadimitriou, 1984)
Planar Even Cycle: Instance: A planar, directed graph G.; Question: Does G have an even cycle?; (Thomassen, 1993; Galluccio and Loebl, 1994)
Even Cycle on Fixed Surface: Instance: An arbitrary fixed surface and any direceted graph G embedded on that surface.; Question: Does G have an even cycle?; (Galluccio and Loebl, 1996)
Even Cycles in H-Free Graphs: Instance: A K3,3 -free or K5 -free directed graph G.; Question: Does G have an even cycle?; (Galluccio and Loebl, 1995)
Planar Perfect Matching: Instance: A planar, undirected graph G.; Question: Does G have a perfect matching?; (Kasteleyn, 1967)

NP-Complete (NPC) Problems

Local Odd [Even] Cycle (LOCODD[EV]CY): Instance: A directed graph G and one of its vertices v.; Question: Does G have an odd [even] cycle through v?; (Klee, Ladner, and Manber, 1984)
General L-Matrix: Instance: An mxn matrix A.; Question: Is A an L-matrix?; (Klee, Ladner, and Manber, 1984)
Restricted L-Matrix: Instance: An (n + floor[n^1/k])xn matrix A.; Question: Is A an L-matrix?; (Klee, Ladner, and Manber, 1984)

NP-Hard Problems

Permanent Equals Determinant: Instance: A square matrix A.; Question: Does perm(A) = det (A)?; (Vazirani and Yannakakis, 1989)
Nonsingular Interval Matrix: Instance: An interval of matrices [A + cB, A - cB], 0 <= c <= 1.; Question: Is every matrix in the interval nonsingular?; (Poljak and Rohn, 1993)

The Even Cycle Problem and Equivalent Ones

Even Cycle (EVCY): Instance: A directed graph G.; Question: Does G have an even cycle?
Even Trail: Instance: A directed graph G.; Question: Does G have an even trail?
Square L-matrix Problem (LMAT): Instance: A square matrix A.; Question: Is A an L-matrix?; (Bassett, Maybee, and Quirk, 1968)
Even Digraph: Instance: A directed graph G.; Question: Is G even?; (Seymour and Thomassen, 1987)
Balanced Labelling: Instance: A directed graph G.; Question: Does G admit a balanced labelling?; (Klee, n. d.)
Perfect Matching: Instance: An undirected, bipartite graph G.; Question: Does G have a perfect matching?; (Vazirani and Yannakakis, 1989)
Restricted Version of Permanent Equals Determinant: Instance: A square matrix A with non-negative entries.; Question: Does perm(A) = det (A)?; (Vazirani and Yannakakis, 1989)
Polya's Problem: Instance: A square 0-1 matrix A.; Question: Can some entries be changed from +1 to -1 to obtain a new matrix B for which det(B) = perm(A)?; (Vazirani and Yannakakis, 1989)