In contrast, the problem of deciding whether the optimal solution for a x has cost exactly k is not necessarily in NP; however, for X NPO it always belongs to a class called DP, which is a subset of PNP [Pap94]. 8 Although both problems Vertex Cover II and Vertex Cover III can be solved by using polynomially times an algorithm for Vertex Cover (both Vertex Cover II and Vertex Cover III, as well as all problems in NPO, belong to FPNP ), there is a slight dierence between the complexities of these two problems: While in the case of Vertex Cover II (and, by
Cover: just check whether the vertex cover returned by M has a size of at most k. Such optimization problems are called NP-hard,9 and, again, we cannot hope to nd polynomial-time algorithms for them. The fact that algorithms for NP-complete problems can be used to solve problems in FNP and in NPO and vice versa is also expressed in the following notion: Vertex Cover, Vertex Cover II, and Vertex Cover III, as well as all other NP-complete decision problems and all NP-hard problems in FNP and NPO are called polynomially equivalent, meaning that, on the one hand, they are not expected to be polynomial-time solvable, but, on the other hand, if one of these problems turns out to be polynomial-time solvable, then the other problems are polynomial-time solvable, too.10
Ways to Cope with NP-hard Problems
As mentioned in the previous section, it seems impossible to nd exact algorithms that solve NP-hard problems eciently, that is, in polynomial time. However, many problems of high practical relevance are NP-hard [GJ79, Pap97], and so there have been developed several ways to cope with these problems. The most common concepts to this end are heuristics, approximation algorithms, and xed-parameter algorithms. For the sake of completeness, we also mention the concept of randomized algorithms, which at rst sight also seems to be an appropriate tool to handle problems that are too dicult to be solved exactly within a reasonable amount of time. However, from the theoretical point of view, randomized algorithms could so far not obtain satisfying results for exactly solving NP-hard problems. Roughly speaking, heuristics are algorithms that work well for many instances of a problem, but not for all. Approximation algorithms are algorithms for optimization problems that do not solve the problem exactly, but compute a solution
denition, all problems in FNP) the correctness of a solution can be checked deterministically in polynomial time, we do not have any polynomial-checkable witness for the correctness of a solution for Vertex Cover III, because it is not clear how to prove its minimality (see footnote 7 on page 16). In fact, the existence of such a witness would imply that the complexity classes NP and coNP (the class of problems having polynomial-time checkable witnesses for noinstances) coincide, which is considered unlikely. 9 There are other notions of hardness (FNP-hardness, FPNP -hardness) that would be more meaningful here, see footnote 6 on page 15. 10 This polynomial equivalence also includes all problems that are complete for the classes coNP, DP, PNP , and FPNP.

If, in addition, (x ) (x), then the problem kernel is called proper [AF06]. The reverse direction of this statement also holds: If there is an algorithm A that solves a problem (X, ) in f ((x)) |x|c time for some constant c, then the following data reduction rule yields a problem kernel of size f ((x)): If f ((x)) |x|, then solve x in f ((x)) |x|c |x|c+1 time by using A. Otherwise return x, whose size is at most f ((x)). 17 There exist other reduction rules that even yield a linear number of vertices for Vertex Cover with parameter k [ACF+ 04, AFLS07, BG93, CFJ04, CKJ01, Fel03, Khu02, NT75].
Figure 1.5: Parameterized reduction from (X, 1 ) to (Y, 2 ). An instance x with parameter k := 1 (x) is transformed within g(k) |x|O(1) time into an instance y with parameter k := 2 (y). The parameter k must only depend on k, but not on |x|. In contrast, the size of y is only bounded by the time needed for the reduction, that is, by g(k) |x|O(1). As a second example for a problem with a kernel, consider the problem of separating points in the plane with axis-parallel linesthis problem was introduced in Section 1.1. Formulated as a decision problem, the question is whether one can separate all given points by inserting at most k axis-parallel lines. The argumentation that leads to the problem kernel is quite simple: With k lines, the plane can be divided into at most k/2 k/2 areas. Hence, if there are more than k/2 k/2 points, the answer must be no. The point separation problem, therefore, has a quadratic kernel with respect to the parameter k = maximum number of line insertions. Unfortunately, there are also parameterized problems that seem not to be xed-parameter tractable. In analogy to the concept of NP-hardness in the classical complexity theory, there is a hardness predicate for parameterized problems, which is based on reductions between parameterized problems. The idea is, in analogy to the denition of NP-hardness, to dene a class that contains many of these dicult problems and to call a problem Y hard if it is at least as hard as all problems in this class, meaning that all problems in this class can be reduced to Y and thus be solved by any algorithm for Y. While in the case of decision problems in classical complexity theory a polynomial-time reduction from a problem X to a problem Y allows to solve X in polynomial time by using a (ctive) polynomial-time algorithm for Y , a reduction from a parameterized problem (X, 1 ) to a parameterized problem (Y, 2 ) as we need it here has to allow for solving a problem X in FPT time by using a (ctive) FPT algorithm for Y. Hence, a parameterized problem (X, 1 ) is parameterized reducible to a parameterized problem (Y, 2 ), denoted by (X, 1 ) FPT (Y, 2 ), if there are two computable functions f, g : and an algorithm which transforms an instance x of X into an instance y of Y in g(1 (x)) |x|O(1) time such that 2 (y) = f (1 (x)) and y is a yes-instance of Y i x is a yes-instance of X. See Figure 1.5 for an illustration. Note that the polynomial-time reduction from Vertex Cover to Independent Set described in Section 1.3.1 is not a parameterized reduction for the parameters size of the desired vertex cover and size of the desired independent set, respectively: The size of the independent set does not only depend on the size of the vertex cover, but also on the number of all vertices in the input

circular-arc

quasi Circ1P [Tuc71] Circ1P [Tuc71]

Circ1P

Helly circular-arc

quasi Circ1P C1P

Circ1P [Gav74]

interval

