Recognition, Generation, and Application of Binary Matrices with the Consecutive-Ones Property

Vorschau

Inhaltsverzeichnis, Datei (54 KB)
Leseprobe, Datei (200 KB)

This thesis is about the computational complexity of several combinatorial problems closely related to the consecutive-ones property of binary matrices (0/1-matrices). Herein, a binary matrix has the consecutive-ones property (C1P) if there is a permutation of its columns that places the 1s consecutively in every row. The C1P has a long history and plays an important role in many applications, ranging from computational biology to railway optimization. This thesis aims, on the one hand, to investigate how the C1P can be established when a given binary matrix initially does not have this property, and, on the other hand, to analyze how the C1P and “relaxed” variants of the C1P can help to tackle matrix problems that are hard to solve in general. Apart from giving an overview on the C1P and its connections to graph theory and algorithmics, the thesis examines four problem complexes.

Finding small forbidden submatrices.
Here, one has given a binary matrix M without the C1P, and the task is to find a minimum-size submatrix of M that does not have the C1P. Such a submatrix is called a forbidden submatrix because it is a cause for the absence of the C1P in M. We show that a forbidden submatrix consisting of a minimum number of rows and columns can be found in polynomial time.

Obtaining the C1P by row or column deletions.
The problems of deleting a minimum number of rows or columns to transform a given matrix into a matrix with the C1P are called Min-COS-R and Min-COS-C, respectively. Both problems are known to be NP-hard even on very sparse matrices, containing only two 1-entries per row and at most three 1-entries per column. Our main results for these problems and their maximization versions are approximation and fixed-parameter algorithms for matrices that have only a bounded number of 1-entries per row.

Covering problems on input matrices with the C1P.
Here, we consider two variants of the subset selection problem Set Cover. Both of these two problems can be modelled as matrix problems and are NP-hard on general binary matrices; we investigate if they become polynomial-time solvable when some or all rows in the input matrix contain only one block of 1s each.

Rectangle stabbing in d dimensions.
(2-Dimensional) Rectangle Stabbing is a geometric problem where the input consists of a set of axis-parallel rectangles and a set of axis-parallel lines, and the task is to select a minimum number of the given lines to intersect every rectangle at least once. The generalization of this problem to d dimensions is called d-Dimensional Rectangle Stabbing. We show that for every d>=2 d-Dimensional Rectangle Stabbing is W¹-hard for the parameter “number of selected lines”. This result is complemented by fixed-parameter algorithms for several restrictions of (2-Dimensional) Rectangle Stabbing.

Parts of the thesis have already been published in the journal “Journal of Discrete Algorithms” and in the proceedings of the conferences “4th Annual Conference on Theory and Applications of Models of Computation (TAMC ’07)”, “3rd Algorithms and Complexity in Durham (ACiD ’07) Workshop”, “2nd International Frontiers of Algorithmics Workshop (FAW ’08)”, and “3rd International Workshop on Algorithms and Computation (WALCOM ’09)”.