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

Table of Contents

Page

List of Figures....................................................................................................... iii

List of Tables........................................................................................................ iv

Introduction........................................................................................................... 1

Chapter 1: Even Cycles in Directed Graphs..................................................... 3

Introduction............................................................................................... 3

Walks, Trails, and Cycles......................................................................... 3

Connectivity Results.............................................................................. 10

Even Digraphs......................................................................................... 13

Restricted Versions................................................................................. 13

Conclusion............................................................................................... 14

Chapter 2: L-Matrices and Sign-solvability..................................................... 15

Introduction............................................................................................. 15

Sign-solvability........................................................................................ 15

L-matrices................................................................................................ 17

S-matrices................................................................................................. 18

Recognition.............................................................................................. 20

Cycles in Matrices................................................................................... 22

Signed Digraphs...................................................................................... 22

Conclusion............................................................................................... 23

Chapter 3: Beyond.............................................................................................. 25

Introduction............................................................................................. 25

Balanced Labellings................................................................................ 25

Distinguished Vertices........................................................................... 26

Permanents.............................................................................................. 26

Pfaffian Orientations.............................................................................. 27

Interval Matrices..................................................................................... 27

Cone-Systems......................................................................................... 28

Table of Contents (continued )

Page

Open Problems....................................................................................... 29

Conclusion............................................................................................... 30

Bibliography........................................................................................................ 31

Appendix A: Computational Complexity....................................................... 36

Appendix B: Directed Graph Theory............................................................... 39

Appendix C: Relatives of the Even Cycle Problem....................................... 42

Polynomial-Time (P) Problems............................................................ 42

NP-Complete (NPC) Problems............................................................ 43

NP-Hard Problems................................................................................. 44

The Even Cycle Problem and Equivalent Ones................................. 44

Introduction

Computational complexity is a rapidly growing field of mathematics. With new knowledge, many new problems have arisen; of these, those which are NP-complete are of singular interest. This thesis discusses several problems which are in some sense near the “boundary” of NP-completeness. We focus on two related problems: the Even Cycle Problem for directed graphs, and the L-Matrix Problem. We explore relationships among these two and other problems in computational complexity, both solved and unsolved. Appendices on the theory of NP-completeness and directed graphs are provided for readers unfamiliar with these topics, and an additional appendix lists the complexities of many relatives of the Even Cycle Problem, including those known to be polynomial-time equivalent to it.

An even cycle is a simple cycle of even length (one that uses an even number of edges). The Even Cycle Problem for directed graphs asks if there an efficient (polynomial-time) algorithm to answer the following:

Instance: A directed graph.

Question: Does the digraph have an even cycle?

We will discover that the Even Cycle Problem is equivalent to many other problems, such as the L-Matrix Problem from mathematical economics:

Instance: A square matrix.

Question: Is the matrix an L-matrix?

An L-matrix is a matrix with signed entries such that every real matrix with the same size and sign pattern as it has linearly independent columns.

These problems are all close to the boundary of NP-completeness in the sense that they strongly resemble certain problems known to admit polynomial-time algorithms, yet they also strongly resemble other problems known to be NP-complete. For example, it is easy to construct a polynomial-time algorithm to test a directed graph for the presence of odd cycles and also for the presence of even closed walks. However, localized version of these problems (e.g., looking for cycles of either parity passing through a given vertex) are NP-complete. Recognizing L-matrices is similar to recognizing S-matrices and matrices with signed permanent — both problems admit efficient algorithms — yet in the rectangular case (even for “almost square” matrices), recognizing L-matrices is NP-complete. The complexity of the Even Cycle Problem and the L-Matrix Problem for square matrices remain unknown.

In the first chapter, we explore the Even Cycle Problem in greater depth, and also describe a few related graph-theoretic problems. The second chapter focuses on the L-Matrix Problem, affiliated concepts, and connections with the Even Cycle Problem for directed graphs. We journey beyond these topics in the third chapter, examining questions about permanents, Pfaffians, and labelled digraphs, and extending results of the previous two chapters to problems with a polytopal flavor. This final chapter concludes with a discussion of open problems and suggested topics for future research.

