Dom, M: Recognition, Generation, and Application of Binary M

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