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

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

Chapter 3: Beyond

Introduction to: Beyond

The Even Cycle Problem leads to many other avenues of research, on such varied topics as labelled digraphs, Pfaffian orientations, permanents, polytopes and more. In this chapter, we briefly explore some of these generalizations and side streets, and conclude our tour with proposed topics for future research.

Balanced Labellings

A balanced labelling of a digraph is an assignment from {-1, 0, +1} to its vertices (one label per vertex) such that not all labels are 0, and every vertex labelled ±1 has at least one neighbor of opposite sign. Let us now prove a digraph has a balanced labelling if and only if it has an even cycle. Unfortunately, there are too many possible labellings to be checked for this result to lead to an efficient algorithm for detecting even cycles.

Theorem (Klee, n. d.): Given a digraph G, the following are equivalent:

G has an even cycle
G admits a balanced labelling
G admits a balanced labelling in which the neighbors of every vertex labelled 0 are also labelled 0.

Proof: Given a balanced labelling, one can find an even cycle by starting with a nonzero label and following edges which alternate sign from one vertex to the next, until some vertex is repeated. The portion of the walk between the two appearances of the repeated vertex is an even cycle.

Conversely, given an even cycle, label its vertices alternatingly +1, -1 and then extend to a balanced labelling for the entire digraph as follows: While there is an edge (x, y) such that x is not yet labelled and y has a nonzero label, label x oppositely from y. When there are no more such edges (x, y), attach the label 0 to all remaining unlabelled nodes. The extended labelling is balanced (by construction), and has the additional property that if a vertex is lablled 0, then so are all of its neighbors. Thus the three properties in the theorem are equivalent.

Distinguished Vertices

A vertex in a signed digraph is distinguished if every path ending at that vertex uses only positive edges. Any strong component of the graph which contains a distinguised vertex is also said to be distinguished. Manber proved several results concerning distinguished vertices. [Manber, 1982] For example, when the digraph is formed from an L-matrix, each distinguished component contains only one distinguished vertex and there are no paths starting in an undistinguished component and ending in a distinguished one. Armed with the concept of distinguished vertices and given any L-matrix A, one can find a vector b such that Ax = b is sign-solvable by choosing b_i >= 0 if i is distinguished, and b_i = 0 otherwise.

Permanents

A formula for the permanent of a square matrix is deceptively similar to the well-known alternating sum for the determinant - simply remove the alternating sign from each term in the sum. However, this "minor" difference greatly increases the difficulty of computing the permanent. In fact, computing the permanent of a matrix is NP-hard, even for 0-1 matrices. [Valiant, 1979]

Because the formula for the permanent is superficially so similar to the determinant, many have sought an expression for one in terms of the other. Polya suggested that perhaps the permanent could be found by computing the determinant of another matrix obtained from the original by reversing the sign of some (possibly none) of its entries. [Polya, 1913] However, he also noted that this is not always possible.

In 1989, Vazirani and Yannakakis showed that determining whether the determinant and permanent of a matrix are equal is NP-hard. However, when we restrict the instances to only 0-1 matrices or matrices with nonnegative entries, they showed this problem is equivalent to the Even Cycle Problem. If we say that Polya's scheme, when applied to a 0-1 matrix A, is to change some +1 entries to -1, then Vazirani and Yannakakis also showed that determining whether or not Polya's scheme can be applied to a square 0-1 matrix A to produce a matrix B such that det(B) = perm(A) is equivalent to the Even Cycle Problem.

Pfaffian Orientations

A [perfect] matching is a subset of the edges of a graph such that every vertex of the graph is incident to at most [exactly] one edge in the matching. In 1967, Kasteleyn described a polynomial time algorithm for computing the number of perfect matchings of any planar, undirected graph. His proof relied heavily on the idea of a Pfaffian orientation of the graph. Of course, any undirected graph can be converted to a directed one by arbitrarily assigning directions to its edges. To assign a Pfaffian orientation, first distinguish each cycle C in the graph G for which C has even length and G\C has a perfect matching. A Pfaffian orientation of G, if one exists, is an orientation such that when traversing each distinguished cycle, an odd number of edges are oriented in the direction of the traversal.