Walks, Trails, and Cycles

For an arbitrary digraph G, consider the following questions:

(1e) Does G contain an even closed walk?

(2e) Does G contain an even closed trail?

(3e) Does G contain an even cycle?

By replacing the word “even” with “odd,” we obtain similar questions (1o), (2o), and (3o). We will also explore localized versions of each, obtained by specifying a vertex v of G and asking (for example):

(1o-loc) Does G have an odd closed walk passing through the vertex v?

The difficulty of detecting even cycles in digraphs apparently was observed first by D.H. Younger. [Younger, 1973] It is still not known whether an efficient algorithm exists for this problem, or whether it is NP-complete. The same is true for the corresponding problem for even closed trails (2e), and in fact, these two problems are equivalent. First let us prove:

Theorem (Klee, Ladner, and Manber, 1984): (1o), (2o), and (3o) all admit polynomial-time solutions.

Proof: Klee, et al. describe an efficient algorithm which solves these and (1e) by solving (1e-loc) and (1o-loc). First we demonstrate the equivalence of (1o), (2o) and (3o) by observing that a digraph has an odd cycle if and only if it has an odd closed walk.

One direction is clear: Every cycle is a closed walk. On the other hand, if W is an odd closed walk x0 x1 … xk (xk = x0 and k is odd), and if W is not already an odd cycle, then there are two vertices repeated in this sequence. Choose i as large as possible subject to the condition that xi = xj for some i < j ≤ k. There is a unique such i and j, and now xi xi+1 ... xj-1 xj is a cycle. If it is an odd cycle, we are done. If not, then j-i is even and the sequence x0 x1 … xi-1 xi xj xj+1 … xk formed by removing the cycle is a shorter odd closed walk. Repeated application of this procedure eventually produces an odd cycle because the digraph is finite. Notice that this proof hinges on the fact that no odd integer can be represented as a sum of two even integers. In contrast, an even integer may be written as a sum of two odd integers, and so a digraph may contain an even closed walk but have no even cycles — for example, the digraph formed by the one-point union of two odd cycles.

Consequently, to solve any of (1o), (2o), and (3o) in polynomial time it suffices to construct an efficient algorithm to determine whether a graph has an odd closed walk. In fact, we will show the stronger result that (1e-loc) and (1o-loc) admit polynomial-time solutions. However, the remaining localized versions are all NP-complete.

In this algorithm, each edge enters the computation at most twice (once for each label that can be “active” on the head vertex of the edge). Thus the computational complexity for solving the localized problems (1o-loc) and (1e-loc) is linear in the number of edges of the digraph (quadratic in the number of vertices). Therefore, determining whether a digraph has an odd cycle (3o) can be solved by an algorithm with time complexity cubic in the number of vertices.

The algorithm is as follows: We are given a digraph G and a vertex v, and ask whether there is an odd (or even) cycle passing through v. Starting at v, breadth-first search through the digraph, keeping track of the parities of lengths of walks discovered. Begin by applying the label 0 to vertex v. Apply the label 1 to the vertex w to indicate the discovery of an odd walk from v to w; similarly, label w with 0 when there is an even walk from v to w. Labels are never removed, and a vertex may have both labels. When attaching a new label to a vertex, the label remains active until the vertex has been “scanned.” Scanning a vertex x consists of inspecting each neighbor y of x to determine whether the recent addition of a new label to x justifies the attachment of a new label to y. The list of all vertices with active labels is kept in a queue Q, which is empty at the beginning of our computation and at the end. When the algorithm terminates, each vertex w carries a label if and only if there is a walk of that parity starting at v and ending at w.

Figure 1 gives the algorithm in pseudo-code. It consists of two functions, the main program and a subsidiary function for applying labels to vertices. Denote the set of all [active] labels of the vertex x by L(x) [A(x)]. The queue Q contains all vertices with active labels, and there are functions add_to_Q(x) and remove_from_Q() which add x to the rear of Q or remove and return the front element of Q, respectively. The functions add_element(element, set) and is_element(element, set) add the element to the set, or return 1 [0] if the element is [not] a member of the set, respectively. Each label is treated as a boolean value (0 or 1), and !s denotes the logical complement of s (read “not s”).