C1P [FG65]
proper / unit interval circular convex bipart.

C1P [Rob69]

C1P r+c [Fis85]

convex bipart.

C1P (per def.)

biconvex bipart.

C1P r+c (per def.)
v1 v2 v3 v4 v5 v6 v7 v1 v2 v3 v0 1
v3 v 6 v1 v10 v 13 v9 v12 v11 v 14 v2 v5 v4 v 7 v8
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14
Figure 2.6: Top: A graph that is a union of vertex-disjoint paths, and its edgevertex incidence matrix. Bottom: A graph that is a union of vertex-disjoint caterpillars, and its vertex-edge incidence matrix. Both matrices have the C1P. For example, every cycle of length at least six contains several asteroidal triples. More examples for graphs containing asteroidal triples are shown in Figure 2.7. In his characterization, Tucker does not use the term convex bipartite graph; however, convex bipartite graphs are identical to graphs with a V2 -consecutive2 arrangement. The following two theorems, hence, characterize convex bipartite graphs. Theorem 2.3 ([Tuc72, Theorem 6]). A bipartite graph G = (V1 , V2 , E) has a V2 -consecutive2 arrangement if and only if V2 contains no asteroidal triple of G. Theorem 2.4 ([Tuc72, Theorem 7]). In a bipartite graph G = (V1 , V2 , E) the vertex set V2 contains no asteroidal triple2 if and only if G contains none of the graphs GIk , GIIk , GIIIk (with k 1), GIV , and GV as shown in Figure 2.7.
Tucker considers the C1P for columns, whereas we are interested in the C1P for rows. Hence, the roles of V1 and V2 are interchanged here compared to Tuckers publication [Tuc72].

GIk : GIIk :

GIIIk :
Figure 2.7: Forbidden induced subgraphs due to Tucker [Tuc72]: The vertex set V2 of a bipartite graph G = (V1 , V2 , E) contains an asteroidal triple i G contains one of the displayed graphs as an induced subgraph, where white vertices correspond to vertices in V2. The numbers k and k +1 refer to the number of black vertices in the lower parts of the rst three graphs. In the case of the graph GIk T , every triple of white vertices is an asteroidal triple. In all other cases, there is exactly one asteroidal triple consisting of white vertices; this triple is denoted by x, y, z. A characterization that is very similar to the one given in Theorem 2.3 is also known for interval graphs: A graph is an interval graph i it is chordal and contains no asteroidal triple [LB62]. The following theorem, which nally characterizes matrices with the C1P, is a direct consequence of Theorems 2.3 and 2.4. Theorem 2.5 ([Tuc72, Theorem 9]). A matrix M has the C1P if and only if it contains none of the matrices MIk , MIIk , MIIIk (with k 1), MIV , and MV as shown in Figure 2.8 as a submatrix.3 The matrices in Figure 2.8 are obtained from the graphs given in Figure 2.7 by considering the half adjacency matrices of these graphs, that is, the graphs given in Figure 2.7 are the representing graphs of the matrices given in Figure 2.8. We will use the symbol T throughout the whole thesis to denote the set of matrices MIk , MIIk , MIIIk (with k 1), MIV , and MV given in Theorem 2.5. The set T is called a set of forbidden submatrices for the C1P.

The roles of rows and columns are interchanged here compared to Tuckers publication [Tuc72].

k+3 k+2 k+3

1 MIk , k 1

0 0 MIIk , k 0

0 MIIIk , k 1
Figure 2.8: The forbidden submatrices for the C1P due to Tucker [Tuc72], given in Theorem 2.5.

Recognizing the C1P

Here we demonstrate some of the most prominent algorithms known for recognizing matrices with the C1P. Hand in hand with these algorithms, several characterizations for matrices having the C1P have been developed; we will also present some of these characterizations. Moreover, we x a small error in Theorem 6.1 of [McC04]. As we will see (Theorem 2.7), every algorithm that recognizes interval graphs can also be used to recognize matrices with the C1P. However, here we mention only those results that explicitly deal with matrices and the C1P, because rst transforming a matrix into a graph and then testing whether this graph is an interval graph does not automatically yield an ecient (that is, linear-time) algorithm for recognizing the C1P. Note that some of the presented results concern the C1P for rows and some the C1P for columns; clearly, due to the symmetry of these two properties, all algorithms can be used for recognizing both of these properties. The following denition introduces some terms needed in this section. Denition 2.9. Two columns c1 , c2 of a 0/1-matrix overlap if there exist three rows r1 , r2 , r3 such that row r1 contains a 1 in both columns c1 and c2 , row r2 contains a 1 in c1 but not in c2 , and row r3 contains a 1 in c2 but not in c1. A column c1 contains a column c2 if for every row r it holds that if c2 has a 1 in row r then c1 also has a 1 in row r. If a column is not contained in any other row, it is maximal.4 All terms can be dened analogously for rows.
Note that this denition of a maximal column does not allow the existence of two identical maximal columns.

2.3. Recognizing the C1P

