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

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

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.