We assume that we are given the source vertex v and the digraph in a manner such that the neighbors of a vertex can be computed efficiently. Table I lists the contents of the queue as the algorithm is run on the sample digraph in figure 2. Each vertex is followed by its currently active labels.

# subsidiary function to add labels to vertices

label(x, y, s) {

if(is_element(!s, A(x)) and !is_element(s, L(x))) {

add_element(s, A(y));

add_element(s, L(y));

if(!is_element(y, Q)) {

add_to_Q(y);

}

# main algorithm

main() {

for each neighbor y of v {

add_element(1, A(y));

add_element(1, L(y));

add_to_Q(y);

}

while Q is nonempty {

x = remove_from_Q();

for each neighbor y of x {

label(x, y, 0);

label(x, y, 1);

A(x) = empty set;

}

if(is_element(0, L(v))) {

print “Vertex v lies on an even closed walk”;

}

if(is_element(1, L(v))) {

print “Vertex v lies on an odd closed walk”;

}

Figure 1: An efficient algorithm for solving (1e-loc) and (1o-loc).

Table I: Active labels of vertices in the queue in a sample run.

Step Vertices in queue (with active labels)

0 empty

1 1 (1) 2 (1) 3 (1)

2 2 (1) 3 (1) 4 (0) 5 (0)

3 3 (1) 4 (0) 5 (0) 1 (0)

4 4 (0) 5 (0) 1 (0)

5 5 (0) 1 (0) v (1)

6 1 (0) v (1)

7 v (1) 4 (1) 5 (1)

8 4 (1) 5 (1) 2 (0) 3 (0)

9 5 (1) 2 (0) 3 (0) v (0)

10 2 (0) 3 (0) v (0)

11 3 (0) v (0)

12 v (0)

13 empty

Figure 2: An example digraph with source vertex v.

As already mentioned, the remaining localized problems are all NP-complete. This situation is in stark contrast to the analogous questions for undirected graphs, all of which (local and global) admit polynomial-time solutions! [La Paugh and Papadimitriou, 1984] For digraphs, the computational complexity of (2e) and (3e) remains unknown, but these two problems are equivalent:

Theorem (Klee, Ladner, and Manber, 1984): Even cycles can be detected efficiently if and only if even closed trails can.

Proof: We describe a polynomial-time algorithm A which takes a digraph G and constructs another digraph H which has an even closed trail if and only if G has an even cycle. Similarly, we describe an algorithm B which constructs a digraph with an even closed trail if and only if the original graph contains an even cycle. These algorithms are illustrated in figure 3. Because each algorithm runs in polynomial time, detecting even cycles in directed graphs is equivalent to detecting even closed trails in directed graphs.

In algorithm A, each vertex of G is replaced by three vertices x0, x1 and x2, and two edges (x0, x1) and (x1, x2). Each edge (x, y) of G is replaced by the edge (x2, y0) in H. Clearly, each cycle of length k in G is transformed into a cycle of length 3k in H. When k is even, this cycle is an even closed trail in H corresponding to the even cycle in G.

On the other hand, suppose T is a closed trail in H. The successive edges of T form a sequence of pairwise edge-disjoint paths of length three. The first two edges of each such path arise from a vertex of G, and the third edge from an edge of G. We claim that no vertex of T is ever repeated, and hence T is actually an even cycle. Consider three successive edges (x0, x1), (x1, x2), (x2, y0) in T, corresponding to an edge (x, y) of G. Now, x2 is not repeated in T because (x1, x2) is the only edge of H into x2, and no edge of T is repeated (T is a trail, by assumption). Similarly, x1 is not repeated. But then the vertex x0 cannot be repeated either, because (x0, x1) is the only edge issuing from x0. Thus, each closed trail T in H is, in fact, a cycle of length 3k, and arises from a cycle of length k in G. Because k and 3k have the same parity, we have constructed the desired algorithm A.

Algorithm B produces the edge graph of G: For each edge (x, y) of G, there is a vertex xy in its edge graph, and (uv, xy) is an edge in the edge graph of G only when v = x. Each closed trail of length k in G involves k distinct, successively adjacent edges, thus leading to a cycle of length k in its edge graph. Conversely, each cycle of length k in the edge graph of G is a sequence of k distinct, adjacent vertices, and hence must come from a sequence of k distinct, successively adjacent edges in G (that is, a closed trail of length k in G).

Figure 3: Algorithms demonstrating the equivalence of detecting even cycles and even closed trails in directed graphs.

Connectivity Results

Although the complexity of finding even closed trails and even cycles remains unknown, there are many results of interest which provide easily checked conditions for a digraph to have an even cycle or an even closed trail. Intuitively, one would expect that a large number of edges (with respect to the number of vertices) would guarantee the existence of an even cycle. That this is indeed the case was established by Chung, Goddard, and Kleitman in 1994:

Theorem: Every strongly connected directed graph with n vertices and at least ë(n + 1)2/4û edges has an even cycle, and this bound is best possible in the sense that there exist strong digraphs with fewer edges and no even cycles.

Of course, this theorem allows for the possibility that many edges are clumped together. In order to obtain better bounds, we need to exlude these cases by better distributing the edges among the vertices. One way to accomplish this task is to place lower or upper bounds on the vertex degrees. For example,

Theorem (Koh, 1976): If each vertex of a digraph G has outdegree at least two, then G contains two edge-disjoint cycles with at least one common vertex. Hence G contains an even closed trail.

Proof: If each vertex of a digraph has outdegree at least one, then the digraph has a cycle. To produce one, start from any edge (x0, x1) and continue to add edges (xk, xk+1) until some vertex is repeated in the sequence x0, …, xk+1. Such edges exist because each vertex has outdegree at least one; until we repeat a vertex, there is always at least one outgoing edge. The graph is finite, so eventually some vertex must be repeated, and then we have found a cycle of the digraph.

Now if every vertex of G has outdegree at least two, start with some cycle C1, and let G1 denote the sugraph of G formed by removing all the edges of C1. Each vertex of G1 has outdegree at least 1, so G1 also has some cycle, C2. Now let G2 be the sugraph of G1 formed by removing the edges of C2. If C2 is vertex-disjoint from C1, then every vertex of G2 also has outdegree at least 1, and we can continue this process. Eventually we obtain two cycles with at least one vertex in common, but with no edges in common.

Given any two such cycles, if either is even then it is an even cycle, and thus an even closed trail. Otherwise, produce an even closed trail by starting at a vertex they have in common and then following first one cycle and then the other.

However, the analogous result for even cycles is not true. In fact, there exist digraphs with arbitrarily large in- and outdegrees, yet no even cycles:

Theorem (Thomassen, 1985): For each positive integer n there are digraphs Dn and Gn having no even cycles, even though

(i) Dn is strong and each vertex of Dn has outdegree n

(ii) each vertex of Gn has indegree n and outdegree at least n

Proof: Let D1 be an odd cycle, and create Dn from Dn-1 by induction as follows: For each vertex v in Dn-1 add a set Yv of n vertices and one more additional vertex v’. Add the edge (v, v’) and for each y in Yv add the edges (v’, y) and (y, v). Also, for each neighbor z of v in Dn-1 and for each member y of Yv, add the edge (y, z). Then Dn is strongly connected by construction, and each vertex of Dn has outdegree exactly n. Every cycle in Dn corresponds to a cycle of the same parity in Dn-1, so Dn has no even cycles (because Dn-1 doesn’t by the induction hypothesis).

Now form the digraph En by reversing all edges of Dn, so each vertex of En has indegree exactly n. Form Gn by taking vertex-disjoint copies of En and Dn and adding all the edges (e, d) for each vertex e in En and d in Dn. Thus, each vertex of Gn has outdegree and indegree at least n. Gn has no even cycles because any cycle must lie entirely in one of its strong components, En and Dn, but neither of these has any even cycles.

Any cycle of a digraph lies in one of its stron