Using overlapping columns. The rst polynomial-time algorithm to recognize matrices having the C1P (for columns) was presented by Fulkerson and Gross [FG65]. Their idea is to decompose the input matrix M into disjoint column sets in such a way that the whole matrix has the C1P for columns i each matrix induced by one of the column sets has the C1P for columns. The partitioning of Ms columns into dierent column sets is performed by dening an overlap graph G(M): Every vertex of this graph corresponds to a column of M, and two vertices are connected i their corresponding columns overlap. Every connected component of this graph denes one column set of the partition of M needed by the algorithm. Now, for the rows of every submatrix of M that is induced by one of the column sets of the partition, a C1-ordering can easily be found, if existing, by considering one column after the other in a certain order and re-arranging the rows if necessary. If, however, the considered submatrix does not have the C1P for columns, this can easily be detected because in this case one always encounters a column whose 1-entries cannot be placed consecutively without destroying the C1P for columns in the already considered columns. In the last phase of the algorithm, the row orderings computed for the submatrices are combined, while possibly re-arranging some of the rows, by using a directed graph called the component graph D(M), which denes a partial order on the connected components of G(M). The whole matrix M has the C1P for columns i all of the submatrices have the C1P for columns [FG65, Theorem 4.1]. The whole procedure takes polynomial time. A more recent linear-time algorithm by Hsu [Hsu02] for recognizing the C1P is based on very similar ideas. PQ-Trees. Booth and Lueker were the rst to present a linear-time algorithm for recognizing matrices with the C1P for columns [BL76]. Linear time means a running time that is linear in the number of rows plus the number of columns plus the number of 1-entries of the given matrix. Booth and Lueker introduced so-called PQ-Trees, which are not only useful for recognizing matrices with the C1P, but also, for example, for recognizing matrices with the Circ1P and for recognizing interval graphs and planar graphs. In the context of recognizing matrices with the C1P for columns, a PQ-tree is an ordered rooted tree that represents a C1-ordering for the rows of a matrix M. To this end, the inner nodes of the PQ-tree are labeled as P-nodes and Q-nodes, and the leaves oneto-one correspond to the rows of the underlying matrix M. Ordering the rows of M in the same way as their corresponding leaves in the PQ-tree yields the strong C1P for columns. In addition, any PQ-tree for M implicitly represents all possible C1-orderings for Ms rows, because by applying a series of certain node reordering operations, every possible PQ-tree for the set of Ms rows can be transformed into any other possible PQ-tree for this row set. Therefore, PQ-trees have the following properties. 1. If T is a PQ-tree for a matrix M, then the sequence of T s leaves from left to right describes a C1-ordering for Ms rows.

y x z Let pxyz := |PGM (y, z)|+|PGM (x, z)|+|PGM (x, y)|. By considering the asteroidal triples in the graph types GIk GV (Figure 3.3) one can verify that

pxyz pxyz pxyz pxyz pxyz

= 2k + 7 = 2k + 9 = 2k + 13 = 21 = 13

if if if if if

M M M M M
= MIk , = MIIk , = MIIIk , = MIV , and = MV.
y x For example, if M = MIIIk , then |PGM (y, z)| = 2k + 3, |PGM (x, z)| = 5, and z |PGM (x, y)| = 5, and, hence, pxyz = (2k + 3) + 5 + 5 = 2k + 13. Let u, v, w C be the vertices chosen in line 6 of the algorithm, and let puvw := u v w |PG (v, w)| + |PG (u, w)| + |PG (u, v)|. Clearly, puvw pxyz because u, v, w are u v w selected such that |PG (v, w)| + |PG(u, w)| + |PG (u, v)| is minimized. The returned submatrix consists of at most (puvw 3)/2 (pxyz 3)/2 rows because each of the vertices u, v, w is counted twice in puvw and because every second vertex u v w in each of the vertex sets PG (v, w), PG (u, w), PG (u, v) corresponds to a column
in M. It follows that the row number of the submatrix returned by the algorithm is upper-bounded by ((2k + 7) 3)/2 = k + 2 = m ((2k + 9) 3)/2 = k + 3 = m ((2k + 13) 3)/2 = k + 5 = m + 3 (21 3)/2 = 9 = m + 5 (13 3)/2 = 5 = m + 1 if if if if if M M M M M = MIk (where m = k + 2), = MIIk (where m = k + 3), = MIIIk (where m = k + 2), = MIV (where m = 4), and = MV (where m = 4).
With a completely analogous argumentation it follows that the column number of the submatrix returned by the algorithm is upper-bounded by ((2k + 7) 3)/2 = k + 2 = n ((2k + 9) 3)/2 = k + 3 = n ((2k + 13) 3)/2 = k + 5 = n + 2 (21 3)/2 = 9 = n + 3 (13 3)/2 = 5 = n if if if if if M M M M M = MIk (where n = k + 2), = MIIk (where n = k + 3), = MIIIk (where n = k + 3), = MIV (where n = 6), and = MV (where n = 5).
To see the claimed running time, note that lines 25 can be executed in O(n2 (n + m)) time by using breadth-rst search (running on a graph G = (V, E) in O(|V | + |E|) time [CLRS01]) in line 5: the number of vertices in C is n, and the input graph Gu for the breadth rst search has m + n vertices and at most m edges. For considering all triples u, v, w in line 6, the algorithm needs O(n3 ) time. The test in line 9 can be executed in linear time (see Section 2.3), that is, in O(m + n + m ) time, and, hence, the time needed for lines 910 is dominated by the time needed for lines 18.
Exact Algorithms for Finding MinimumSize Forbidden Submatrices
In the previous section, we have seen how to nd a forbidden submatrix whose number of rows and columns is close to be minimum. Now we turn our attention to the problem of nding a forbidden submatrix from T whose number of rows, columns, rows and columns, or entries is actually minimum, at the cost of an increased running time compared to the procedure presented in the previous section. We rst present in Section 3.3.1 two rather straightforward brute-force approaches, which are able to nd any submatrix in a given matrix. These algorithms are ecient for nding submatrices of the types MIV and MV and for nding any submatrix from T in (, )-matrices where is small compared to the number of columns. In Section 3.3.2 we show how to nd submatrices of the types MIk , MIIk , and MIIIk in polynomial time even in matrices with a large number of 1s per row. Finally, in Section 3.3.2 we combine the algorithms of Sections 3.3.1 and 3.3.2.