One reason Pfaffian orientations are of interest is that given a graph G with a Pfaffian orientation, if the matrix B is obtained from its adjacency matrix A by replacing with -1 those entries corresponding to edges which are reversed in the orientation (i.e., Polya's scheme), then the determinant of B is the square of the number of perfect matchings in G.

Every K_3,3-free graph has a Pfaffian orientation that can be found in polynomial time. [Little, 1974] On the other hand, deciding whether or not a bipartite graph has a Pfaffian orientation is equivalent to the Even Cycle Problem. [Vazirani and Yannakakis, 1989]

Interval Matrices

We can generalize sign-solvability by a modification of the qualitative class. When the qualitative classes are viewed as collections of matrices whose entries belong to one of three intervals, the two open intervals (-

, 0) and (0,

) together with the degenerate interval {0}, a natural generalization of sign-solvability (and other concepts related to sign patterns) is to consider interval matrices, whose entries belong to certain intervals. That is, given a set of intervals or types of intervals, we define the "qualitative class" (with respect to that set) to be those matrices whose entries lie in those [types of] intervals.

The usual type of interval matrix found in the literature is a restriction to finite closed (or open) intervals. Then we can describe qualitative classes succinctly as [A - B, A + B] := { M \in R_nxn such that a_{i j} - b_{i j} <= m_{i j} <= a_{i j} + b_{i j}} where A is the matrix whose entries are the midpoints of each interval and B is a nonnegative matrix determining the length of each interval (using strict inequalities when we wish to consider open intervals). In general, the computational complexity of recognizing whether every matrix in such a "qualitative class" is nonsingular is NP-hard. [Poljak and Rohn, 1993]

Cone-Systems

We mentioned in passing that an equivalent definition of an nx(n+1) S-matrix is that when its columns are treated as vertices in Rn, they determine an n-simplex with the origin in its interior. Continuing in this direction, observe that the columns of any matrix in the qualitative class Q(A) (for some matrix A) all lie in convex cones. This follows from the fact that for any vector x, Q(x) is a sign cone of vectors with the same sign as x in each of its coordinates.

When viewed in this way, the recognition problem for S-matrices becomes a question of determining whether the origin belongs to certain convex sets derived from the sign-cones. Klee, von Hohenbalken and Lewis proved the more general result that, given any mxn system (A₁, A₂, ..., A_n) of finitely-presented cones, there are polynomial time algorithms to recognize whether the origin is in the vector sum of the cones and whether it is in their convex hull. As a consequence, the recognition problem for S-matrices admits a polynomial-time solution.

Their geometric approach is beautiful, and ties in with interval matrices as well. Unfortunately, interval matrices have upper and lower bounds for each entry, so each cone could require up to O(2m) generators. Sign-cones need only O(m) generators, so their algorithm solves the recognition problem for sign-cones in polynomial time, but not for general interval matrices. In general, the complexities of algorithms for polytopes depend on the representations of the polytopes - either as the convex hull of a set of vertices, or as the intersection of half-spaces determined by linear inequalities. Interval matrices, for example, can be represented using O(m) linear inequalities. Perhaps their result can also be proved for cones presented in this way.

Also, their algorithm is not as efficient as the O(m²) algorithm for recognizing S-matrices [Klee, 1987], so other improvements may be possible. What happens for matrices whose columns belong to more general polytopes than just cones? What characterizations might these matrices have in terms of digraphs? What connections do they have to sign-solvability, or more general kinds of solvability?

Open Problems

Many of the generalizations mentioned in this chapter have not been fully investigated. Klee (personal communication) has suggested examining, for example, interval matrices using five types of intervals: (-

, -1], (-1, 0), {0}, (0, 1), and [1,

). In general, what happens when we fix a set of intervals and then define the qualitative classes using these intervals? When are all the matrices in such a class solvable? Stable? Are there analogs of L- and S-matrices for these classes?

Especially promising are the generalizations from sign-cones to polytopes. How can the considerable machinery from the theory of polytopes be brought to bear on this subject? Klee, von Hohenbalken, and Lewis (1993) successfully employed results from linear programming to establish the computational complexity of some of these systems, but this is only a beginning.

Even when we constrain ourselves to remain within the confines of the original problems concerning L-matrices, sign-solvability, and even cycles in directed graphs, there are many interesting unexplored avenues and unsolved problems. (Of course, there is always the main one: Determine the complexity of the Even Cycle Problem!) Many results for L-matrices and their ilk can be translated into results for directed graphs, and vice-versa. [e.g., Brualdi and Shader, chapter 6] What other results can be so translated? For example, what implications do k-connectedness or planarity of a digraph have for its adjacency matrix, and how do these implications affect our analysis of the square L-matrix problem? Can an efficient algorithm for one restricted problem (such as the polynomial-time algorithm for recognizing planar digraphs without even cycles) be transformed into efficient algorithms for the others (perhaps an efficient algorithm for recognizing a certain subclass of L-matrices)?

It would be very surprising if the only 2-connected digraph with no even cycles is the one given in the first chapter. Perhaps there is only a finite list of such graphs; even if there are infinitely many, perhaps they can be described succinctly enough to allow a polynomial-time algorithm to test whether a given 2-connected digraph is one of them. If nothing else, surely upper bounds on the number of edges can be found, analogous to the bound for (1-)connected digraphs. [Chung, Goddard, and Kleitman, 1994]

Conclusion

The Even Cycle Mystery remains unsolved. In the course of investigating this thorny case, sleuths have discovered leads into many disparate areas of mathematics, and proximity to problems of widely varying difficulty and complexity. Although the case may never be completely solved, progress continues to be made as many exciting answers are found, and even more unanswered questions are raised.