The C1P being a desirable property that often leads to ecient algorithms, the natural problem arises what to do if a given matrix does not have the C1P. As a consequence, there has been recently increased interest in matrix modication problems that deal with the transformation of a given 0/1-matrix into a 0/1matrix fullling the C1P [HG02, TZ07]. Applications for problems of this kind can also be found in computational biology [ABH98, AM96, GGKS95, LH03, WR00], see Section 1.1. The following two minimization problems show up naturally in this context:
: Given a binary matrix M, nd a minimum-cardinality set of columns to delete such that the resulting matrix has the C1P.
Given a binary matrix M, nd a minimum-cardinality set of rows to delete such that the resulting matrix has the C1P. 79
Chapter 4. The C1P Submatrix Problem
These problems can also be posed as decision problemsin that case, the input does not only consist of a matrix M, but it contains also a positive integer d and the question is whether M can be transformed into a matrix having the C1P by deleting at most d columns or rows, respectively. We will use the problem names Min-COS-C and Min-COS-R for the minimization problem as well as for the corresponding decision problem. In addition to the two minimization problems dened above, we will also consider the maximization duals of Min-COS-C and Min-COS-R:
: Given a binary matrix M, nd a maximum-cardinality set of columns that induces a matrix having the C1P.
: Given a binary matrix M, nd a maximum-cardinality set of rows that induces a matrix having the C1P.
Again, we use the names Max-COS-C and Max-COS-R for both the optimization and the decision versions of the problems. In case of the decision versions, we ask whether there is a column set or a row set, respectively, that induces a matrix with the C1P and whose cardinality is greater than or equal to a given value d. Note that we will always use d to denote the number of columns or rows to be deleted when considering Min-COS-C or Min-COS-R, and d to denote the number of columns or rows to be selected when considering Max-COS-C or Max-COS-R. Concerning the computational hardness of these problems in the classical complexity theory, it makes obviously no dierence if one considers Min-COSC (Min-COS-R) or Max-COS-C (Max-COS-R): the optimum solution for the maximization problem can be directly derived from the optimum solution for the minimization problem and vice versa. However, the approximability of the minimization and the maximization problems may dier, and also from the parameterized point of view it makes a dierence if one considers the problems Min-COS-C and Min-COS-R, where the standard parameter would be d, or the problems Max-COS-C and Max-COS-R with the standard parameter d. Whereas previous work [Haj00, HG02, TZ07] focussed on the maximization versions, here we mainly concentrate on the minimization versions of the problems. In particular, from the parameterized point of view and when expecting that large submatrices with the C1P exist, this appears to be the more natural optimization criterion. Unfortunately, even for sparse matrices with few 1-entries, as they occur in many applications [AM96, DER89, KS96, TZ07, WR00], both the maximization and minimization problems quickly become NP-hard [HG02, TZ07]. In this chapter, we therefore explore the algorithmic complexity of these problems in a more ne-grained way, providing new algorithmic results. To this end, based on the forbidden submatrix characterization for the C1P (Theorem 2.5) due to Tucker [Tuc72], our main technical result is a structural theorem dealing with the selection of particularly useful forbidden submatrices.

Maximization on (, 2)- and (2, )-Matrices
In this section, we present a polynomial-time approximation and a xed-parameter algorithm for Max-COS-R on (, 2)-matrices and a xed-parameter algorithm for Max-COS-C on (2, )-matricesfor the latter problem, a polynomialtime approximation was already known [TZ07]. Like in the previous section, we use the equivalence between these two problems and the graph problems MaxWEIDPS and Max-WEIDCatS.
Max-COS-R on (, 2)-Matrices
Max-COS-R on (, 2)-matrices is equivalent to Max-WEIDPS (see Section 4.2). Therefore, to achieve the mentioned results for the former problem, it suces to nd a polynomial-time approximation and a xed-parameter algorithm for Max-WEIDPS. Approximation algorithm. We show that Max-WEIDPS can be approximated in polynomial time with a factor of 3/4, which immediately implies that Max-COS-R on (, 2)-matrices is approximable with the same factor. For approximating Max-WEIDPS, we use a part of an algorithm of Serdyukov [Ser84] (see [BGS02, HR00] for descriptions of the algorithm in English language), which approximates the problem Max-TSP with a factor of 3/4 in O(|V |3 ) time.
Input: A complete graph G = (V, E), in which every edge e E has a nonnegative weight w(e). Task: Find a cycle of maximum weight that contains every vertex from V exactly once. Serdyukovs algorithm works on complete graphs, and as an intermediate step it produces a set of vertex-disjoint paths. The idea for approximating MaxWEIDPS is, therefore, to construct for a given instance (G, w) an edge-weighted complete graph G such that every set of vertex-disjoint paths in G one-to-one corresponds to a set of vertex-disjoint paths of the same weight in the original graph G. On this modied instance, we run the rst phase of the algorithm of Serdyukov, which outputs a set of vertex disjoint paths whose weight is at least 3/4 times the weight of an optimal solution for Max-WEIDPS. More precisely, for a given instance (G, w) of Max-WEIDPS, we construct an instance (G = (V, E ), w ) of Max-TSP, where G is the complete graph with vertex set V and where the weight of every edge {u, v} E is given by w ({u, v}) = w({u, v}) 0 if {u, v} E if {u, v} E. /
It is obvious that if there is a subgraph H of G that consists of vertex-disjoint paths and has weight d , then there is also a subgraph H of G consisting of vertexdisjoint paths and having weight d : To obtain H, just remove all edges from H that do not exist in Gthe weight of these edges is 0. The approximation algorithm of Serdyukov for Max-TSP constructs two or three (depending on whether |V | is even or odd) subgraphsso-called partial tours, which consist of vertex-disjoint paths. Out of these partial tours the algorithm selects one with maximum weight and extends it to a cycle of length |V | by adding some edges, which is always possible because the input graph is complete. The approximation factor of 3/4 is shown by proving that the weight of at least one of the partial tours is at least 3/4 times the weight of an optimal solution for Max-TSP [Ser84]. Clearly, the weight of an optimal solution for Max-WEIDPS on (G , w ) is a lower bound for Max-TSP on (G , w ) because every set of vertex-disjoint paths can be completed to a cycle of length |V |. Therefore, Serdyukovs algorithm always nds a set of vertex-disjoint paths whose weight is at least 3/4 times the weight of an optimal solution for Max-WEIDPS on (G , w ). As argued above, from this set of paths we can directly obtain a set of vertex-disjoint paths in G having the same weight, which yields the following result. Theorem 4.4. Max-WEIDPS can be approximated in O(|V |3 ) time with a factor of 3/4. With the equivalence between Max-COS-R on (, 2)-matrices and MaxWEIDPS and since the edge-weighted complete graph G can be constructed in O(mn) time for a given m n matrix, we obtain the following corollary.

in all rows ri with i ({1,. , k + 1} R) ({k + 2, k + 3} \ R). It is easy to see that complementing these rows in M results in the described matrix, proving the claim. See Figure 4.8 for an illustration of the claim. We return to the proof of Case 5. The matrix B together with a 0-column has been created by complementing a subset of the rows belonging to B. Applying the above claim, regarding B together with the 0-column as the matrix M mentioned in the claim, shows that there is a column cj in A such that complementing all rows that contain a 1 in column cj results in an MIk+1 and a 0-column. Then, A must contain a submatrix from X as we have shown in Case 3 and Case 4. Case 6: The submatrix B is isomorphic to MIIIk with k 1. Similarly to Case 5, this case can be reduced to Case 3 or Case 4 by applying the following claim, which reveals the relationship between matrix types MIIIk and MIk. This claim can be proven in analogy to the claim in Case 5. Claim: For an integer k 1, let M = MIIIk , and let M be any matrix resulting from M by complementing a subset of its rows. Then, complementing all rows of M that have a 1 in column ck+3 results in a (k + 2) (k + 3) matrix containing MIk and an additional 0-column.
We have presented a systematic analysis of the complexity of various restricted variants of the in general NP-hard problems Min-COS-C, Min-COS-R, MaxCOS-C, and Max-COS-R. Besides hardness for some of the problem variants, we could achieve polynomial-time approximation algorithms and exact xedparameter algorithms in many cases. In addition, our algorithms for Min-COSC and Min-COS-R on (, )-matrices can easily be adapted to work for the problem of deleting a minimum number of rows and columns. However, there remain questions unanswered: Our main results focus on Min-COS-C and MinCOS-R with a restricted number of 1s per row, but no restriction on the number of 1s in the columns; similar studies would be desirable for the case that we have a restricted number of 1s per column, but no restriction for the rows. Moreover, it should be investigated whether the running times for Min-COS-R and Max-COS-C (see Table 4.4) can be improved. In particular, we think that approximating Min-COS-R with a factor of + 1 should be possible within a running time that is polynomial in the input size and has no exponential factor depending on. An interesting research direction is also to consider the problem Min-CO-1E (ipping a minimum number of 1-entries). We conjecture that for (, )-matrices the presented approximation and xed-parameter tractability results for Min-COS-C should extend to Min-CO-1Ehowever, we could not prove that (the reason is that, in the case of Min-CO-1E, we have no statements similar to Lemmas 4.4 and 4.5). Only for = 2 we have algorithmic results simply based on the equivalence to Min-COS-R in this case.

1: S := ; Cblue := Cblue ; 2: while Cblue = : { 3: C := set from Cblue with minimum right index; 4: S := S {srx(C) }; 5: Cblue := Cblue \ {C Cblue : C S = }; } 6: return S ;
Theorem 5.2. For MDH with C1P, the greedy algorithm approximates an optimal solution within an additive term of one in O(|S| |Cblue |) time, provided that the elements in S are sorted such that all subsets in Cblue have the C1P. Proof. Obviously, the output S of the greedy algorithm has the minimum overlap property. It is also clear that the algorithm runs in O(|S||Cblue|) time. It remains to determine max{|C S | | C Cred }. Let Cmax denote one subset in Cred with |Cmax S | = max{|C S | | C Cred }. Due to the C1P, all sets C chosen in step 3 are pairwise disjoint, and, hence, the set Cmax contains at least |Cmax S | 1 pairwise disjoint sets from Cblue as subsets. This implies that any solution for this instance has to contain at least |Cmax S | 1 elements from Cmax to satisfy the minimum overlap property for these pairwise disjoint Cblue -sets. Therefore, |Cmax S opt | |Cmax S | 1 for any optimal solution S opt.
Dynamic Programming for Red-Blue Set Cover
In the case of RBSC with C1P, we do not know an ILP formulation whose coecient matrix is totally unimodular. We present a polynomial-time dynamic programming algorithm that solves the optimization version of Red-Blue Set Cover with C1P: Given S, Cblue , and Cred , nd a subset S S with S C = for all C Cblue which minimizes |{C Cred | S C = }|. We assume that the sets in Cblue are ordered according to their left indices and denote them with B1 ,. , B|Cblue | ; the sets of Cred are ordered analogously and denoted with R1 ,. , R|Cred |. If a set in Cblue is a superset of another set in Cblue , it can be removed. Therefore, for any two sets Bi , Bj Cblue it holds that lx(Bi ) < lx(Bj ) rx(Bi ) < rx(Bj ). Given a subset S S, we denote with w(S ) the number of sets from Cred that are covered by S . The idea of the dynamic programming algorithm is to compute so-called optimal partial solutions Sopt (i1 , i2 , j). Each optimal partial solution Sopt (i1 , i2 , j) has the following properties: 1. Sopt (i1 , i2 , j) {s1 ,. , si1 }, 2. Sopt (i1 , i2 , j) covers all sets B1 ,. , Bj , 3. if i2 > 0, then Sopt (i1 , i2 , j) contains at least one element from {si2 ,. , sn } (where n := |S|), and 4. the cost w(Sopt (i1 , i2 , j)) is minimum under all subsets of S that have the rst three properties. A subset of S that has the rst three properties is called a feasible partial solution. The algorithm uses a three-dimensional table Sopt (i1 , i2 , j) with 1 i1 n, 0 i2 n, and 1 j |Cblue | for storing optimal partial solutions, and a table Wopt (i1 , i2 , j) of the same size where the cost of every optimal partial solution is stored. Then, the entry Sopt (n, 0, |Cblue |) contains an optimal solution for the RBSC instance. The two tables are lled with three nested loops, iterating over i1 , i2 , and j. To compute table entries Sopt (i1 , i2 , j), Wopt (i1 , i2 , j) with i1 = 1 is simple. All other entries are computed as follows: If lx(Bj ) > i1 or i2 > i1 , then there is no partial solution Sopt (i1 , i2 , j), and Wopt (i1 , i2 , j) is set to. Otherwise, we consider two cases: the optimal partial solution contains si1 or not. (Note that if i2 = i1 , then all feasible partial solutions have to contain si1.) In the rst case, the optimal partial solution Sopt (i1 , i2 , j) can only contain elements from {s1 ,. , si}, and, hence, Sopt (i1 , i2 , j) = Sopt (i1 1, i2 , j). In the second case, the optimal partial solution Sopt (i1 , i2 , j) is computed as follows: By choosing si1 , property 3 is clearly

A geometric covering problem, in the broadest sense, consists of a set of geometric objects and a set of resources; the goal is to nd a small set of resources that covers all the objects. Geometric covering problems arise in many practical applications (for example, train station location, reducing interference in cellular networks) and are subject of intensive research (see [AS98, CV07, GKW08, KMN05, KN96, LM05, MT82, Nus97, Seg99, SW96] and the references given below). In this chapter, we consider the following problem. 139
Chapter 6. Rectangle Stabbing
Figure 6.1: Left: An instance of (2-Dimensional) Rectangle Stabbing, consisting of a set of axis-parallel rectangles and a set of axis-parallel lines. Right: An instance of 3-Dimensional Rectangle Stabbing, consisting of a set of axis-parallel boxes and a set of axis-parallel planes. d Input:
A set R of axis-parallel d-dimensional hyperrectangles, a set L of axis-parallel (d 1)-dimensional hyperplanes, and a positive integer k. Question: Is there a set L L with |L | k such that every hyperrectangle from R is intersected by at least one hyperplane from L ?
In the case d = 2, the set R consists of axis-parallel rectangles in the plane, and L consists of vertical and horizontal lines; we call this variant Rectangle Stabbing for short. Since even the case d = 2 is NP-hard (see [GIK02, MSW05]), d-Dimensional Rectangle Stabbing is clearly NP-complete for every constant d 2. In the polynomial-time approximation setting, the optimization version of d-Dimensional Rectangle Stabbing is considered, which asks for a minimum-cardinality set L L to cover all hyperrectangles from R. See Figure 6.1 for examples. Applications of d-Dimensional Rectangle Stabbing range from radiotherapy [HM91] to embedded sensor networks, spatial data organization, and statistical analysis [CDKW05, KSPS02] (see also Section 1.1). Moreover, the problem of stabbing arbitrary connected closed shapes (instead of rectangles) in the plane with axis-parallel lines can easily be reduced to (2-Dimensional) Rectangle Stabbing by replacing each shape by its bounding box (that is, by the smallest possible rectangle containing the shape). Similarly, the stabbing problem where only the rectangles in the plane are given and k horizontal and vertical lines shall be inserted that stab all rectangles is equivalent to Rectangle Stabbing: To transform an instance of the former problem into an instance of Rectangle Stabbing, insert a set of O(|R|) lines. For each given rectangle,
6.1. Introduction and Overview
this set contains four lines: two horizontal lines going through the upper and lower boundary of the rectangle, and two vertical lines going through the left and right boundary of the rectangle. To reduce in the other direction, shrink each rectangle until each of its boundaries coincides with a line, and remove all lines. Concerning d-Dimensional Rectangle Stabbing and its variants, the literature so far mainly considers polynomial-time approximability. Hassin and Megiddo [HM91] give a factor-d2d1 approximation for stabbing d-dimensional, identical objects (that is, translates of one object) with axis-parallel lines in ddimensional space. Gaur et al. [GIK02] describe a factor-d approximation for d-Dimensional Rectangle Stabbing; the two-dimensional case Rectangle Stabbing, hence, can be approximated with a factor of two. A similar result was obtained by Mecke et al. [MSW05]; they give a factor-d approximation algorithm for Set Cover, restricted to instances whose matrix representations have at most d blocks of 1s per row. This restricted variant of Set Cover, which we call d-C1P-Set Cover, is a generalization of d-Dimensional Rectangle Stabbing (see Section 6.2). The factor-d approximation also works for the weighted version of d-C1P-Set Cover [MSW05]. Weighted and capacitated versions of d-Dimensional Rectangle Stabbing have been considered by Even et al. [ELR+ 08] and by Xu and Xu [XX07], also leading to several approximation algorithms. A restricted, but still NP-complete variant of (2-Dimensional) Rectangle Stabbing is called Interval Stabbing; here, every rectangle in the input is intersected by at most one horizontal line, but arbitrarily many vertical lines (that is, every rectangle is just a horizontal interval in the plane). Kovaleva and Spieksma [KS01, KS06] give constant-factor approximation algorithms for several variants of Interval Stabbing. Approximation algorithms for the more general variant of Interval Stabbing where the input contains horizontal and vertical intervals have been developed by Hassin and Megiddo [HM91]. Surprisingly, there are no results concerning the xed-parameter tractability of d-Dimensional Rectangle Stabbing. In this chapter, therefore, we study d-Dimensional Rectangle Stabbing from the viewpoint of parameterized complexity. More specically, we analyze whether d-Dimensional Rectangle Stabbing is xed-parameter tractable with respect to the parameter k = solution size, that is, whether there is an algorithm running in f (k) |R L|O(1) time. On the one hand, we show in Sections 6.3 and 6.4 that for d 3 and d = 2, respectively, the problem is W[1]-hard with respect to the parameter k, which presumably means that there is no such algorithm. On the other hand, we consider several natural restrictions of the case d = 2 in Section 6.5 and show them to be xed-parameter tractable with respect to the parameter k. Note that the known reductions proving the NP-hardness of Rectangle Stabbing and d-Dimensional Rectangle Stabbing [GIK02, MSW05] do not show the W[1]-hardness of these problems.

A graph G = (V, E) is called k-colorable if there is a function c : V {1,. , k} satisfying {u, v} E : c(u) = c(v); the function c is then called a proper vertex k-coloring for G. To achieve our hardness results in Sections 6.3 and 6.4, we consider d-Dimensional Rectangle Stabbing as a restriction of the problem Set Cover, which we introduced in Section 2.5:
Input: A binary matrix M and a positive integer k. Question: Is there a set C of at most k columns of M such that the submatrix M of M that is induced by these columns has at least one 1 in every row? To introduce our restricted versions of Set Cover, we need the following denitions. Denition 6.1. 1. A binary matrix M has the d-consecutive-ones property (d-C1P) if in every row of M there are at most d blocks of 1s. 2. A binary matrix M with columns c1 ,. , cn has the separated d-consecutiveones property (d-XC1P) if M can be split into submatrices M1 ,. , Md such that M = (M1 | M2 |. | Md ) and each Mi with i {1,. , d} has the strong C1P; that is, the columns of M can be partitioned into d sets of consecutive columns C 1 = {c1 ,. , cj1 }, C 2 = {cj1 +1 ,. , cj2 },. , C d = {cjd1 +1 ,. , cn } such that for every i {1,. , d} the submatrix of M induced by C i has at most one block of 1s per row. See Figure 6.2 for an illustration for the d-C1P and d-XC1P.1 If Set Cover is restricted by demanding that the input matrix M must have the d-C1P, then we call the resulting problem d-C1P-Set Cover; if M must have the d-XC1P, then we call the resulting problem d-XC1P-Set Cover. Observation 6.1. The problems d-Dimensional Rectangle Stabbing and d-XC1P-Set Cover are equivalent: There are two polynomial-time reductions, one from d-Dimensional Rectangle Stabbing to d-XC1P-Set Cover and one from d-XC1P-Set Cover to d-Dimensional Rectangle Stabbing,
To be consistent with the terms C1P, strong C1P, Circ1P, and strong Circ1P, it would be more appropriate to call the properties introduced in Denition 6.1 strong d-C1P and strong d-XC1P instead of just d-C1P and d-XC1P, respectively. However, we omit the attribute strong here because we assume that in this chapter the columns of every matrix are already ordered in an appropriate way. Note that it is NP-hard to nd a permutation of the columns of a binary matrix that minimizes the number of blocks of 1s per row [AM96, FGS96, GGKS95, WLZ07] (see also [BGRS04, WR00]), and it is also NP-hard to nd a permutation that minimizes the total number of blocks of 1s [GJ79, Had02] (see also [HL08]).

158 Input:

Rh : a set of axis-parallel rectangles with bounded height, Rv : a set of axis-parallel rectangles with bounded width, H, V : a set of horizontal lines and a set of vertical lines, kh , kv : nonnegative integers. Output: A subset of H V containing at most kh lines from H and at most kv lines from V that stabs all rectangles from Rh Rv , or null, if no such subset exists. 1: function stab(Rh , Rv , H, V, kh , kv ) { 0 2: if greedy(Rh , V, kv ) returns a set Rh Rh of rectangles: { if kh = 0: return null; 3: 0 4: for each rectangle r Rh : for each line h H that intersects r: { 5: Rh := Rh \ Rh (h); Rv := Rv \ Rv (h); H := H \ {h}; 6: A := stab(Rh , Rv , H , V, kh 1, kv ); 7: if A = null: return A {h}; } 8: return null; } 0 9: if greedy(Rv , H, kh ) returns a set Rv Rv of rectangles: { 10: if kv = 0: return null; 0 11: for each rectangle r Rv : for each line v V that intersects r: { 12: Rh := Rh \ Rh (v); Rv := Rv \ Rv (v); V := V \ {v}; 13: A := stab(Rh , Rv , H, V , kh , kv 1); 14: if A = null: return A {v}; } 15: return null; } 16: return the union V H of the solutions returned by the two calls (lines 2 and 9) of greedy(); } Figure 6.8: Branching algorithm for stabbing a set Rv Rh of rectangles with at most kv lines chosen from a given set V of vertical lines and at most kh lines chosen from a given set H of horizontal lines. For a line l, we denote with Rh (l) and Rv (l) the set of all rectangles in Rh and Rv , respectively, that are intersected by l. An entry in a row i and a column j of M is 1 i the edge ei is incident to the vertex corresponding to column j. Clearly M has the 2-XC1P with C 1 = {v1 , v2 ,. , vn } and C 2 = {xe1 , ye1 ,. , xem , yem }. Moreover, there are exactly two 1s in every column xe1 , ye1 ,. , xem , yem. Therefore, the matrix M can be transformed into an equivalent instance of the restricted variant of Rectangle Stabbing. Obviously, G has a vertex cover of size |E| + k i M has a solution of size |E|+k. We just mention in passing that this reduction also proves Corollary 1 of [MSW05] in an easier way. For the case b = 2, there is a simple k k nO(1) -time branching algorithm: In every node of the search tree, try to stab all rectangles while only using vertical linesto this end, use the greedy algorithm of Figure 6.4. If the greedy algorithm
does not return a solution but a set of k + 1 rectangles that cannot be stabbed with k vertical lines, then one has to select a horizontal line that intersects two of these rectangles. We can assume that the instance is reduced with respect to the data reduction rules described above, and, therefore, there can be at most k such lines. Branch on which of these lines should be taken into the solution. However, we do not know whether this algorithm can be generalized for the case b 3. Nevertheless, we show that the restriction of Rectangle Stabbing is xed-parameter tractable with respect to the combined parameters k and b by developing a problem kernel. First, in addition to the previously mentioned data reduction rules, we use the following data reduction rule: Rule 7: If there are bk + 2 rectangles r1 ,. , rbk+2 R such that for each i {1,. , bk + 1} it holds that every vertical line that intersects ri also intersects rbk+2 , then delete rbk+2. The correctness of this data reduction rule follows from the fact that k horizontal lines cannot intersect all rectangles r1 ,. , rbk+1. Hence, if the instance with rbk+2 deleted is a yes-instance, every solution must contain a vertical line stabbing some of the rectangles r1 ,. , rbk+1 , and this line also stabs rbk+2 in the original instance, which, therefore, is also a yes-instance. The following two observations are immediate consequences of Rule 7. Observation 6.5. For every rectangle r in a reduced instance there are at most bk rectangles r = r with lx(r ) lx(r) and rx(r ) rx(r). Observation 6.6. In a reduced instance, for every j {1,. , n} there are at most bk + 1 rectangles r with lx(r) = j. The observations made so far lead to the following correlation between the position of a rectangle and its maximum possible width: Lemma 6.3. For every rectangle r R in a reduced instance, rx(r) (bk + 1) lx(r). Proof. By induction on lx(r). For all rectangles r with lx(r) = 1, the lemma is true: Assume, for the sake of a contradiction, that there is a rectangle r with lx(r) = 1 and rx(r) > (bk + 1). Due to Observation 6.3, there must be a rectangle r with rx(r ) = p for every p {lx(r),. , rx(r) 1}. This means that there are at least bk + 1 rectangles r = r with lx(r ) lx(r) and rx(r ) rx(r), contradicting Observation 6.5. Now let j be an integer greater than 1 and assume the lemma to be true for all rectangles r with 1 lx(r) j. Let r be a rectangle with lx(r) = j + 1, and assume, for the sake of a contradiction, that rx(r) > (bk + 1) lx(r). Observation 6.3 implies that there must be a rectangle r with rx(r ) = p for every p {lx(r),. , rx(r) 1}. Due to Observation 6.5, at most bk of these

[Gar07]

[Gav74]
[GGKS95] Paul W. Goldberg, Martin Charles Golumbic, Haim Kaplan, and Ron Shamir. Four strikes against physical mapping of DNA. Journal of Computational Biology, 2(1):139152, 1995. Cited on pages 1, 27, 44, 79, 142. [Gho62] Alain Ghouila-Houri. Caractrisation des matrices totalement unie modulaires. Comptes Rendus de l Acadmie des Sciences, Paris, e 254:11921194, 1962. Cited on page 53. Daya Ram Gaur, Toshihide Ibaraki, and Ramesh Krishnamurti. Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem. Journal of Algorithms, 43(1):138152, 2002. Cited on pages 62, 140, 141, 161. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979. Cited on pages 14, 17, 44, 81, 87, 137, 142, 157. Fred W. Glover and Gary A. Kochenberger, editors. Handbook of Metaheuristics, volume 57 of International Series in Operations Research & Management Science. Springer, 2003. Cited on page 18. Panos Giannopoulos, Christian Knauer, and Sue Whitesides. Parameterized complexity of geometric problems. The Computer Journal, 51(3):372384, 2008. Cited on page 139. GNU Linear Programming Kit. Homepage of the GLPK software package, 2008. http://www.gnu.org/software/glpk. Cited on page 48. Jiong Guo and Rolf Niedermeier. Invitation to data reduction and problem kernelization. ACM SIGACT News, 38(1):3145, 2007. Cited on page 22.

[GIK02]

[GJ79]

[GK03]

[GKW08]

[GLP08]

[GN07]

174 [Gol04]

Bibliography Martin C. Golumbic. Algorithmic Graph Theory and Perfect Graphs, volume 57 of Annals of Discrete Mathematics. Elsevier B. V., 2nd edition, 2004. First edition Academic Press, 1980. Cited on pages 33, 51. Joachim von zur Gathen and Malte Sieveking. A bound on solutions of linear integer equations and inequalities. Proceedings of the American Mathematical Society, 72:155158, 1978. Cited on page 49. Salim Haddadi. A note on the NP-hardness of the consecutive block minimization problem. International Transactions in Operational Research, 9(6):775777, 2002. Cited on pages 44, 142. G. Hajs. Uber eine Art von Graphen. Internationale Mathematische o Nachrichten, 11, Problem 65, 1957. In German language. Cited on page 32. MohammadTaghi Hajiaghayi. Consecutive ones property. Manuscript, School of Computer Science, University of Waterloo, Canada, 2000. Cited on pages 80, 81. Johan H astad. Clique is hard to approximate within n1. Acta Mathematica, 182:105142, 1999. Cited on pages 21, 88. MohammadTaghi Hajiaghayi and Yashar Ganjali. A note on the consecutive ones submatrix problem. Information Processing Letters, 83(3):163166, 2002. Cited on pages 34, 79, 80, 81. Alan J. Homan and Joseph B. Kruskal. Integral boundary points of convex polyhedra. In H. W. Kuhn and A. W. Tucker, editors, Linear Inequalities and Related Systems, pages 223246. Princeton University Press, 1956. Cited on page 53. Dorit S. Hochbaum and Asaf Levin. Cyclical scheduling and multishift scheduling: Complexity and approximation algorithms. Discrete Optimization, 3(4):327340, 2006. Cited on page 27. Salim Haddadi and Zoubir Layouni. Consecutive block minimization is 1.5-approximable. Information Processing Letters, 108:132135, 2008. Cited on pages 44, 142. Refael Hassin and Nimrod Megiddo. Approximation algorithms for hitting objects with straight lines. Discrete Applied Mathematics, 30:2942, 1991. Cited on pages 27, 140, 141, 155, 156. Wen-Lian Hsu and Tze-Heng Ma. Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs. SIAM Journal on Computing, 28(3):10041020, 1999. Cited on page 33.