Parameterized Low-Rank Binary Matrix Approximation
Fedor V. Fomin†

Petr A. Golovach†

∗

Fahad Panolan†

arXiv:1803.06102v1 [cs.DS] 16 Mar 2018

Abstract
We provide a number of algorithmic results for the following family of problems: For
a given binary m × n matrix A and integer k, decide whether there is a “simple” binary
matrix B which differs from A in at most k entries. For an integer r, the “simplicity” of B
is characterized as follows.
• Binary r-Means: Matrix B has at most r different columns. This problem is known
to be NP-complete already for r = 2. We show that the problem is solvable in time
2O(k log k) · (nm)O(1) and thus is fixed-parameter tractable parameterized by k. We
prove that the problem admits a polynomial kernel when parameterized by r and k
but it has no polynomial kernel when parameterized by k only unless NP ⊆ coNP /poly.
We also complement these result by showing that when being
√ parameterized by r and
O(r· k log (k+r))
(nm)O(1) , which
k, the problem admits an algorithm of running time 2
1/2−ε
is subexponential in k for r ∈ O(k
) for any ε > 0.
• Low GF(2)-Rank Approximation: Matrix B is of GF(2)-rank at most r. This
problem is known to be NP-complete already for r = 1. It also known to be W[1]-hard
when parameterized by k. Interestingly, when parameterized by r and
k, the problem
3/2 √
is not only fixed-parameter tractable, but it is solvable in time 2O(r · k log k) (nm)O(1) ,
which is subexponential in k.
• Low Boolean-Rank Approximation: Matrix B is of Boolean rank at most r. The
problem is known to be NP-complete for k = √0 as well as for r = 1. We show that it
r
is solvable in subexponential in k time 2O(r2 · k log k) (nm)O(1) .

1

Introduction

In this paper we consider the following generic problem. Given a binary m × n matrix, that is
a matrix with entries from domain {0, 1},


a11 a12 . . . a1n
 a21 a21 . . . a2n 


m×n
A= .
,
..
..  = (aij ) ∈ {0, 1}
.
.
.
 .
.
.
. 
am1 am2 . . . amn
the task is to find a “simple” binary m × n matrix B which approximates A subject to some
specified constrains. One of the most widely studied error measures is the Frobenius norm,
which for a matrix A is defined as
v
uX
n
um X
t
|aij |2 .
kAkF =
i=1 j=1
∗

The research leading to these results have been supported by the Research Council of Norway via the projects
“CLASSIS” and “MULTIVAL”.
†
Department of Informatics, University of Bergen, Norway.

1

Here the sums are taken over R. Then for a given nonnegative integer k, we want to decide
whether there is a matrix B with certain properties such that
kA − Bk2F ≤ k.
We consider the binary matrix approximation problems when for a given integer r, the
approximation binary matrix B
(A1) has at most r pairwise-distinct columns,
(A2) is of GF(2)-rank at most r, and
(A3) is of Boolean rank at most r.
Each of these variants is very well-studied. Before defining each of the problems formally and
providing an overview of the relevant results, the following observation is in order. Since we
approximate a binary matrix by a binary matrix, in this case minimizing the Frobenius norm
of A − B is equivalent to minimizing the `0 -norm of A − B, where the measure kAk0 is the
number of non-zero entries of matrix A. We also will be using another equivalent way of
measuring the quality of approximation of a binary matrix A by a binary matrix B by taking
the sum of the Hamming distances between their columns. Let us recall that the Hamming
m
|
|
distance between
Pm two vectors x, y ∈ {0, 1} , where x = (x1 , . . . , xm ) and y = (y1 , . . . , ym ) , is
dH (x, y) = i=1 |xi − yi | or, in words, the number of positions i ∈ {1, . . . , m} where xi and yi
differ. Then for binary m × n matrix A with columns a1 , . . . , an and matrix B with columns
b1 , . . . , bn , we define
n
X
dH (A, B) =
dH (ai , bi ).
i=1

In other words, dH (A, B) is the number of positions with different entries in matrices A and
B. Then we have the following.
kA −

Bk2F

= kA − Bk0 = dH (A, B) =

n
X

dH (ai , bi ).

(1)

i=1

Problem (A1): Binary r-Means. By (1), the problem of approximating a binary m × n
matrix A by a binary m × n matrix B with at most r different columns (problem (A1)) is
equivalent to the following clustering problem. For given a set of n binary m-dimensional
vectors a1 , . . . , an (which constitute the columns of matrix A) and a positive integer r, Binary
r-Means aims to partition the vectors in at most r clusters, as to minimize the sum of withinclusters sums of Hamming distances to their binary means. More formally,
Binary r-Means
Input:
Task:

An m × n matrix A with columns (a1 , . . . , an ), a positive integer r and
a nonnegative integer k.
Decide whether there is a positive integer r0 ≤ r, a partition {I1 , . . . , Ir0 }
0
of {1, . . . , n} and vectors c1 , . . . , cr ∈ {0, 1}m such that
0

r X
X
i=1 j∈Ii

2

dH (ci , aj ) ≤ k?

To see the equivalence of Binary r-Means and problem (A1), it is sufficient to observe
that the pairwise different columns of an approximate matrix B such that kA − Bk0 ≤ k can
0
be used as vectors c1 , . . . , cr , r0 ≤ r. As far as the mean vectors are selected, a partition of
columns of A can be obtained by assigning each column-vector ai to its closest mean vector
cj (ties breaking arbitrarily). Then for such clustering the total sum of distances from vectors
within cluster to their centers does not exceed k. Similarly, solution to Binary r-Means can
be used as columns (with possible repetitions) of matrix B such that kA − Bk0 ≤ k. For that
we put bi = cj , where cj is the closest vector to ai .
This problem was introduced by Kleinberg, Papadimitriou, and Raghavan [39] as one of the
examples of segmentation problems. Approximation algorithms for optimization versions of this
problem were given by Alon and Sudakov [3] and Ostrovsky and Rabani [58], who referred to
it as clustering in the Hamming cube. In bioinformatics, the case when r = 2 is known under
the name Binary-Constructive-MEC (Minimum Error Correction) and was studied as a
model for the Single Individual Haplotyping problem [15]. Miettinen et al. [51] studied
this problem under the name Discrete Basis Partitioning Problem.
Binary r-Means can be seen as a discrete variant of the well-known k-Means Clustering.
(Since in problems (A2) and (A3) we use r for the rank of the approximation matrix, we also
use r in (A1) to denote the number of clusters which is commonly denoted by k in the literature
on means clustering.) This problem has been studied thoroughly, particularly in the areas of
computational geometry and machine learning. We refer to [1, 6, 41] for further references to
the works on k-Means Clustering.
Problem (A2): Low GF(2)-Rank Approximation. Let A be a m × n binary matrix. In
this case we view the elements of A as elements of GF(2), the Galois field of two elements.
Then the GF(2)-rank of A is the minimum r such that A = U · V, where U is m × r and V
is r × n binary matrices, and arithmetic operations are over GF(2). Equivalently, this is the
minimum number of binary vectors, such that every column (row) of A is a linear combination
(over GF(2)) of these vectors. Then (A2) is the following problem.
Low GF(2)-Rank Approximation
Input:
An m × n-matrix A over GF(2), a positive integer r and a nonnegative
integer k.
Task:
Decide whether there is a binary m × n-matrix B with GF(2)-rank
(B) ≤ r such that kA − Bk2F ≤ k.
Low GF(2)-Rank Approximation arises naturally in applications involving binary data sets
and serves as an important tool in dimension reduction for high-dimensional data sets with
binary attributes, see [19, 37, 33, 40, 59, 62, 69] for further references and numerous applications
of the problem.
Low GF(2)-Rank Approximation can be rephrased as a special variant (over GF(2)) of
the problem finding the rigidity of a matrix. (For a target rank r, the rigidity of a matrix A over
a field F is the minimum Hamming distance between A and a matrix of rank at most r.) Rigidity
is a classical concept in Computational Complexity Theory studied due to its connections with
lower bounds for arithmetic circuits [31, 32, 65, 60]. We refer to [43] for an extensive survey on
this topic.
Low GF(2)-Rank Approximation is also a special case of a general class of problems
approximating a matrix by a matrix with a small non-negative rank. Already Non-negative
Matrix Factorization (NMF) is a nontrivial problem and it appears in many settings. In
particular, in machine learning, approximation by a low non-negative rank matrix has gained
extreme popularity after the influential article in Nature by Lee and Seung [42]. NMF is
an ubiquitous problem and besides machine learning, it has been independently introduced
3

and studied in combinatorial optimization [23, 68], and communication complexity [2, 44]. An
extended overview of applications of NMF in statistics, quantum mechanics, biology, economics,
and chemometrics, can be found in the work of Cohen and Rothblum [17] and recent books
[14, 55, 26].
Problem (A3): Low Boolean-Rank Approximation. Let A be a binary m × n matrix.
This time we view the elements of A as Boolean variables. The Boolean rank of A is the
minimum r such that A = U ∧ V for a Boolean m × r matrix U and a Boolean r × n matrix V,
where the product is Boolean, that is, the logical ∧ plays the role of multiplication and ∨ the
role of sum. Here 0 ∧ 0 = 0, 0 ∧ 1 = 0, 1 ∧ 1 = 1 , 0 ∨ 0 = 0, 0 ∨ 1 = 1, and 1 ∨ 1 = 1. Thus the
matrix product is over the Boolean semi-ring (0, 1, ∧, ∨). This can be equivalently expressed as
the normal matrix product with addition defined as 1 + 1 = 1. Binary matrices equipped with
such algebra are called Boolean matrices. Equivalently, A = (aij ) ∈ {0, 1}m×n has the Boolean
rank 1 if A = x| ∧ y, where x = (x1 , x2 , . . . , xm ) ∈ {0, 1}m and y = (y1 , y2 , . . . , yn ) ∈ {0, 1}n
are nonzero vectors and the product is Boolean, that is, aij = xi ∧ yj . Then the Boolean rank
of A is the minimum integer r such that A = a(1) ∨ · · · ∨ a(r) , where a(1) , . . . , a(r) are matrices
of Boolean rank 1; zero matrix is the unique matrix with the Boolean rank 0. Then Low
Boolean-Rank Approximation is defined as follows.
Low Boolean-Rank Approximation
Input:
Task:

A Boolean m × n matrix A, a positive integer r and a nonnegative
integer k.
Decide whether there is a Boolean m × n matrix B of Boolean rank at
most r such that dH (A, B) ≤ k.

For r = 1 Low Boolean-Rank Approximation coincides with Low GF(2)-Rank Approximation but for r > 1 these are different problems.
Boolean low-rank approximation has attracted much attention, especially in the data mining
and knowledge discovery communities. In data mining, matrix decompositions are often used
to produce concise representations of data. Since much of the real data such as word-document
data is binary or even Boolean in nature, Boolean low-rank approximation could provide a
deeper insight into the semantics associated with the original matrix. There is a big body of
work done on Low Boolean-Rank Approximation, see e.g. [7, 9, 19, 46, 51, 52, 63]. In the
literature the problem appears under different names like Discrete Basis Problem [51] or
Minimal Noise Role Mining Problem [64, 46, 53].
P-Matrix Approximation. While at first glance Low GF(2)-Rank Approximation and
Low Boolean-Rank Approximation look very similar, algorithmically the latter problem
is more challenging. The fact that GF(2) is a field allows to play with different equivalent
definitions of rank like row rank and column ranks. We exploit this strongly in our algorithm
for Low GF(2)-Rank Approximation. For Low Boolean-Rank Approximation the
matrix product is over the Boolean semi-ring and nice properties of the GF(2)-rank cannot be
used here (see, e.g. [34]). Our algorithm for Low Boolean-Rank Approximation is based
on solving an auxiliary P-Matrix Approximation problem, where the task is to approximate
a matrix A by a matrix B whose block structure is defined by a given pattern matrix P. It
appears, that P-Matrix Approximation is also an interesting problem on its own.
More formally, let P = (pij ) ∈ {0, 1}p×q be a binary p×q matrix. We say that a binary m×n
matrix B = (bij ) ∈ {0, 1}m×n is a P-matrix if there is a partition {I1 , . . . , Ip } of {1, . . . , m} and
a partition {J1 , . . . , Jq } of {1, . . . , n} such that for every i ∈ {1, . . . , p}, j ∈ {1, . . . , q}, s ∈ Ii
and t ∈ Jj , bst = pij . In words, the columns and rows of B can be permuted such that the block
structure of the resulting matrix is defined by P.
4

P-Matrix Approximation
Input:
Task:

An m×n binary matrix A, a pattern binary matrix P and a nonnegative
integer k.
Decide whether there is an m × n P-matrix B such that kA − Bk2F ≤ k.

The notion of P-matrix was implicitly defined by Wulff et al. [67] as an auxiliary tool for
their approximation algorithm for the related monochromatic biclustering problem. P-Matrix
Approximation is also closely related to the problems arising in tiling transaction databases
(i.e., binary matrices), where the task is to find a tiling covers of a given binary matrix with a
small number of submatrices full of 1s, see [27].
Since Low GF(2)-Rank Approximation remains NP-complete for r = 1 [28], we have
that
Approximation is NP-complete already for very simple pattern matrix P =
 P-Matrix

0 0
.
0 1

1.1

Related work

In this subsection we give an overview of previous related algorithmic and complexity results for
problems (A1)–(A3), as well as related problems. Since each of the problems has many practical
applications, there is a tremendous amount of literature on heuristics and implementations. In
this overview we concentrate on known results about algorithms with proven guarantee, with
emphasis on parameterized complexity.
Problem (A1): Binary r-Means. Binary r-Means is trivially solvable in polynomial time
for r = 1, and as was shown by Feige in [22], is NP-complete for every r ≥ 2.
PTAS (polynomial time approximation scheme) for optimization variants of Binary rMeans were developed in [3, 58]. Approximation algorithms for more general k-Means Clustering is a thoroughly studied topic [1, 6, 41]. Inaba et al. [35] have shown that the general
k-Means Clustering is solvable in time nmr+1 (here n is the number of vectors, m is the
dimension and r the number of required clusters). We are not aware of any, except the trivial
brute-force, exact algorithm for Binary r-Means prior to our work.
Problem (A2): Low GF(2)-Rank Approximation. When low-rank approximation matrix
B is not required to be binary, then the optimal Frobenius norm rank-r approximation of
(not necessarily binary) matrix A can be efficiently found via the singular value decomposition
(SVD). This is an extremely well-studied problem and we refer to surveys for an overview of
algorithms for low rank approximation [38, 47, 66]. However, SVD does not guarantee to find an
optimal solution in the case when additional structural constrains on the low-rank approximation
matrix B (like being non-negative or binary) are imposed.
In fact, most of these constrained variants of low-rank approximation are NP-hard. In
particular, Gillis and Vavasis [28] and Dan et al. [19] have shown that Low GF(2)-Rank Approximation is NP-complete for every r ≥ 1. Approximation algorithms for the optimization
version of Low Boolean-Rank Approximation were considered in [36, 37, 19, 40, 62, 12]
among others.
Most of the known results about the parameterized complexity of the problem follows from
the results for Matrix Rigidity. Fomin et al. have proved in [25] that for every finite field,
and in particular GF(2), Matrix Rigidity over a finite field is W[1]-hard being parameterized
by k. This implies that Low GF(2)-Rank Approximation is W[1]-hard when parameterized by k. However, when parameterized by k and r, the problem becomes fixed-parameter
tractable. For Low GF(2)-Rank Approximation, the algorithm from [25] runs in time
5

√

2O(f (r) k log k) (nm)O(1) , where f is some function of r. While the function f (r) is not specified
in [25], the algorithm in [25] invokes enumeration of all 2r × 2r binary matrices of rank r, and
thus the running time is at least double-exponential in r.
Meesum, Misra, and Saurabh [49], and Meesum and Saurabh [50] considered parameterized
algorithms for related problems about editing of the adjacencies of a graph (or directed graph)
targeting a graph with adjacency matrix of small rank.
Problem (A3): Low Boolean-Rank Approximation. It follows from the rank definitions
that a matrix is of Boolean rank r = 1 if and only if its GF(2)-rank is 1. Thus by the results
of Gillis and Vavasis [28] and Dan et al. [19] Low Boolean-Rank Approximation is
NP-complete already for r = 1. Lu et al. [45] gave a formulation of Low Boolean-Rank
Approximation as an integer programming problem with exponential number of variables and
constraints.
While computing GF(2)-rank (or rank over any other field) of a matrix can be performed in
polynomial time, deciding whether the Boolean rank of a given matrix is at most r is already an
NP-complete problem. Thus Low Boolean-Rank Approximation is NP-complete already
for k = 0. This follows from the well-known relation between the Boolean rank and covering
edges of a bipartite graph by bicliques [30]. Let us briefly describe this equivalence. For
Boolean matrix A, let GA be the corresponding bipartite graph, i.e. the bipartite graph whose
biadjacency matrix is A. By the equivalent definition of the Boolean rank, A has Boolean rank
r if and only if it is the logical disjunction of r Boolean matrices of rank 1. But for every
bipartite graph whose biadjacency matrix is a Boolean matrix of rank at most 1, its edges can
be covered by at most one biclique (complete bipartite graph). Thus deciding whether a matrix
is of Boolean rank r is exactly the same as deciding whether edges of a bipartite graph can
be covered by at most r bicliques. The latter Biclique Cover problem is known to be NPO(r)
complete [57]. Biclique Cover is solvable in time 22
(nm)O(1) [29] and unless Exponential
o(r)
Time Hypothesis (ETH) fails, it cannot be solved in time 22 (nm)O(1) [13].
For the special case r = 1 Low Boolean-Rank Approximation and k√≤ kAk0 /240,
Bringmann, Kolev and Woodruff gave an exact algorithm of running time 2k/ kAk0 (nm)O(1)
[12]. (Let us remind that the `0 -norm of a matrix is the number of its non-zero entries.) More
generally, exact algorithms for NMF were studied by Cohen and Rothblum in [17]. Arora et
al. [5] and Moitra [54], who showed that for a fixed value of r, NMF is solvable in polynomial
time. Related are also the works of Razenshteyn et al. [61] on weighted low-rank approximation,
Clarkson and Woodruff [16] on robust subspace approximation, and Basu et al. [8] on PSD
factorization.
Observe that all the problems studied in this paper could be seen as matrix editing problems.
For Binary r-Means, we can assume that r ≤ n as otherwise we have a trivial NO-instance.
Then the problem asks whether it is possible to edit at most k entries of the input matrix,
that is, replace some 0s by 1s and some 1s by 0s, in such a way that the obtained matrix has
at most r pairwise-distinct columns. Respectively, Low GF(2)-Rank Approximation asks
whether it is possible to edit at most k entries of the input matrix to obtain a matrix of rank
at most r. In P-Matrix Approximation, we ask whether we can edit at most k elements to
obtain a P-matrix. A lot of work in graph algorithms has been done on graph editing problems,
in particular parameterized subexponential time algorithms were developed for a number of
problems, including various cluster editing problems [21, 24].

1.2

Our results and methods

We study the parameterized complexity of Binary r-Means, Low GF(2)-Rank Approximation and Low Boolean-Rank Approximation. We refer to the recent books of Cygan
6

et al. [18] and Downey and Fellows [20] for the introduction to Parameterized Algorithms and
Complexity. Our results are summarized in Table 1.

Binary r-Means

k
2
, Thm 1
No poly-kernel, Thm 4

GF(2) Approx
Boolean Approx

W[1]-hard [25]
NP-c for k = 0 [57]

r

O(k log k)

NP-c for r ≥ 2 [22]
NP-c for r ≥ 1 [28, 19]
NP-c for r ≥ 1 [28, 19]

√

O(r·

2

k+r
k log (k+r))

, Thm 5
Poly-kernel, Thm 2
3/2 √
2O(r ·√ k log k) , Thm 6
r
2O(r2 · k log k) , Thm 8

Table 1: Parameterized complexity of low-rank approximation. GF(2) Approx stands for
Low GF(2)-Rank Approximation and Bool Approx for Low Boolean-Rank Approximation. We omit the polynomial factor (nm)O(1) in running times.
Our first main result concerns Binary r-Means. We show (Theorem 1) that the problem
is solvable in time 2O(k log k) · (nm)O(1) . Therefore, Binary r-Means is FPT parameterized
by k. Since Low GF(2)-Rank Approximation parameterized by k is W[1]-hard and Low
Boolean-Rank Approximation is NP-complete for any fixed k ≥ 0, we find Theorem 1
quite surprising. The proof of Theorem 1 is based on a fundamental result of Marx [48] about
the complexity of a problem on strings, namely Consensus Patterns. We solve Binary rMeans by constructing a two-stage FPT Turing reduction to Consensus Patterns. First,
we use the color coding technique of Alon, Yuster, and Zwick from [4] to reduce Binary rMeans to some special auxiliary problem and then show that this problem can be reduced
to Consensus Patterns, and this allows us to apply the algorithm of Marx [48]. We also
prove (Theorem 2) that Binary r-Means admits a polynomial kernel when parameterized by
r and k. That is, we give a polynomial time algorithm that for a given instance of Binary
r-Means outputs an equivalent instance with O(k 2 + kr) columns and O(k 3 + kr) rows. For
parameterization by k only, we show in Theorem 4 that Binary r-Means has no polynomial
kernel unless NP ⊆ coNP /poly, the standard complexity assumption.
Our second main result concerns Low Boolean-Rank Approximation. As we mentioned above, the problem is NP-complete for k = 0, as well as for for r = 1, and hence is
intractable being parameterized by k or by r only. On the other hand, a simpler Low GF(2)Rank √Approximation is not only FPT parameterized by k + r, by [25] it is solvable in time
2O(f (r) k log k) (nm)O(1) , where f is some function of r, and thus is subexponential in k. It is natural to ask whether a similar complexity behavior could be expected for Low Boolean-Rank
Approximation. Our second main result, Theorem 8, shows√that this is indeed the case: Low
r
Boolean-Rank Approximation is solvable in time 2O(r2 · k log k) (nm)O(1) . The proof of this
theorem is technical and consists of several steps. We first develop a subexponential algorithm
for solving auxiliary P-Matrix Approximation, and then construct an FPT Turing reduction
from Low Boolean-Rank Approximation to P-Matrix Approximation.
Let us note that due to the relation of Boolean rank computation to Biclique Cover, the
result of [13] implies that unless Exponential Time Hypothesis (ETH) fails, Low Booleano(r)
Rank Approximation cannot be solved in time 22 f (k)(nm)O(1) for any function f . Thus
the dependence in r in our algorithm cannot be improved significantly unless ETH fails.
Interestingly, the technique developed for solving
P-Matrix Approximation can be used
√
O(r· k log (k+r))
(nm)O(1) for Binary r-Means and
to obtain
algorithms of running times 2
√
3/2 · k log k)
O(r
O(1)
2
(nm)
for Low GF(2)-Rank Approximation (Theorems 5 and 6 respectively). For Binary r-Means, Theorems 5 provides much better running time than Theorem 1
for values of r ∈ o((k log k)1/2 ).
For Low GF(2)-Rank Approximation, comparing Theorem 6 and the running time
7

√

2O(f (r) k log k) (nm)O(1) from [25],
√ let us note that Theorem 6 not only slightly improves the
exponential dependence in k by log k; it also drastically improves the exponential dependence
r
3/2
in r, from 22 to 2r .
The remaining part of the paper is organized as follows. In Section 2 we introduce basic
notations and obtain some auxiliary results. In Section 3 we show that Binary r-Means
is FPT when parameterized by k only. In Section 4 we discuss kernelization for Binary rMeans. In Section 5 we construct FPT algorithms for Binary r-Means and Low GF(2)Rank Approximation parameterized by k and r that are subexponential in k. In Section 6
we give a subexponential algorithm for Low Boolean-Rank Approximation. We conclude
our paper is Section 7 by stating some open problems.

2

Preliminaries

In this section we introduce the terminology used throughout the paper and obtain some properties of the solutions to our problems.
All matrices and vectors considered in this paper are assumed to be (0, 1)-matrices and
vectors respectively unless explicitly specified otherwise. Let A = (aij ) ∈ {0, 1}m×n be an
m × n-matrix. Thus aij , i ∈ {1, . . . , m} and j ∈ {1, . . . , n}, are the elements of A. For
I ⊆ {1, . . . , m} and J ⊆ {1, . . . , n}, we denote by A[I, J] the |I| × |J|-submatrix of A with the
elements aij where i ∈ I and j ∈ J. We say that two matrices A and B are isomorphic
if B
P
can be obtained from A by permutations of rows andL
columns. We use “+” and “ ” to denote
sums and summations over R, and we use “⊕” and “ ” for sums and summations over GF(2).
We also consider string of symbols. For two strings a and b, we denote by ab their concatenation. For a positive integer k, ak denotes the concatenation of k copies of a; a0 is assumed
to be the empty string. Let a = a1 · · · a` be a string over an alphabet Σ. Recall that a string
b is said to be a substring of a if b = ah ah+1 · · · at for some 1 ≤ h ≤ t ≤ `; we write that
b = a[h..t] in this case. Let a = a1 · · · a` and b = b1 · · · b` be strings of the same length ` over
Σ. Similar to the the definition of Hamming distance between two (0, 1)-vectors, the Hamming distance dH (a, b) between two strings is defined as the number of position i ∈ {1, . . . , `}
where the strings differ. We would like to mention that for Hamming distance (for vectors and
strings), the triangular inequality holds. That is, for any three strings a, b, c of length n each,
dH (a, c) ≤ dH (a, b) + dH (b, c).

2.1

Properties of Binary r-Means

Let (A, r, k) be an instance of Binary r-Means where A is a matrix with columns (a1 , . . . , an ).
We say that a partition {I1 , . . . , Ir0 } of {1, . . . , n} for r0 ≤ r is a solution for (A, r, k) if there
Pr0 P
0
i j
are vectors c1 , . . . , cr ∈ {0, 1}m such that
i=1
j∈Ii dH (c , a ) ≤ k. We say that each Ii
or, equivalently, the multiset of columns {aj | j ∈ Ii } (some columns could be the same) is a
cluster and call ci the mean of the cluster. Observe that given a cluster I ⊆ {1, . . . , n}, one
can easily compute an optimal mean c = (c1 , . . . , cm )| as follows. Let aj = (a1j , . . . , amj )| for
j ∈ {1, . . . , n}. For each i ∈ {1, . . . , m}, consider the multiset Si = {aij | j ∈ I} and put ci = 0
or ci = 1 according to the majority of elements in Si , that is, ci = 0 if at least half of the
elements in Si are 0s and ci = 1 otherwise. We refer to this construction of c as the majority
rule.
0
In the opposite direction, given a set of means c1 , . . . , cr , we can construct clusters {I1 , . . . , Ir0 }
as follows: for each column aj , find the closest ci , i ∈ {1, . . . , r0 }, such that dH (ci , aj ) is minimum and assign j to Ii . Note that this procedure does not guarantee that all clusters are
nonempty but we can simply delete empty clusters. Hence, we can define a solution as a set of
0
means C = {c1 , . . . , cr }. These arguments also imply the following observation.
8

Observation 1. The task of Binary r-Means can equivalently be stated as follows: de0
cide
exist a positive integer r0 ≤ r and vectors c1 , . . . , cr ∈ {0, 1}m such that
Pn whether there
j i
0
i=1 min{dH (c , a ) | 1 ≤ j ≤ r } ≤ k.
Definition 1 (Initial cluster and regular partition). Let A be an m × n-matrix with columns
a1 , . . . , an . An initial cluster is an inclusion maximal set I ⊆ {1, . . . , n} such that all the
columns in the multiset {aj | j ∈ I} are equal.
We say that a partition {I1 , . . . , Ir0 } of the columns of matrix A is regular if for every initial
cluster I, there is i ∈ {1, . . . , r0 } such that I ⊆ Ii .
By the definition of the regular partition, every initial cluster of A is in some set Ii but the
set Ii may contain many initial clusters.
Lemma 1. Let (A, r, k) be a yes-instance of Binary r-Means. Then there is a solution
{I1 , . . . , Ir0 }, r0 ≤ r which is regular (i.e, for any initial cluster I of A, there is i ∈ {1, . . . , r0 }
such that I ⊆ Ii ).
0

Proof. Let a1 , . . . , an be thePcolumns of A. By Observation 1, there are vectors c1 , . . . , cr
for some r0 ≤ r such that ni=1 min{dH (cj , ai ) | 1 ≤ j ≤ r0 } ≤ k. Once we have the vec0
tors c1 , . . . , cr , a solution can be obtained by assigning each vector ai to a closest vector in
0
{c1 , . . . , cr }. This implies the conclusion of the lemma.

2.2

Properties of Low GF(2)-Rank Approximation

For Low GF(2)-Rank Approximation, we need the following folklore observation. We provide a proof for completeness.
Observation 2. Let A be a matrix over GF(2) with rank(A) ≤ r. Then A has at most 2r
pairwise-distinct columns and at most 2r pairwise-distinct rows.
Proof. We show the claim for columns; the proof for the rows is similar in arguments to that of
the case of columns. Assume that rank(A) = r and let e1 , . . . , er be a basis of the column space
of A. Then every column ai of A is a linear combination of e1 , . . . , er . Since A is aL
matrix over
GF(2), it implies that for every columns ai , there is I ⊆ {1, . . . , r} such that ai = j∈I ej . As
the number of distinct subsets of {1, . . . , r} is 2r , the claim follows.
By making use of Observation 2, we can reformulate Low GF(2)-Rank Approximation
as follows: given an m × n matrix A over GF(2) with the columns a1 , . . . , an , a positive integer
r and a nonnegative integer k, we ask whether there is a positive integer r0 ≤ 2r , a partition
0
(I1 , . . . , Ir0 ) of {1, . . . , n} and vectors c1 , . . . , cr ∈ {0, 1}m such that
0

r X
X

dH (ci , aj ) ≤ k

i=1 j∈Ii
0

and the dimension of the linear space spanned by the vectors c1 , . . . , cr is at most r. Note that
0
given a partition {I1 , . . . , Ir0 } of {1, . . . , n}, we cannot select c1 , . . . , cr using the majority rule
like the case of Binary r-Means because of the rank conditions on these vectors. But given
0
c1 , . . . , cr , one can construct an optimal partition {I1 , . . . , Ir0 } with respect to these vectors in
the same way as before for Binary r-Means. Similar to Observation 1, we can restate the task
of Low GF(2)-Rank Approximation.
Observation 3. The task of Low GF(2)-Rank Approximation of binary matrix A with
columns a1 , . . . , an can equivalently be stated as follows: decide whether there is a positive
0
integer
r0 ≤ r and linearly
independent vectors c1 , . . . , cr ∈ {0, 1}m over GF(2) such that
Pn
L
i
j
0
i=1 min{dH (s, a ) | s =
j∈I c , I ⊆ {1, . . . , r }} ≤ k.
9

Recall that it was proved by Fomin et al. [25] that Low GF(2)-Rank Approximation is
FPT when parameterized by k and r. To demonstrate that the total dependency on k + r could
be relatively small, we observe the following.
Proposition 1. Low GF(2)-Rank Approximation is solvable in time 2O(k log r) · (nm)O(1) .
Proof. In what follows by rank we mean the GF(2)-rank of a matrix. It is more convenient for
this algorithm to interpret Low GF(2)-Rank Approximation as a matrix editing problem.
Given a matrix A over GF(2), a positive integer r and a nonnegative integer k, decide whether
it is possible to obtain from A a matrix B with rank(B) ≤ r by editing at most k elements, i.e.,
by replacing 0s by 1s and 1s by 0s. We use this to construct a recursive branching algorithm
for the problem.
Let (A = (aij ), r, k) be an instance of Low GF(2)-Rank Approximation. The algorithm
for (A, r, k) works as follows.
• If rank(A) ≤ r, then return YES and stop.
• If k = 0, then return NO and stop.
• Since the rank of A is more than r, there are r + 1 columns I ⊆ {1, . . . , m} and r + 1 rows
J ⊆ {1, . . . , n} such that the induced submatrix A[I, J] is of rank r + 1. We branch into
(r + 1)2 subproblems: For each i ∈ I and j ∈ J we do the following:
– construct matrix A0 from A by replacing aij with aij ⊕ 1,
– call the algorithm for (A0 , r, k − 1) and
∗ if the algorithm returns YES, then return YES and stop.
• Return NO and stop.
To show the correctness of the algorithm, we observe the following. Let B be an m × nmatrix of rank at most r. If rank(A[I, J]) > r + 1 for some I ⊆ {1, . . . , m} and J ⊆ {1, . . . , n},
then kA[I, J] − B[I, J]k2F ≥ 1, i.e, A[I, J] and B[I, J] differ in at least one element. To evaluate
the running time, notice that we can compute rank(A) in polynomial time, and if rank(A) > r,
then we can find in polynomial time an (r + 1) × (r + 1)-submatrix of A of rank r + 1. Then we
have (r + 1)2 branches in our algorithm. Since we decrease the parameter k in every recursive
call, the depth of the recurrence tree is at most k. It implies that the algorithm runs in time
(r + 1)2k · (nm)O(1) .

2.3

Properties of P-Matrix Approximation

We will be using the following observation which follows directly from the definition of a Pmatrix.
Observation 4. Let P be a binary p × q matrix. Then every P-matrix B has at most p
pairwise-distinct rows and at most q pairwise-distinct columns.
In our algorithm for P-Matrix Approximation, we need a subroutine for checking whether
a matrix A is a P-matrix. For that we employ the following brute-force algorithm. Let A be
an m × n-matrix. Let a1 , . . . , am be the rows of A, and let a1 , . . . , an be the columns of A.
Let I = {I1 , . . . , Is } be the partition of {1, . . . , m} into inclusion-maximal sets of indices such
that for every i ∈ {1, . . . , s} the rows aj for j ∈ Ii are equal. Similarly, let J = {J1 , . . . , Jt }
be the partition of {1, . . . , n} into inclusion-maximal sets such that for every i ∈ {1, . . . , t}, the
columns aj for j ∈ Ii are equal. We say that (I, J ) is the block partition of A.
10

Observation 5. There is an algorithm which given an m × n-matrix A = (aij ) ∈ {0, 1}m×n
and a p × q-matrix P = (pij ) ∈ {0, 1}p×q , runs in time 2O(p log p+q log q) · (nm)O(1) , and decides
whether A is a P-matrix or not.
Proof. Let (I = {I1 , . . . , Is }, J = {J1 , . . . , Jt }) be the block partition of A and let (X =
{X1 , . . . , Xp0 }, Y = {Y1 , . . . , Yq0 }) be the block partition of P. Observe that A is a P-matrix
if and only if s = p0 , t = q 0 and there are permutations α and β of {1, . . . , p0 } and {1, . . . , q 0 },
respectively, such that the following holds for every i ∈ {1, . . . , p0 } and j ∈ {1, . . . , q 0 }:
i) |Ii | ≥ |Xα(i) | and |Jj | ≥ |Yβ(j) |,
ii) ai0 j 0 = pi00 j 00 for i0 ∈ Ii , j ∈ Jj , i00 ∈ Xα(i) and j 00 ∈ Yβ(i) .
Thus in order to check whether A is a P-matrix, we check whether s = p0 and t = q 0 ,
and if it holds, we consider all possible permutations α and β and verify (i) and (ii). Note
that the block partitions of A and P can be constructed in polynomial time. Since there
are p0 ! ∈ 2O(p log p) and q 0 ! ∈ 2O(q log q) permutations of {1, . . . , p0 } and {1, . . . , q 0 }, respectively,
and (i)–(ii) can be verified in polynomial time, we obtain that the algorithm runs in time
2O(p log p+q log q) · (nm)O(1) .
We conclude the section by showing that P-Matrix Approximation is FPT when parameterized by k and the size of P.
Proposition 2. P-Matrix Approximation can be solved in time 2O(k(log p+log q)+p log p+q log q) ·
(nm)O(1) .
Proof. As with Low GF(2)-Rank Approximation in Proposition 1, we consider P-Matrix
Approximation as a matrix editing problem. The task now is to obtain from the input matrix
A a P-matrix by at most k editing operations. We construct a recursive branching algorithm for
this. Let (A, P, k) be an instance of P-Matrix Approximation, where A = (aij ) ∈ {0, 1}m×n
and P = (pij ) ∈ {0, 1}p×q . Then the algorithm works as follows.
• Check whether A is a P-matrix using Observation 5. If it is so, then return YES and
stop.
• If k = 0, then return NO and stop.
• Find the block partition (I, J ) of A. Let I = {I1 , . . . , Is } and J = {J1 , . . . , Jt }. Set
p0 = min{s, p + 1} and q 0 = min{t, q + 1}. For each i ∈ {1, . . . , p0 } and j ∈ {1, . . . , q 0 } do
the following:
– construct a matrix A0 from A by replacing the value of an arbitrary ai0 j 0 for i0 ∈ Ii
and j 0 ∈ Jj by the opposite value, i.e., set it ai0 j 0 = 1 if it was 0 and 0 otherwise,
– call the algorithm recursively for (A0 , r, k − 1), and
∗ if the algorithm returns YES, then return YES and stop.
• Return NO and stop.
For the correctness of the algorithm, let us assume that the algorithm did not stop in the
S0
S0
first two steps. That is, A is not a P-matrix and k > 0. Consider I = pi=1 Ii and J = qj=1 Jj .
Let B = (bij ) ∈ {0, 1}m×n be a P-matrix such that kA − Bk2F ≤ k. Observe that A[I, J] and
B[I, J] differ in at least one element. Hence, there is i ∈ {1, . . . , p0 } and j ∈ {1, . . . , q 0 } such
that ai0 j 0 6= bi0 j 0 for i0 ∈ Ii and j 0 ∈ Jj . Note that for any choice of i0 , i00 ∈ Ii and j 0 , j 00 ∈ Jj , the
matrices A0 and A00 obtained from A by changing the elements ai0 j 0 and ai00 j 00 respectively, are
11

isomorphic. This implies that (A, P, k) is a yes-instance of P-Matrix Approximation if and
only if (A0 , P, k − 1) is a yes-instance for one of the branches of the algorithm.
For the running time evaluation, recall that by Observation 5, the first step can be done
in time 2O(p log p+q log q) · (nm)O(1) . Then the block partition of A can be constructed in polynomial time and we have at most (p + 1)(q + 1) recursive calls of the algorithm in the third
step. The depth of recursion is at most k. Hence, we conclude that the total running time is
2O(k(log p+log q)+p log p+q log q) · (nm)O(1) .

3

Binary r-Means parameterized by k

In this section we prove that Binary r-Means is FPT when parameterized by k. That is we
prove the following theorem.
Theorem 1. Binary r-Means is solvable in time 2O(k log k) · (nm)O(1) .
The proof of Theorem 1 consists of two FPT Turing reductions. First we define a new
auxiliary problem Cluster Selection and show how to reduce this problem the Consensus
Patterns problem. Then we can use as a black box the algorithm of Marx [48] for this problem.
The second reduction is from Binary r-Means to Cluster Selection and is based on the
color coding technique of Alon, Yuster, and Zwick from [4].
From Cluster Selection to Consensus Patterns. In the Cluster Selection problem we
are given a regular partition {I1 , . . . , Ip } of columns of matrix A. Our task is to select from
each set Ii exactly one initial cluster such that the total deviation of all the vectors in these
clusters from their mean is at most d. More formally,
Cluster Selection
Input:
Task:

An m × n-matrix A with columns a1 , . . . , an , a regular partition
{I1 , . . . , Ip } of {1, . . . , n}, and a nonnegative integer d.
Decide whether there is a set of initial clusters J1 , . . . , Jp and a vector
c ∈ {0, 1}m such that Ji ⊆ Ii for i ∈ {1, . . . , p} and
p X
X

dH (c, aj ) ≤ d.

i=1 j∈Ji

If (A, {I1 , . . . , Ip }, d) is a yes-instance of Cluster Selection, then we say that the corresponding sets of initial clusters {J1 , . . . , Jp } and the vector c (or just {J1 , . . . , Jp } as c can be
computed by the majority rule from the set of cluster) is a solution for the instance. We show
that Cluster Selection is FPT when parameterized by d. Towards that, we use the results
of Marx [48] about the Consensus Patterns problem.
Consensus Patterns
Input:
Task:

A (multi) set of p strings {s1 , . . . , sp } over an alphabet Σ, a positive
integer t and a nonnegative integer d.
Decide whether there is a string s of length t overP
Σ, and a length t
substring s0i of si for every i ∈ {1, . . . , p} such that pi=1 dH (s, s0i ) ≤ d.

Marx proved that Consensus Patterns can be solved in time δ O(δ) ·|Σ|δ ·L9 where δ = d/p
and L is the total length of all the strings in the input [48]. It gives us the following lemma.
12

Lemma 2 ([48]). Consensus Patterns can be solved in time 2O(d log d) · L9 , where L is the
total length of all the strings in the input if the size of Σ is bounded by a constant.
Now we are ready to show the following result for Cluster Selection.
Lemma 3. Cluster Selection can be solved in time 2O(d log d) · (nm)O(1) .
Proof. Let (A, {I1 , . . . , Ip }, d) be an instance of Cluster Selection. Let a1 , . . . , an be the
i
columns of A. First, we check whether there are initial clusters J1 ,P
. . . , JP
p and a vector c = a
p
h
for some i ∈ {1, . . . , n} such that Jj ⊆ Ij for j ∈ {1, . . . , p} and j=1 h∈Jj dH (c, a ) ≤ d.
Towards that we consider all possible choices of c = ai for i ∈ {1, . . . , n}. P
Suppose that c is
given. For every j ∈ {1, . . . , p}, we find an initial cluster Jj ⊆ Ij such that h∈Jj dH (c, ah ) is
P
P
minimum. If pj=1 h∈Jj dH (c, ah ) ≤ d, then we return the corresponding solution, i.e., the set
of initial clusters {J1 , . . . , Jp } and c. Otherwise, we discard the choice of c. It is straightforward
to see that this procedure is correct and can be performed in polynomial time. Now on we
assume that this is not the case. That is, if (A, {I1 , . . . , Ip }, d) is a yes-instance, then c 6= ai for
any solution. In particular, it means that for every solution ({J1 , . . . , Jp }, c), dH (c, aj ) ≥ 1 for
j ∈ J1 ∪ . . . ∪ Jp . If p > d, we obtain that (A, {I1 , . . . , Ip }, d) is a no-instance. In this case we
return the answer and stop. Hence, from now we assume that p ≤ d. Moreover, observe that
|J1 | + . . . + |Jp | ≤ d for any solution ({J1 , . . . , Jp }, c).
We consider all P-tuples of positive integers (`1 , . . . , `p ) such that `1 + . . . + `p ≤ d and for
each P-tuple check whether there is a solution ({J1 , . . . , Jp }, c) with |Ji | = `i for i ∈ {1, . . . , p}.
Note that there are at most 2d+p ≤ 4d such P-tuples. If we find a solution for one of the
P-tuples, we return it and stop. If we have no solution for any P-tuple, we conclude that we
have a no-instance of the problem.
Assume that we are given a P-tuple (`1 , . . . , `p ). If there is i ∈ {1, . . . , p} such that there is no
initial cluster Ji ∈ Ii with |Ji | = `i , then we discard the current choice of the P-tuple. Otherwise,
we reduce the instance of the problem using the following rule: if there is i ∈ {1, . . . , p} and an
initial cluster J ⊆ Ii such that |I| =
6 `i , then delete columns ah for h ∈ J from the matrix and
set Ii = Ii \ J. By this rule, we can assume that each Ii contains only initial clusters of size `i .
Let Ii = {J1i , . . . , Jqii } where J1i , . . . , Jqii are initial clusters for i ∈ {1, . . . , p}.
We reduce the problem of checking the existence of a solution ({J1 , . . . , Jp }, c) with |Ji | = `i
for i ∈ {1, . . . , p} to the Consensus Patterns problem. Towards that, we first define the
alphabet Σ = {0, 1, a, b} and strings
a=a
. . a},
| .{z
m+d

b = b| .{z
. . }b,
m+d

and 0 = 0| .{z
. . 0} .
d

Then x = ab · · · ab is defined to be the string obtained by the alternating concatenation of d + 1
copies of a and d + 1 copies of b. Now we construct ` = `1 + . . . + `p strings sji for i ∈ {1, . . . , p}
and j ∈ {1, . . . , `i }. For each i ∈ {1, . . . , p}, we do the following.
• For every q ∈ {1, . . . , qi }, select a column ahi,q for hi,q ∈ Jqi and, by slightly abusing the
notation, consider it to be a (0, 1)-string.
• Then for every j ∈ {1, . . . , `i }, set sji = xahi,1 0x . . . xahi,qi 0x.
Observe that the strings sji for j ∈ {1, . . . , `i } are the same. We denote by S = {sji | 1 ≤
i ≤ p, 1 ≤ j ≤ `i } the collection (multiset) of all constructed strings. Finally, we define
t = (m + d)(2d + 3). Then output (S, Σ, t, d) as the instance of Consensus Patterns. Now
we prove the correctness of the reduction.
13

Claim 3.1. The instance (A, {I1 , . . . , Ip }, d) of Cluster Selection has a solution ({J1 , . . . , Jp }, c)
with |Ji | = `i for i ∈ {1, . . . , p} if and only if (S, Σ, t, d) is a yes-instance of Consensus Patterns.
Proof of Claim 3.1. Suppose that the instance (A, {I1 , . . . , Ip }, d) of Cluster Selection has
a solution ({J1 , . . . , Jp }, c) with |Ji | = `i for i ∈ {1, . . . , p}. For every i ∈ {1, . . . , p} and
j ∈ {1, . . . , `i }, we select the substring ŝji = xahi,j 0x where hi,j ∈ Ji . By the definition,
|ŝji | = 2|x| + m + d = t. We set s = xc0x considering the vector c being a (0, 1)-string. Clearly,
|s| = t. We have that
p X
`i
X
i=1 j=1

dH (s, ŝji )

=

p
X

`i dH (c, a

i=1

hi,j

)=

p X
X

dH (c, ah ) ≤ d.

i=1 h∈Ji

Therefore, (S, Σ, t, d) is a yes-instance of Consensus Patterns.
Now we prove the reverse direction. Assume that (S, Σ, t, d) is a yes-instance of Consensus
Patterns. Let ŝji be a substring of sji of length t for i ∈ {1, . . . , p} and j ∈ {1, . . . , `i }, and
P Pi
let s be a string of length t over Σ such that pi=1 `j=1
dH (s, ŝji ) ≤ d. We first show that
there is a positive integer α ≤ t − m + 1 such that for every i ∈ {1, . . . , p} and j ∈ {1, . . . , `i },
ŝji [α..α + m − 1] = ahi,j for some hi,j ∈ Ii .
Consider the substring ŝ11 . Since |ŝ11 | = t, by the definition of the string s11 , we have that
there is a positive integer β ≤ t − |x| + 1 = t − 2(m + d)(d + 1) + 1 such that ŝ11 [β..β + |x| − 1] =
ŝ11 [β..β + 2(m + d)(d + 1) − 1] = x. Let i ∈ {1, . . . , p} and j ∈ {1, . . . , `i }. Suppose that
ŝji [β..β + 2(m + d)(d + 1) − 1] 6= x. Recall that x contains 2(d + 1) alternating copies of a and
b and |a| = |b| = m + d. Because dH (ŝ11 , ŝji ) ≤ dH (ŝ11 , s) + dH (s, ŝji ) ≤ d (by the triangular
inequality) and by the construction of the strings of S, we have that that either
i) there is γ = β + 2(m + d)h for some nonnegative integer h ≤ d such that ŝji [β..γ − 1] =
x[β..γ − 1] and ŝji [γ..γ + m − 1] = ahi,j for some hi,j ∈ Ii , or
ii) there is γ = β+2(m+d)h for some integer 1 ≤ h ≤ d such that ŝji [γ..β+2(m+d)(d+1)−1] =
x[γ..β + 2(m + d)(d + 1) − 1] and ŝji [γ − (m + d)..γ − d + 1] = ahi,j for some hi,j ∈ Ii .
We would like to mention that in the above two cases, in one of them x[β..γ − 1] or x[γ..β +
2(m + d)(d + 1) − 1] may not be well defined. But at least in one of them it will be well defined.
These cases are symmetric and without loss of generality we can consider only the case (i). We
have that ŝji [γ..γ + (m + d) − 1] and ŝ11 [γ..γ + (m + d) − 1] differ in all the symbols, because all
the symbols of ŝji [γ..γ + (m + d) − 1] are 0 or 1 and ŝ11 [γ..γ + (m + d) − 1] = a. Since m + d > d, it
contradicts the property that dH (ŝ11 , ŝji ) ≤ d. So we have that ŝji [β..β + 2(m + d)(d + 1) − 1] = x
for every i ∈ {1, . . . , p} and j ∈ {1, . . . , `i }.
If β > m + d, then we set α = β − (m + d). Notice that that for every i ∈ {1, . . . , p} and
j ∈ {1, . . . , `i }, ŝji [α..α + m − 1] = ahi,j for some hi,j ∈ Ii . Suppose β ≤ m + d. Then we set
α = β + 2(m + d)(d + 1). Because t = (m + d)(2d + 3), it holds that α ≤ t − m + 1 and for
every i ∈ {1, . . . , p} and j ∈ {1, . . . , `i }, ŝji [α..α + m − 1] = ahi,j for some hi,j ∈ Ii . Now consider
c = s[α..α + m − 1]. Because for every i ∈ {1, . . . , p} and j ∈ {1, . . . , `i }, ŝji [α..α + m − 1] = ahi,j
for some hi,j ∈ Ii , we can assume that c is a (0, 1)-string. We consider it as a vector of {0, 1}m .
Let i ∈ {1, . . . , p}. We consider the columns ahi,j for j ∈ {1, . . . , `i } and find among them
the column ahi such that dH (c, ahi ) is minimum. Let Jrii ⊆ Ii for ri ∈ {1, . . . , qi } be an initial cluster that contains hi . We show that ({Jr11 , . . . , Jrpp }, c) is a solution for the instance

14

(A, {I1 , . . . , Ip }, d) of Cluster Selection. To see it, it is sufficient to observe that the following inequality holds.
p X
X
i=1 h∈Jri
i

dH (c, ah ) =

p
X

`i dH (c, ahi ) ≤

i=1

p X
`i
X

dH (c, ahi,j ) ≤

i=1 j=1

p X
`i
X

dH (s, ŝji ) ≤ d.

i=1 j=1

This concludes the proof of the claim.
Using Claim 3.1 and Lemma 2, we solve Consensus Patterns for (S, Σ, t, d). This completes the description of our algorithm and its correctness proof. To evaluate the running time,
recall first that we check in polynomial time whether we have a solution with c coinciding with a
column of A. If we fail to find such a solution, then we consider at most 4d P-tuples (`1 , . . . , `p ).
Then for each P-tuple, we either discard it immediately or construct in polynomial time the
corresponding instance of Consensus Patterns, which is solved in time 2O(d log d) · (nm)O(1)
by Lemma 2. Hence, the total running time is 2O(d log d) · (nm)O(1) .
Let us note that we are using Lemma 2 as a black box in our algorithm for Cluster Selection. By adapting the algorithm of Marx [48] for Consensus Patterns to solve Cluster
Selection it is possible to improve the polynomial factor in the running time but this would
demand repeating and rewriting various parts of [48].
From Binary r-Means to Consensus Patterns. Now we prove the main result of the
section.
Proof of Theorem 1. Our algorithm for Binary r-Means uses the color coding technique introduced by Alon, Yuster and Zwick in [4] (see also [18] for the introduction to this technique).
In the end we obtain a deterministic algorithm but it is more convenient for us to describe a
randomized true-biased Monte-Carlo algorithm and then explain how it could be derandomized.
Let (A, r, k) be a yes-instance of Binary r-Means where A = (a1 , . . . , an ). Then by
0
Lemma 1, there is a regular solution {I1 , . . . , Ir0 } for this instance. Let c1 , . . . , cr be the
corresponding means of the clusters. Recall that regularity means that for any initial cluster
I, there is a cluster in the solution that contains it. We say that a cluster Ii of the solution is
simple if it contain exactly one initial cluster and Ii is composite otherwise.
Let Ii be a composite
P
cluster of {I1 , . . . , Ir0 } that contains h ≥ 2 initial clusters. Then j∈Ii (ci , aj ) ≥ h − 1. This
observation immediately implies that a regular solution contains at most k composite clusters
and the remaining clusters are simple. Moreover, the total number of initial clusters in the
composite clusters is at most
also that if Ii is a simple cluster then ci = ah for
P 2k. i Note
arbitrary h ∈ Ii , because j∈Ii (c , aj ) = 0, That is, simple clusters do not contribute to the
total cost of the solution.
Let (A, r, k) be an instance of Binary r-Means where A = (a1 , . . . , an ). We construct
the set I of initial clusters for the matrix A. Let s = |I|. The above observations imply that
finding a solution for Binary r-Means is equivalent to finding a set I 0 ⊆ I of size at most 2k
such that I 0 can be partitioned into at most r − s + |I 0 | composite clusters. More precisely, we
are looking for I 0 ⊆ I of size at most 2k such that there is a partition {P1 , . . . , Pt } of I 0 with
t ≤ r − s + |I 0 | and vectors s1 , . . . , st ∈ {0, 1}m with the property that
t XX
X

dH (si , ah ) ≤ k.

i=1 I∈Pi j∈I

If s ≤ r the (A, r, k) is a trivial yes-instance of the problem with I being a solution. If
r + k < s, then (A, r, k) is a trivial no-instance. Hence, we assume from now that r < s ≤ r + k.
15

We color the elements of I independently and uniformly at random by 2k colors 1, . . . , 2k.
Observe that if (A, r, k) is a yes-instance, then at most 2k initial clusters in a solution that
are included in composite clusters are colored by distinct colors with the probability at least
(2k)!
≥ e−2k . We say that a solution {I1 , . . . , Ir0 } for (A, r, k) is a colorful solution if all initial
(2k)2k
clusters that are included in composite clusters of {I1 , . . . , Ir0 } are colored by distinct colors.
We construct an algorithm for finding a colorful solution (if it exists).
Denote by I1 , . . . , I2k the sets of color classes of initial clusters, i.e., the sets of initial clusters
that are colored by 1, . . . , 2k, respectively. Note that some sets could be empty. We consider all
possible partitions P = {P1 , . . . , Pt } of nonempty subsets of {1, . . . , 2k} such that each set of P
contains at least two elements. . Notice that if (A, r, k) has a colorful solution {I1 , . . . , Ir0 }, then
there is P = {P1 , . . . , Pt } such that a cluster Ii of the solution is composite cluster containing
initial clusters colored by a set of colors Xi if and only if there is Xi ∈ P. Since we consider all
possible P, if (A, r, k) has a colorful solution, we will find P satisfying this condition. Assume
that P = {P1 , . . . , Pt } is given. If s − |P1 | − . . . − |Pt | + t > r, we discard the current choice of
P. Assume from now that this is not the case.
For
S each i ∈ {1, . . . , t}, we do the following. Let Pi = {i1 , . . . , ip } ⊆ {1, . . . , 2k}. Let
Jji = I∈Ii I and J i = J1i ∪ . . . ∪ Jpi . Denote by Ai the submatrix of A containing the columns
j

ah with h ∈ J i . We use Lemma 3 to find the minimum nonnegative integer di ≤ k such
that (Ai , {J1i , . . . , Jpi }, di ) is a yes-instance of Cluster Selection. If such a value of di does
not exist, we discard the current choice of P. Otherwise, we find the corresponding solution
({Li1 , . . . , Lip }, si ) of Cluster Selection. Let Li = Li1 ∪ . . . ∪ Lip
If we computed di and constructed Li for all i ∈ {1, . . . , t}, we check whether d1 +. . .+dt ≤ k.
If it holds, we return the colorful solution with the composite clusters L1 , . . . , Lt whose means
are s1 , . . . , st respectively and the remaining clusters are simple. Otherwise, we discard the
choice of P. If for one of the choices of P we find a colorful solution, we return it and stop. If
we fails to find a solution for all possible choices of P, we return the answer NO and stop.
If the described algorithm produces a solution, then it is straightforward to verify that this
is a colorful solution to (A, r, k) recalling that simple clusters do not contribute to the total
cost of the solution. In the other direction, if (A, r, k) has a colorful solution {I1 , . . . , Ir0 }, then
there is P = {P1 , . . . , Pt } such that cluster Ii of the solution is a composite cluster containing
initial clusters colored by a set of colors Xi if and only if there is Xi ∈ P. Let L1 , . . . , Lt be
the composite clusters of the solution
P that correspond to P1 , . . . , Pt , respectively and denote
by s1 , . . . , st their means. Let di = h∈Li dH (si , ah ) for i ∈ {1, . . . , t}. It immediately follows
that for each i ∈ {1, . . . , t}, it holds that if Pi = {i1 , . . . , ip }, then the constructed instance
(Ai , {J1i , . . . , Jpi }, di ) of Cluster Selection is a yes-instance. Hence, the algorithm returns a
colorful solution.
To evaluate the running time, recall that we consider 2O(k log k) partitions P = {P1 , . . . , Pt }
of nonempty subsets of {1, . . . , 2k}. Then for each P, we construct in polynomial time at most
k|P| instances of Cluster Selection. These instances are solved in time 2O(k log k) · (nm)O(1)
by Lemma 3. We conclude that the total running time of the algorithm that checks the existence
of a colorful solution is 2O(k log k) · (nm)O(1) .
Clearly, if for a random coloring of I, there is a colorful solution to (A, r, k), then (A, r, k)
is a yes-instance. We consider N = de2k e random colorings of I and for each coloring, we check
the existence of a colorful solution. If we find such a solution, we return it and stop. Otherwise,
if we failed to find a solution for all colorings, we return the answer NO. Recall that if (A, r, k)
is a yes-instance with a solution {I1 , . . . , Ir0 }, then the initial clusters that are included in the
composite clusters of the solution are colored by distinct colors with the probability at least
(2k)!
≥ e−2k . Hence, the probability that a yes-instance has no colorful solution is at most
(2k)2k
(1−e−2k ) and, therefore, the probability that a yes-instance has no colorful solution for N ≥ e2k
16

2k

random colorings is at most (1 − e−2k )e ≤ e−1 . We conclude that our randomized algorithm
returns a false negative answer with probability at most e−1 < 1. The total running time of the
algorithm is N · 2O(k log k) · (nm)O(1) , that is, 2O(k log k) · (nm)O(1) .
By the standard derandomization technique using perfect hash families, see [4, 56], our
algorithm can be derandomized. Thus, we conclude that Binary r-Means is solvable in the
deterministic time 2O(k log k) · (nm)O(1) .

4

Kernelization for Binary r-Means

In this section we show that Binary r-Means admits a polynomial kernel when parameterized
by r and k. Then we complement this result and Theorem 1 by proving that it is unlikely
that the problem has a polynomial kernel when parameterized by k only. Let us start from the
definition of a kernel, here we follow [18].
Roughly speaking, kernelization is a preprocessing algorithm that consecutively applies various data reduction rules in order to shrink the instance size as much as possible. Thus, such a
preprocessing algorithm takes as input an instance (I, k) ∈ Σ∗ × N of Q, works in polynomial
time, and returns an equivalent instance (I 0 , k 0 ) of Q. The quality of kernelization algorithm
A is measured by the size of the output. More precisely, the output size of a preprocessing
algorithm A is a function sizeA : N → N ∪ {∞} defined as follows:
sizeA (k) = sup{|I 0 | + k 0 : (I 0 , k 0 ) = A(I, k), I ∈ Σ∗ }.
Definition 2. A kernelization algorithm, or simply a kernel, for a parameterized problem Q
is an algorithm A that, given an instance (I, k) of Q, works in polynomial time and returns
an equivalent instance (I 0 , k 0 ) of Q. Moreover, sizeA (k) ≤ g(k) for some computable function
g : N → N.
If the upper bound g(·) is a polynomial function of the parameter, then we say that Q admits
a polynomial kernel .

4.1

Polynomial kernel with parameter k + r.

Theorem 2. Binary r-Means parameterized by r and k has a kernel of size O(k 3 (k + r)2 ).
Moreover, the kernelization algorithm in polynomial time either solves the problem or outputs an
instance of Binary r-Means with the matrix that has at most k + r pairwise distinct columns
and O(k 2 (k + r)) pairwise distinct rows.
Proof. Let (A, r, k) be an instance of Binary r-Means. Let a1 , . . . , an be the columns of
A = (aij ) ∈ {0, 1}m×n . We apply the following sequence of reduction rules.
Reduction Rule 4.1. If A has at most r pairwise distinct columns then output a trivial yesinstance and stop. If A has at least k + r + 1 pairwise distinct columns then output a trivial
no-instance and stop.
Let us remind that an initial cluster is an inclusion maximal set of equal columns of the
input matrix. To show that the rule is sound, observe first that if A has at most r pairwise
distinct columns, then the initial clusters form a solution. Therefore, (A, r, k) is a yes-instance.
Suppose that (A, r, k) is a yes-instance of BinaryP
r-Means. By Observation 1, there is a set
0
of means {c1 , . . . , cr } for some r0 ≤ r such that ni∈1 min{dH (cj , ai ) | 1 ≤ j ≤ r0 } ≤ k. It
0
immediately implies that A has at most k columns that are distinct from c1 , . . . , cr . Therefore,
A has at most r + k distinct columns.
Assume that Reduction Rule 4.1 is not applicable on the input instance. Then we exhaustively apply the following rule.
17

Reduction Rule 4.2. If A has an initial cluster I ⊆ {1, . . . , n} with |I| > k + 1, then delete
a column ai for i ∈ I.
Claim 4.1. Reduction Rule 4.2 is sound.
Proof of Claim 4.1. To show that the rule is sound, assume that A0 is obtained from A by the
application of Reduction Rule 4.2 to the initial cluster I and let ai be the deleted column. We
use the notation a1 , . . . , ai−1 , ai+1 , . . . an for the columns of A0 .
Suppose that (A, r, k) is a yes-instance. Let {I1 , . . . , Ir0 } be a solution with the means
0
1
c , . . . , cr . For j ∈ {1, . . . , r0 }, let Jj = Ij \ {i}. We have that
0

k≥

r X
X

0

j

h

dH (c , a ) ≥

j=1 h∈Ij

r X
X

dH (cj , ah )

j=1 h∈Jj

and, therefore, {J1 , . . . , Jr0 } is a solution for (A0 , r, k). Therefore, if (A, r, k) is a yes-instance,
then (A0 , r, k) is a yes-instance.
Now assume that (A0 , r, k) is a yes-instance. Then by Lemma 1, (A0 , r, k) admits a regular
0
solution {J1 , . . . , Jr0 } and we have that I 0 ⊆ Js for some s ∈ {1, . . . , r0 }. Denote by c1 , . . . , cr
the means of J1 , . . . , Jr0 obtained by the majority rule. We have that
0

k≥

r X
X

dH (cj , ah ) ≥

j=1 h∈Jj

X

dH (cs , ah ) ≥

X

dH (cs , ah ).

h∈I 0

h∈Js

Since |I 0 | ≥ k+1, we have that cs = ah for h ∈ I 0 . Hence, cs = ai . Let Ij = Jj for j ∈ {1, . . . , r0 },
j 6= s, and let Is = Js ∪ {i}. Because cs = ai , we obtain that
0

r X
X
j=1 h∈Ij

0

j

h

dH (c , a ) =

r X
X

dH (cj , ah ) ≤ k

j=1 h∈Jj

and {I1 , . . . , Ir0 } is a solution for (A, r, k). That is, if (A0 , r, k) is a yes-instance, then (A, r, k)
is also a yes-instance. This completes the soundness proof.
To simplify notations, assume that A with the columns a1 , . . . , an is the instance of Binary
r-Means obtained by the exhaustive application of Reduction Rule 4.2. Note that by Reduction
Rules 4.1 and 4.2, A has at most k + r pairwise distinct columns and n ≤ (k + 1)(k + r). This
means that we have that the number of columns is bounded by a polynomial of k and r. However,
the number of rows still could be large. Respectively, our aim now is to construct an equivalent
instance with the bounded number of rows.
We greedily construct the partition S = {S1 , . . . , Ss } of {1, . . . , n} using the following algorithm. Let i ≥ 1 be an integer and supposeSthat the sets S0 , . . . , Si−1 are already constructed
i−1
assuming that S0 = ∅. Let I = {1, . . . , n} \ j=0
Sj . If I 6= ∅, we construct Si :
• set Si = {s} for arbitrary s ∈ I and set I = I \ {s},
• while there is j ∈ I such that dH (aj , ah ) ≤ k for some h ∈ Si , then set Si = Si ∪ {j} and
set I = I \ {j}.
The crucial property of the partition S is that every cluster of a solution solution is entirely
in some of part of the partition. This way S separates the clustering problem into subproblems.
More precisely,
Claim 4.2. Let {I1 , . . . , Ir0 } be a solution for (A, r, k). Then for every i ∈ {1, . . . , r0 } there is
j ∈ {1, . . . , s} such that Ii ⊆ Sj .
18

0

Proof of Claim 4.2. Let c1 , . . . , cr be the means of I1 , . . . , Ir0 obtained by the majority rule.
For the sake of contraction, assume that there is a cluster Ii such that there are p, q ∈ Ii with
p and q in distinct sets of the partition {S1 , . . . , Ss }. Then dH (ap , aq ) > k. Therefore,
0

r X
X
j=1 h∈Ij

dH (cj , ah ) ≥

X

dH (ci , ah ) ≥ dH (ci , ap ) + dH (ci , aq ) ≥ dH (ap , aq ) > k

h∈Ii

contradicting that {I1 , . . . , Ir0 } is a solution.
We say that a row of a binary matrix is uniform if all its elements are equal. Thus a uniform
row consists entirely from 0s or from 1s. Otherwise, a row is nonuniform. We show that the
submatrices of A composed by the columns with indices from the same part of partition of S,
have a bounded number of nonuniform rows.
Claim 4.3. For every i ∈ {1, . . . , s}, the matrix A[{1, . . . , m}, Si ] has at most (|Si | − 1)k
nonuniform columns.
Proof of Claim 4.3. Let i ∈ {1, . . . , s} and ` = |Si |. Recall that Si is constructed greedily by
adding the index of a column that is at distance at most k from some columns whose index is
already included in Si . Denote respectively by I1 , . . . , I` the sets constructed on each iteration.
For every j ∈ {1, . . . , `}, we show inductively that A[{1, . . . , m}, Ij ] has at most (j − 1)k
nonuniform columns. The claim is trivial for j = 1. Let I2 = {p, q} for some distinct p, q ∈ Si ,
then because dH (ap , aq ) ≤ k, we have that ap and aq differ in at most k positions and, therefore,
A[{1, . . . , m}, I2 ] has at most k nonuniform rows.
Let j ≥ 3. Assume that p ∈ Ij \ Ij−1 . By the inductive assumption, A[{1, . . . , m}, Ij−1 ] has
at least m−(j −2)k uniform rows. Denote by J ⊆ {1, . . . , m} the set of indices of uniform rows of
A[{1, . . . , m}, Ij−1 ]. Since dH (ap , aq ) ≤ k for some q ∈ Ii−1 , there are at most k positions where
ap and aq are distinct. In particular, there are at most k indices of J for which the corresponding
elements of ap and aq are distinct. This immediately implies that A[{1, . . . , m}, Ij ] has at least
|J| − k ≥ m − (j − 2)k − k = m − (j − 1)k uniform rows. Hence, A[{1, . . . , m}, Ij ] has at most
(j − 1)k nonuniform rows.
Now we proceed with the kernelization algorithm. The next rule is used to deal with trivial
cases.
Reduction Rule 4.3. If s > r, then output a trivial no-instance and stop.
The soundness of the rule is immediately implied by Claim 4.2. From now we assume that
s ≤ r.
Observe that if all the rows of the matrix A[{1, . . . , m}, Si ] are uniform, then Si is an initial
cluster. Since after the application of Reduction Rule 4.1 the number of initial clusters is at
least r + 1, we have that for some i ∈ {1, . . . , s}, matrix A[{1, . . . , m}, Si ] contains nonuniform
rows. Let `i be the number of nonuniform rows in A[{1, . . . , m}, Si ] for i ∈ {1, . . . , s}, and let
` = max1≤i≤s `i . For each i ∈ {1, . . . , s}, we find a set of indices Ri ⊆ {1, . . . , m} such that
|Ri | = ` and A[Ri , Si ] contains all nonuniform rows of A[{1, . . . , m}, Si ]. For i ∈ {1, . . . , s}, we
define Bi = A[Ri , Si ]. For i ∈ {1, . . . , s}, we denote by 0i and 1s d(k + 1)/2e × |Si |-matrix with
all the elements 0 and 1 respectively. We use the matrices Bi , 0i and 1i as blocks to define


B1 B2 · · · Bs
 11 02 · · · 0s 


 01 12 · · · 0s 
D=

 .
.. . .
.. 
 ..
. . 
.
01

02
19

···

1s

We denote the columns of D by

d1 , . . . , dn

following the convention that the columns of

Bi
..
.

!

are indexed by j ∈ Si according to the indexing of the corresponding columns of A.
Then our kernelization algorithm returns the instance (D, r, k) of Binary r-Means.
The correctness of the algorithm is based on the following claim.
Claim 4.4. (A, r, k) is a yes-instance of Binary r-Means if and only if (D, r, k) is a yesinstance.
Proof of Claim 4.4. We show that {I1 , . . . , Ir0 } is a solution for (A, r, k) if and only if {I1 , . . . , Ir0 }
is a solution for (D, r, k).
0
Suppose that {I1 , . . . , Ir0 } is a solution for (A, r, k). Denote by c1 , . . . , cr the means of
0
the clusters of the solution obtained by the majority rule. Let s1 , . . . , sr be the means of
the corresponding clusters for D obtained by the majority rule. By Claim 4.2, for every i ∈
{1, . . . , r0 }, there is j ∈ {1, . . . , s} such that Ii ⊆ Sj . Notice that by the construction of D, it
holds that for every p ∈ Sj , dH (ap , ci ) = dH (dp , si ), because all the rows of A[{1, . . . , m}\Ri , Si ]
and all the rows of D[{` + 1, . . . , m}, Si ] are uniform. Therefore,
0

r X
X

0

i

j

dH (s , d ) =

i=1 j∈Ii

r X
X

dH (ci , aj ) ≤ k

i=1 j∈Ii

and {I1 , . . . , Ir0 } is a solution for (D, r, k).
0
Assume that {I1 , . . . , Ir0 } is a solution for (D, r, k) and denote by s1 , . . . , sr the means of
the clusters for D obtained by the majority rule.
We observe that for every i ∈ {1, . . . , r0 } there is j ∈ {1, . . . , s} such that Ii ⊆ Sj . To see
this, assume that this is not the case and there is a cluster Ii such that there are p, q ∈ Ii with
p and q in distinct sets of the partition {S1 , . . . , Ss }. Then dH (dp , dq ) > k by the construction
of D as dp and dq differ in at least 2d(k + 1)/2e positions. Therefore,
0

r X
X

dH (sj , dh ) ≥

j=1 h∈Ij

X

dH (si , dh ) ≥ dH (si , dp ) + dH (si , dq ) ≥ dH (dp , dq ) > k

h∈Ii

contradicting that {I1 , . . . , Ir0 } is a solution.
0
Let c1 , . . . , cr be the means of the corresponding clusters for A obtained by the majority
rule. Since for every i ∈ {1, . . . , r0 }, there is j ∈ {1, . . . , s} such that Ii ⊆ Sj , we again obtain
that for every p ∈ Sj , dH (ap , ci ) = dH (dp , si ). Hence,
0

r X
X

0

i

j

dH (c , a ) =

i=1 j∈Ii

r X
X

dH (si , dj ) ≤ k

i=1 j∈Ii

and {I1 , . . . , Ir0 } is a solution for (A, r, k).
Finally, to bound the size D, recall that D has n ≤ (k + 1)(k + r) columns and at most k + r
of them are pairwise distinct. The matrices B1 , . . . , Bs have ` rows where ` is the maximum
number of nonuniform rows in A[{1, . . . , m}, Si ]. By Claim 4.3,
` = max (|Si | − 1)k ≤ (n − 1)k ≤ ((k + 1)(k + r) − 1)k.
1≤i≤s

Because s ≤ r, we obtain that D has at most ((k +1)(k +r)−1)k +d(k +1)/2er rows. Therefore,
D has O(k 3 (k+r)2 ) elements. Note also that D has at most ((k+1)(k+r)−1)k+r = O(k 2 (k+r))
pairwise distinct rows. This completes the correctness proof.
20

To evaluate the running time, observe that Reduction Rules 4.1–4.3 demand polynomial
time. The greedy algorithm that was used to construct the partition S = {S1 , . . . , Ss } of
{1, . . . , n} is trivially polynomial. The construction of B1 , . . . , Bs is also polynomial and, therefore, D is constructed in polynomial time.

4.2

Ruling out polynomial kernel with parameter k.

Our next aim is to show that Binary r-Means parameterized by k does not admit a polynomial
kernel unless NP ⊆ coNP /poly. We do this in two steps. First, we use the composition technique
introduced by Bodlaender et al. [10] (see also [18] for the introduction to this technique) to show
that it is unlikely that the Consensus String with Outliers problem introduced by Boucher,
Lo and Lokshtanov in [11] has a polynomial kernel. Then we use this result to prove the claim
for Binary r-Means.
Consensus String with Outliers
Input:
Task:

A (multi) set of p strings S = {s1 , . . . , sn } of the same length ` over an
alphabet Σ, a positive integer r and nonengative integer d.
Decide whether there isPa string s of length ` over Σ and I ⊆ {1, . . . , n}
with |I| = r such that i∈I dH (s, si ) ≤ d.

Boucher, Lo and Lokshtanov in [11] investigated parameterized complexity of Consensus
String with Outliers and obtained a number of approximation and inapproximability results. In particular, they proved that the problem is FPT when parameterized by d. We show
that it is unlikely that this problem has a polynomial kernel for this parameterization.
Theorem 3. Consensus String with Outliers has no polynomial kernel when parameterized by d unless NP ⊆ coNP /poly even for strings over the binary alphabet. Moreover, the result
holds for the instances with r ≤ d.
Proof. We use the fact that Consensus String with Outliers is NP-complete for strings
over the binary alphabet Σ = {0, 1} [11] and construct a composition algorithm for the problem
parameterized by d.
Let (S1 , r, d), . . . , (St , r, d) be instances of Consensus String with Outliers where S1 , . . . , St
are (multi) sets of binary strings of the same length `. Denote by 0̄ and 1̄ the strings of length
d + 1 composed by 0s and 1s respectively, that is,
0̄ = 0| .{z
. . 0} and 1̄ = |1 .{z
. . 1} .
d+1

d+1

For i ∈ {1, . . . , t}, we define the set of strings
Si0 = {s0̄i−1 1̄0̄t−i | s ∈ Si }.
Then we put S ∗ = ∪ti=1 Si0 and consider the instance (S ∗ , r, d) of Consensus String with
Outliers.
We show that (S ∗ , r, d) is a yes-instance of Consensus String with Outliers if and only
if there is i ∈ {1, . . . , t} such that (Si , r, d) is a yes-instance.
Assume that for i ∈ {1, . . . , t}, the strings of Si and Si0 are indexed by indices from a set
Ii , where I1 , . . . , It are disjoint, and denote the strings of S = ∪ti=1 Si and S ∗ by sj and s0j
respectively for j ∈ ∪ti=1 Ii .

21

Suppose that there is i ∈ {1, . . . , t} such that (Si , r, d) is a yes-instance of Consensus
String with
P Outliers. Then there is I ⊆ Ii such that |I| = r and a binary string s of length
` such that i∈I dH (s, si ) ≤ d. Let s0 = s0̄i−1 1̄0̄t−i . Since I ⊆ Ii , we have that
X
X
dH (s0 , s0i ) =
dH (s, si ) ≤ d,
i∈I

i∈I

that is, (S ∗ , r, d) is a yes-instance.
Assume that (S ∗ , r, d) is a yes-instance of Consensus String with Outliers. Then
there
is I ⊆ ∪ti= Ii such that |I| = r and a binary string s0 of length ` + (d + 1)t such that
P
0 0
i∈I dH (s , si ) ≤ d. We show that there is i ∈ {1, . . . , t} such that I ⊆ Ii . To obtain a
contradiction, assume that there are distinct i, j ∈ {1, . . . , t} such that I ∩ Ii 6= ∅ and I ∩ Ij 6= ∅.
Let p ∈ I ∩ Ii and q ∈ I ∩ Ij . We conclude that
X
dH (s0 , s0h ) ≥ dH (s0 , s0p ) + dH (s0 , s0q ) ≥ dH (s0p , s0q )
h∈I

≥ dH (0̄i−1 1̄0̄t−i , 0̄j−1 1̄0̄t−j ) ≥ 2(d + 1) > d,
which is a contradiction. Hence, there is i ∈ {1, . . . , t} such that I ⊆ Ii . Let s be a substring of
s0 containing the first ` symbols. We have that
X
X
dH (s, sh ) =
dH (s0 , s0h ) ≤ d,
h∈I

h∈I

that is, (Si , r, d) is a yes-instance of Consensus String with Outliers.
P
Observe that every string of S ∗ is of length ` + (d + 1)t and that |S ∗ | = ti=1 |Si |. This
means that the size of (S ∗ , r, d) is polynomial in the sum of the sizes of (Si , r, d) and t. Note also
that the parameter d remains the same. By the results of Bodlaender et al. [10], we conclude
that Consensus String with Outliers has no polynomial kernel when parameterized by d
unless NP ⊆ coNP /poly.
To see that the result holds even if r ≤ d, we observe that for r ≥ d + 1, Consensus String
with Outliers is solvable in polynomial time. Let (S, r, d) be a yes-instance of Consensus
String with Outliers where S = {s
P1 , . . . , sn } and r ≥ d + 1. Then there is a string s and
I ⊆ {1, . . . , n} with |I| = r such that i∈I dH (s, si ) ≤ d. Since |I| = r ≥ d + 1, there is i ∈ I
such that s = si , that is, the mean string s is one of the input strings. This brings us to the
following simple algorithm. Let (S, r, d) be an instance of Consensus String with Outliers
with S = {s1 , . . . , sn } and r ≥ d + 1. For each i ∈ {1, . . . , n}, we check whether the instance
has a solution with s = si . We do it by the greedy selection of r strings closest to s (in the
Hamming distance). It is straightforward to see that this is a polynomial time algorithm solving
the problem.
We use Theorem 3 to obtain our kernelization lower bound for Binary r-Means.
Theorem 4. Binary r-Means has no polynomial kernel when parameterized by k unless NP ⊆
coNP /poly.
Proof. We reduce Consensus String with Outliers to Binary r-Means.
Let (S, r, d) be an instance of Consensus String with Outliers, where S = {s1 , . . . , sn }
is a (multi) set of binary strings of length ` and r ≤ d. Denote by 0̄ and 1̄ the strings of
length d + 1 composed by 0s and 1s respectively. For i ∈ {1, . . . , n}, we set s0i = si 0̄i−1 1̄0̄n−i .
We construct the matrix A considering s01 , . . . , s0n to be vectors of {0, 1}`+(d+1)n composing the
columns of A. Slightly abusing notation, we use s01 , . . . , s0n to denote the columns of A. We set
k = (d + 1)r + d and set r0 = n − r + 1.
22

We claim that (S, r, d) is a yes-instance of Consensus String with Outliers if and only
if (A, r0 , k) is a yes-instance of Binary r-Means.
Suppose that (S, r, d) is a yes-instance of Consensus String with Outliers.
Let I ⊆
P
{1, . . . , n} and a string s of length ` be a solution, that is, |I| = r and i∈I dH (s, si ) ≤ d.
Denote s0 = s0̄n . By the definition of s01 , . . . , s0n , we have that
X
dH (s0 , s0i ) ≤ d + (d + 1)r.
i∈I

We construct clusters I1 , . . . , Ir0 for (A, r0 , k) as follows. We put I1 = I and let I2 , . . . , Ir0 be
one-element disjoint subsets of {1, . . . , n} \ I. Then we define the means c1 , . . . , cn as follows.
We set c1 = s0 considering s0 to be a binary vector. For every single-element cluster Ii = {j}
for i ∈ {2, . . . , r0 }, we set ci = s0j . Note that dH (ci , sj ) = 0 for i ∈ {2, . . . , n} and j ∈ Ii . Then
we have
r0 X
X
X
X
dH (ci , s0j ) =
dH (c1 , s0j ) =
dH (s0 , s0j ) ≤ d + (d + 1)r ≤ k,
i=1 j∈Ii

j∈I

j∈I

(A, r0 , k).

that is, {I1 , . . . , Ir0 } is a solution for
This means that (A, r0 , k) is a yes-instance of
Binary r-Means.
Assume that (A, r0 , k) is a yes-instance of Binary r-Means. Let {I1 , . . . , Ip }, p ≤ r0 , be a
solution. Denote by c1 , . . . , cp the corresponding means obtained by the majority rule. If r = 1,
then (S, r, d) is a trivial yes-instance of Consensus String with Outliers. Let r ≥ 2. Then
because r0 = n − r + 1, we have that there are clusters Ij with at least two elements. We assume
that |Ij | ≥ 2 for j ∈ {1, . . . , q} for some q ≤ p and |Ij | = 1 for j ∈ {q + 1, . . . , p}.
We
P show that q = 1. Targeting towards a contradiction, let us assume that q ≥ 2. We have
that qi=1 |Ii | = n − (p − q), that is, n − (p − q) columns of A are in clusters with at least two
elements. By the construction of A, we have that the last n(d + 1) elements of each mean ci
are 0s for i ∈ {1, . . . , q}, because the means were constructed by the majority rule. This implies
that dH (ci , s0j ) ≥ d + 1 for j ∈ Ii and i ∈ {1, . . . , q}. Clearly, dH (ci , s0j ) = 0 for j ∈ Ii and
i ∈ {q + 1, . . . , p} as these clusters Ii contain one element each. Then
p X
X

dH (ci , s0j ) =

i=1 j∈Ii

q X
X

dH (ci , s0j ) ≥

i=1 j∈Ii
0

q
X

|Ii |(d + 1) = (n − (p − q))(d + 1)

i=1

≥(n − r + 2)(d + 1) = (r + 1)(d + 1) > k

contradicting that {I1 , . . . , Ip } is a solution. Therefore, q = 1.
We have that |I1 | = n − p + 1 ≥ n − r0 + 1 = r. Let I ⊆ I1 with |I| = r. Recall that
we defined the string s0j = sj 0̄j−1 1̄0̄n−j for j ∈ {1, . . . , n} and we consider these strings as the
columns of A. In particular, the first ` elements correspond to sj and the last n(d + 1) elements
correspond to the string 0̄j−1 1̄0̄n−j . As above, we have that the last n(d + 1) elements of c1 are
0s. Denote by s the vector composed by the first ` elements of c1 . We have that
X

dH (c1 , s0j ) ≤

j∈I

X

dH (c1 , s0j ) ≤

j∈I1

p X
X

dH (ci , s0j ) ≤ k = (d + 1)r + d.

i=1 j∈Ii

Since
X

dH (c1 , s0j ) =

j∈I

X
X
(dH (s, sj ) + (d + 1)) =
dH (s, sj ) + (d + 1)r,
j∈I

j∈I

P

we conclude that j∈I (dH (s, sj ) ≤ d. This implies that (S, r, d) is a yes-instance of Consensus
String with Outliers.
23

Summarizing, we have constructed a parameterized reduction of Consensus String with
Outliers to Binary r-Means. Notice that for the new parameter k of Binary r-Means,
we have that k = (d + 1)r + d = O(d) since r ≤ d. This observation together with Theorem 3
implies that Binary r-Means has no polynomial kernel when parameterized by k unless NP ⊆
coNP /poly.

5

Subexponential algorithms for Binary r-Means and Low GF(2)Rank Approximation

We have already seen that Binary r-Means is solvable in time 2O(k log k) ·(nm)O(1) (Theorem 1)
and Low GF(2)-Rank Approximation is solvable in time 2O(k log r) ·(nm)O(1) (Proposition 1).
In this section we show that with respect to the combined parameterization by k and r, there
are algorithms for Binary r-Means and Low GF(2)-Rank Approximation which runs in
time
√ subexponential in k. For constant rank r, the running times of these algorithms are in
2O( k log k) · (nm)O(1) , which outperforms the algorithms from Theorem 1 and Proposition 1.
On the other hand, in both cases we are paying for the improvements on the dependency on k
by making the dependency on r worse. In Subsection 5.1 we construct an algorithm for Binary
r-Means and in Subsection 5.2 for Low GF(2)-Rank Approximation.

5.1

Subexponential algorithm for Binary r-Means

In this section we design a subexponential (in k) time algorithm for Binary r-Means.
√
Theorem 5. Binary r-Means is solvable in time 2O(r k log(k+r)) · (nm)O(1) .
Towards the proof of Theorem 5, we prove some auxiliary lemmas.
We will be seeking for a special type of solutions.
Definition 3. Let A be an m × n-matrix with rows a1 , . . . , am . We say that a vector c =
(c1 , . . . , cm )| ∈ {0, 1}m agrees with A if ci = cj whenever ai = aj for i, j ∈ {1, . . . , m}.
We will be using the following properties of vectors that agree with matrix A.
Lemma 4. Let (A, r, k) be a yes-instance of Binary r-Means. Then (A, r, k) has a solution
such that for each cluster of the solution its mean agrees with A.
Proof. Let {I1 , . . . , Ir0 } be a solution to (A, r, k). For i ∈ {1, . . . , r0 }, let ci = (ci1 , . . . , cim )| ∈
{0, 1}m be the mean of the cluster Ii computed by the majority rule. Then if aj and ah are rows
of A and aj = ah , then cij = cih because the majority rule computes the same value. Hence, we
have that ci agrees with A for each i ∈ {1, . . . , r0 }.
Lemma 5. Let A be a binary m × n matrix with at
of A
t different rows, a be a column
Pmost
h
t
m
and h be a positive integer. Then there are at most i=1 i binary vectors b ∈ {0, 1} agreeing
with A and which are within the Hamming distance at most h from a.
Proof. Let I1 , . . . , It be the partition of rows of A into inclusion-maximal sets of equal rows.
Vector a agrees with A. Also for every vector b that agrees with A there is J ⊆ {1, . . . , t}, such
that b is obtained from a by changing for every i ∈ J the coordinates corresponding to all rows
from Ii . But since the distance from aPand bis at most h, the size of J is at most h. Hence,
the number of such vectors is at most hi=1 ti .
Now we are ready to prove Theorem 5.
24

Proof of Theorem 5. Let (A, r, k) be an instance of Binary r-Means with A = (a1 , . . . , an ).
First, we preprocess the instance using the kernelization algorithm from Theorem 2. If the
algorithm solves the problem, we return the answer and stop. Assume that this is not the case.
Then the algorithm return an instance of Binary r-Means where the matrix has at most k + r
pairwise distinct columns and O(k 2 (k + r)) pairwise distinct row. To simplify notations, we
use the same notation (A, r, k) for the obtained instance. Denote by w the number of pairwise
distinct rows of A.
Informally, our algorithm does the following. For a given partial clustering of some columns
of A, budget d and a new subset I of columns of A which have to be clustered, it tries to extend
the partial solution by not exceeding the budget d. Some of the columns from I can go to the
existing cluster and some can form new clusters. Suppose that we know the minimum distance
h from vectors in new cluster to their means. Then all vectors which are within the distance
less than h to the already existing means, can be assigned to the existing clusters. Then we will
be basically left with
√ two options. Either the number of columns to be assigned to new clusters
does not exceed p
d log w; in this case we brute-force in all possible partitions of I. Or we can
upper bound h ≤ k/ log w and invoke recursive arguments based on Lemma 5.
Let us give a formal description of the algorithm. Towards that we design a recursive
algorithm Extend-Means. The input of Extend-Means is a set I ⊆ {1, . . . , n}, a set of
vectors S ⊆ {0, 1}m of size at most r that agree with A, and a nonnegative integer d, The
m
ouput of Extend-Means is a set of vectors
P C ⊆ {0, 1} i of size at most r such that each of
the vectors agrees with A, S ⊆ C, and i∈I min{dH (c, a ) | c ∈ C} ≤ d (if such set exists).
We say that such a set C is a solution. Thus we are looking for a solution extending the partial
solution S for the set of column vectors indexed by I.
To solve Binary r-Means, we call Extend-Means(I = {1, . . . , n}, S = ∅, d = k). The
correctness of this step follows from Observation 1 and Lemma 4. Algorithm Extend-Means
performs in 4 steps.
P
Step 1. If i∈I min{dH (s, ai ) | s ∈ S} ≤ d, then S itself satisfies the conditions of the ouput.
In this case we return C = S and stop.
Step 2. If |S| = r, then we cannot add vectors to S. Return NO and stop.
Step 3. For every h = 0, . . . , d, do the following.
(i) For every i ∈ I, if ` = min{dH (s, ai ) | s ∈ S} ≤ h − 1, then set I = I \ {i} and d = d − `.
√
(ii) If |I| ≤ d log w, then for each p ≤ min{|I|, r − |S|}, consider all possible partitions
{J0 , . . . , Jp } of I, where J0 could be empty, and do the following:
– for every j ∈ {1, . . . , p}, find the optimal mean sj for the cluster Jj using the majority
rule;
– set S = S ∪ {s1 , . . . , sp },
P
– if i∈I min{dH (s, ai ) | s ∈ S} ≤ d, then return C = S and stop.
If we do not return a solution and do not stop for any value of p and choice of {J0 , . . . , Jp },
then return NO and stop.
(iii) If h ≤ d/|I|, then for each vector s ∈ {0, 1}m that agrees with A and such that dH (s, ai ) =
h for some i ∈ I do the following: call Extend-Means{I, S ∪ {s}, d} and if the algorithm
returns a solution C, then return it and stop.
Step 4. Return NO and stop.
25

Correctness. Now argue for the correctness of the algorithm. First of all, by its construction,
if the algorithm returns
P a set of vectors C, then each of the vectors from C agrees with A,
|C| ≤ r, S ⊆ C, and i∈I min{dH (c, ai ) | c ∈ C} ≤ d.
Now we show that if there is a solution to (I, S, d) then the algorithm returns a solution.
The proof is by induction on r − |S|. We assume that there is a solution to (I, S, d). The base
case is when |S| = r. Then C = S is a solution and the algorithm returns C in Step 1.
Now we consider the induction step. That is |S| < r. By induction hypothesis we have that
for any S 0 ⊃ S of size at most r, I 0 ⊆ {1, . . . , n} and a nonnegative integer d0 such that each
vector from S 0 agrees with A, the algorithm returns a solution to the input (S 0 , I 0 , d0 ) if such a
solution exists.
If S is a solution, then the algorithm outputs it in Step 2 and we are done. Now we assume
that S is not a solution. Since S is not a solution and therePis a solution to (I, S, d) (by
assumption), we have that there is a solution C ⊃ S such that i∈I min{dH (c, ai ) | c ∈ C} is
minimum and for every c ∈ C \ S, there is i ∈ I such that dH (s, ai ) ≥ dH (c, ai ) = h for all
s ∈ S. We choose such a solution C = C ∗ , c = c∗ ∈ C ∗ \ S and i = i∗ ∈ I in such a way that
the value of h is the minimized. Clearly, h ≤ d. We claim that the algorithm outputs a solution
in Step 3 for this value of h unless it already produced a solution for some lesser value of h. In
the later case we are done. So now we have that Step 3 is executed for value h. Let the set
J ⊆ I and an integer d0 be constructed as follows:
• set J = I and d0 = d,
• for every i ∈ J, if ` = min{dH (s, ai ) | s ∈ S} ≤ h − 1, then set J = J \ {i} and d0 = d0 − `.
Notice that for every j ∈ I \ J, min{dH (s, aj ) | s ∈ S} ≤ min{dH (c, aj ) | c ∈ C ∗ \ S}. Therefore,
(J, S, d0 ) is an equivalent input, that is, we have a solution for this input if and only if there is
a solution for the original input (I, S, d). Moreover, C ∗ is a solution for (J, S, d0 ). Observe also
that by the choice of h, i∗ ∈ J. Then for every c ∈ C ∗ and j ∈ J, dH (c, aj ) ≥ h. Note that for
the set I and the integer
d = d0 .
√ d0 constructed in Step 3 (i), we have that I = J and
∗
Suppose that |J| ≤ d log w. This case is considered in Step 3 (ii). Let C \S = {c1 , . . . , cp }.
We construct partition {J0 , . . . , Jp } of J whose sets could be empty as follows. For each i ∈ J,
find t = min{dH (c, ai ) | c ∈ C ∗ }. If t = dH (c, ai ) for c ∈ S, then include i ∈ J0 . Otherwise,
find minimum i ∈ {1, . . . , p} such that t = dH (ci , ai ) and include i in Ji . Assume without loss
of generality that J1 , . . . , Jp are nonempty. (Otherwise, we can just ignore empty sets.) For
each i ∈ {1, . .P
. , p}, let si be the P
optimum mean for the cluster Ji constructed by the majority
rule. Clearly, j∈Ji dH (si , aj ) ≤ j∈Ji dH (ci , aj ). Recall also that the majority rule constructs
vectors that agree with A. This implies that C 0 = S ∪ {s1 , . . . , sp } is a solution. Since in Step 4
we consider all p ≤ min{|I|, r − |S|} and all partitions of I into p + 1 subsets, the algorithm
outputs C 0 . That is the algorithm outputs
a solution.
√
From now we assume that |J| ≥ d0 log w. This case is analyzed in Step 3 (iii). Note that
for every c ∈ C ∗ and j ∈ J, dH (c, aj ) ≥ h. Hence, h ≤ d0 /|J|. In Step 3 (iii), for each vector
s ∈ {0, 1}m which agrees with A and which is a the Hamming distance at most h from some aj ,
j ∈ J, we call Extend-Means(J, S ∪ {s}, d0 ). We have that in some branch of the algorithm,
∗
we call Extend-Means(J, S ∪ {c∗ }, d0 ), because dH (c∗ , ai ) = h and i∗ ∈ J. By the inductive
assumption, the algorithm outputs a solution C 0 for the input (J, S ∪ {c∗ }, d0 ). Then C 0 is a
solution to (I, S, d).
To complete the correctness proof, note that the depth of the recursion is upper bounded
by r. It follows that the algorithm perform finite number of steps and returns either a solution
or the answer NO.
Running time. To evaluate the running time, note that Steps 1 and 2 can be done in polynomial time. In Step 3, we consider d + 1 ≤ k + 1 values of h and for each h, we perform
26

√
Steps 3 (i)–(iii). Step 3 (i) is √done in polynomial time. Since |I| ≤ d log w and p ≤ r in
Step 3 (ii), we consider 2O(log r k log w) partitions
of I in this step. Because w = O(k 2 (k + r)),
√
2
O(log r k log(k (k+r)))
Step 3 (ii) can
· (nm)O(1) . In Step 3 (iii), we have that
p be done inptime 2
h ≤ d/|I| ≤ d/ log w ≤ k/ log w. Recall that A has at most r + k pairwise-distinct columns.
Hence, to construct s in Step 3 (iii), we consider at most r + k columns ai for i ∈ I. Recall also
that A √
has w distinct rows. Since s agrees with A, by Lemma 5, we have that there are at most
O(log w k/ log w
2
vectors s at the Hamming distance at most h from ai . It follows
√ that Step 3 (iii)
O(log w k/ log w)
without recursive√calls of Extend-Means can be performed in time 2
· (nm)O(1)
k
log
w)
O(
recursive calls of the algorithm. The depth of the recursion is upper
and we have 2
bounded by r. Using the
that w = O(k 2 (k + r)),
√ property
√ we have that the total running time
2
O(r k log(k+r))
O(r k log k (k+r))
O(1)
of our algorithm is 2
· (nm)
or 2
· (nm)O(1) .

5.2

Subexponential algorithm for Low GF(2)-Rank Approximation

In this subsection we prove the following theorem.
Theorem 6. Low GF(2)-Rank Approximation is solvable in time 2O(r

3/2

√

k log k) · (nm)O(1) .

The general idea of parameterized subexponential time algorithm for Low GF(2)-Rank
Approximation (Theorem 6)is similar to the parameterized subexponential time algorithm for
Binary r-Means. However, because we cannot use the majority rule like the case of Binary
r-Means, there are some complications. We start with some auxiliary lemmas and then prove
Theorem 6.
Lemma 6. Let (A, r, k) be a yes-instance of Low GF(2)-Rank Approximation. Then A
has at most 2r + k pairwise-distinct columns and at most 2r + k pairwise-distinct rows.
Proof. Since (A, r, k) is a yes-instance of Low GF(2)-Rank Approximation, there is an
m×n-matrix B over GF(2) with rank(B) ≤ r such that kA−Bk2F ≤ k. By Observation 2, B has
at most 2r pairwise-distinct columns and at most 2r pairwise-distinct rows. Since kA−Bk2F ≤ k,
we have that matrices A and B differ in at most k columns and in at most k rows. This
immediately implies the claim.
In this section it is more convenient to use the alternative formulation of Low GF(2)Rank Approximation from Observation 3: given an m × n-matrix A with columns a1 , . . . , an
over GF(2), a positive integer r and a nonnegative integer k, decide whether there is a positive
0
integer
r0 ≤ r and linearly
independent vectors c1 , . . . , cr ∈ {0, 1}m over GF(2) such that
Pn
L
i
j
0
i∈1 min{dH (s, a ) | s =
j∈I c , I ⊆ {1, . . . , r }} ≤ k. Respectively, throughout this section
0
we say that a set of vectors C = {c1 , . . . , cr } satisfying the above condition is a solution for
(A, r, k). Recall that a vector c = (c1 , . . . , cm )| ∈ {0, 1}m agrees with an m × n-matrix A with
rows a1 , . . . , am if ci = cj whenever ai = aj for i, j ∈ {1, . . . , m}.
Lemma 7. Let (A, r, k) be a yes-instance of Low GF(2)-Rank Approximation. Then
0
(A, r, k) has a solution C = {c1 , . . . , cr } such that ci agrees with A for all i ∈ {1, . . . , r0 }.
Proof. Denote by a1 , . . . , an and a1 , . . . , am the columns and rows of A, respectively. Let
0
C = {c1 , . . . , cr }, where ci = (ci1 , . . . , cim )| for i ∈ {1, . . . , r0 }, be a solution such that the total
number of pairs of integers p, q ∈ {1, . . . , m} such that ap = aq and there is i ∈ {1, . . . , n} such
that cip 6= ciq is minimum. We claim that each ci agrees with A. To obtain a contradiction,
assume that there are p, q ∈ {1, . . . , m} such that ap = aq and there is i ∈ {1, . . . , n} such that
cip 6= ciq . For i ∈ {1, . . . , n}, denote by J(i) ⊆ {1, . . . , n} the subset of indices such that
M
M
dH (
cj , ai ) = min{dH (s, ai ) | s =
cj , I ⊆ {1, . . . , r0 }}.
j∈I

j∈J(i)

27

L
For each j ∈ {1, . . . , m}, let sj = (sj1 , . . . , sjn ) where sji = h∈J(i) chj for i ∈ {1, . . . , n}. Assume
without loss of generality that dH (sp , ap ) ≤ dH (sq , aq ). For i ∈ {1, . . . , r0 }, denote by ĉi the
vector obtained from ci by replacing ciq with cip . We have that
n
X
i=1

dH (

M

h

i

c ,a ) ≤

n
X
i=1

h∈I(i)

dH (

M

ĉh , ai ).

h∈I(i)
0

This implies that the set of vectors Ĉ obtained from {ĉ1 , . . . , ĉr } by taking a maximum set
of linearly independent vectors, is a solution. But this contradicts the choice of C, because
ĉip = ĉiq = cip for i ∈ {1, . . . , r0 }. We conclude that the vectors of C agree with A.
Now we are ready to prove Theorem 6.
Proof of Theorem 6. Let (A, r, k) be an instance of Low GF(2)-Rank Approximation with
A = (a1 , . . . , an ). First, we preprocess the instance using Lemma 6. That is, if A has at least
2r + k + 1 pairwise-distinct columns or at least 2r + k + 1 distinct rows, we return the answer
NO and stop. Now on we assume that the number of pairwise-distinct columns as well as rows
is at most 2r + k.
As in the proof of Theorem 5, we construct an algorithm extending a partial solution.
Towards that we design a recursive algorithm Extend-Solution. Input of Extend-Solution
is a set I ⊆ {1, . . . , n}, a p-sized set of linearly independent vectors S = {s1 , . . . , sp } ⊆ {0, 1}m
over GF(2) that agree with A, and a nonnegative integer d. The output of Extend-Solution
0
is a set of linearly independent vectors C = {c1 , . .P
. , cr } ⊆ {0, 1}m over GF(2),
that
L such
j, J ⊆
c
each of them agrees with A, |C| ≤ r, S ⊆ C and i∈I min{dH (s, ai ) | s =
j∈J
{1, . . . , r0 }} ≤ d if it exists or concludes that no such set exists. We say that such a set C is
a solution and call (I, S, d) an instance of Extend-Solution. Then to solve Low GF(2)Rank Approximation, we call Extend-Solution({1, . . . , n}, ∅, k). For the simplicity of
explanation, we solve the decision version of the problem. Our algorithm could be easily modified
to produce a solution if it exists.
We denote by S = (s1 , . . . , sp ) the m × p-matrix whose columns are the vectors of S and
denote by s1 , . . . , sm its rows. For I ⊆ {1, . . . , n}, we define AI = A[{1, . . . , m}, I]. We denote
by aI1 , . . . , aIm the rows of AI . Our algorithm uses the following properties of S and AI .
Claim 5.1. A solution C for an instance (I, S, d) exists if and only if there is r0 ≤ r and
0
0
two r0 -tuples of vectors (x1 , . . . , xr ) and (y1 , . . . , yr ) with xi ∈ {0, 1}p and yi ∈ {0, 1}|I| for
i ∈ {1, . . . , r0 } such that
m
X
i=1

min{dH (y, (aIi )| ) | y =

M

yj , J ⊆ {1, . . . , r0 } and s|i =

j∈J

M

xj } ≤ d.

j∈J

Proof of Claim 5.1. For an m × p-matrix X and an m × q-matrix Y, we denote by (X|Y) the
augmentation of X by Y, that is, the m × (p + q)-matrix whose first p columns are the columns
of X and the last q columns are the columns of Y.
Note that we have a solution C for an instance (I, S, d) if and only if there is an m × |I|matrix ÂI such that rank(S|ÂI ) ≤ r and kAI − ÂI k2F ≤ d. This observation immediately
implies the claim.
Now we are ready to describe algorithm Extend-Solution. Let (I, S, d) be the input of
Extend-Solution. It performs in 4 steps.
P
L
Step 1. If i∈I min{dH (s, ai ) | s = j∈J sj , J ⊆ {1, . . . , p}} ≤ d, then return YES and stop.
Step 2. If p = r, then return NO and stop.
Step 3. For every h = 0, . . . , d, do the following.
28

L
(i) For every i ∈ I, if ` = min{dH (s, ai ) | s = j∈J sj , J ⊆ {1, . . . , p}} ≤ h − 1, then set
I = I \ {i} and d = d − `.
p
(ii) If |I| ≤ d log(2r + d), then do the following:
0

0

– for each r0 ≤ r, consider all possible r0 -tuples of vectors (x1 , . . . , xr ) and (y1 , . . . , yr )
with xi ∈ {0, 1}p and yi ∈ {0,
1}|I| for i ∈ {1, . . . , r0 }, and do the
if
P
L
L following:
|
m
I
|
j
0
j
i=1 min{dH (y, (ai ) ) | y =
j∈J y , J ⊆ {1, . . . , r } and si =
j∈J x } ≤ d,
then return YES and stop.
– Return NO and stop.
(iii) If h ≤ d/|I|, then consider each vector s ∈ {0, 1}m such that s agrees with A, s is linearly
independent with the vectors of S and dH (s, ai ) = h for some i ∈ I and do the following:
call Extend-Solution(I, S ∪ {s}, d) and if the algorithm returns YES, then return YES
and stop.
Step 4. Return NO and stop.
Correctness. The construction of the algorithm and Claim 5.1 imply that if the algorithm
returns YES, then there is a solution C for the instance (I, S, d).
Now we show the reverse direction. That is, we show that if there is a solution C for (I, S, d),
then the algorithm returns YES. We assume that there is a solution C for (I, S, d). The proof
is by induction on r − |S|. The base case is when |S| = r. In this case C = S and algorithm
returns YES in Step 1.
Now consider the induction step. That is, |S| < r. By the induction hypothesis we have
that for every I 0 ⊆ {1, . . . , n}, a set of size at most r linearly independent vectors S 0 ⊃ S that
agree with A, and a nonnegative integer d0 , the algorithm returns YES if a solution for the
input (S 0 , I 0 , d0 ) exists. If the algorithm output YES in Step 1, then we are done. Otherwise we
have that S is not a solution. Since |S| < r, Step 2 is not executed. SincePS is not a solution,
0
we have
C = {c1 , . . . , cr } ⊃ S minimizing the sum i∈I min{dH (c, ai ) |
L thatj for every solution
0
c =
j∈J c , J ⊆ {1, . . . , r }} satisfies the following property: There exists i ∈ I such that
for every linear combination
s ∈ {0, 1}m of vectors from S we have dH (s, ai ) > h, where
L
h = min{dH (c, ai ) | c = j∈J cj , J ⊆ {1, . . . , r0 }}. We choose a solution C = C ∗ and i = i∗ ∈ I
in such a way that
the value of h is minimum. Notice that there is a subset J ∗ ⊆ {1, . . . , r0 }
L
∗
6 ∅. We assume that c∗ ∈ C ∗ .
such that c∗ = j∈J ∗ cj , h = dH (c∗ , ai ) and S ∩ {cj : j ∈ J ∗ } =
∗
Otherwise, we L
just add c to the solution and exclude arbitrary cj ∈
/ S with j ∈ J ∗ from C ∗
0
(because c∗ = j∈J ∗ cj ). Let C ∗ = {c1 , . . . , cr }. Clearly, h ≤ d. We claim that the algorithm
outputs YES in Step 3 for this value of h unless it already produced the same answer for some
smaller value of h. Let the set I 0 ⊆ I and the integer d0 be constructed as follows:
• set I 0 = I and d0 = d,
• for every i ∈ I 0 , if ` = min{dH (s, ai ) | s =
I 0 = I 0 \ {i} and d0 = d0 − `.

L

j∈J

sj , J ⊆ {1, . . . , p}} ≤ h − 1, then set

Notice that for every j ∈ I \ I 0 ,
M
M
sj , J ⊆ {1, . . . , p}} ≤ min{dH (c, aj ) | c =
cj , J ⊆ {1, . . . , r0 }}.
min{dH (s, aj ) | s =
j∈J

j∈J

Because of the choice of h, we have a solution for (I 0 , S, d0 ) if and only if there is a solution
for the original input (I, S, d). Moreover, C ∗ is a solution for (I 0 , S, d0 ). Observe also that by
the choice of h we have that i∗ ∈ I 0 .
29

Note that for the set I and an
integer d constructed in Step 3 (i), we have that I = I 0
p
and d = d0 . Suppose that |I 0 | ≤ d0 log(2r + d0 ). This case is considered in Step 3 (ii). By
00
00
Claim 5.1, there is r00 ≤ r and two r00 -tuples of vectors (x1 , . . . , xr ) and (y1 , . . . , yr ) with
0
xi ∈ {0, 1}p and yi ∈ {0, 1}|I | for i ∈ {1, . . . , r00 } such that
m
X

min{dH (y, a|i ) | y =

i=1

M

yj , J ⊆ {1, . . . , r00 } and s|i =

j∈J

M

xj } ≤ d0 .

(2)

j∈J
00

Since our algorithm considers all r00 ≤ r and all possible r00 -tuples of vectors (x1 , . . . , xr ) and
00
0
(y1 , . . . , yr ) with xi ∈ {0, 1}p and yi ∈ {0, 1}|I | for i ∈ {1, . . . , r00 } and verifies (2), we obtain
that the algorithm outputs YES in Step
p3 (ii).
3 (iii).
From now we assume that |I 0 | > d0 log(2r + d0 ). This case is analyzed
Lin Step
0
0
j
i
Note that for every j ∈ I and J ⊆ {1, . . . , r }, dH (c, a ) ≥ h for c =
i∈J c . Hence,
h ≤ d0 /|I 0 |. In Step 3 (iii), we consider every vector s ∈ {0, 1}m such that s agrees with A,
s is linearly independent with the vectors of S and dH (s, aj ) = h for some j ∈ I 0 , and call
Extend-Solution(I 0 , S ∪ {s}, d0 ). We have that in some recursive call of the algorithm, we
∗
call Extend-Solution(J, S ∪ {c∗ }, d0 ), because dH (c∗ , ai ) = h and i∗ ∈ I 0 . By the induction
hypothesis, the algorithm outputs YES for the input (I 0 , S ∪ {c∗ }, d0 ). Then we output YES for
(I, S, d).
To complete the correctness proof, note that the depth of the recursion is at most r. It
follows that the algorithm performs a finite number of steps and correctly reports that (I, S, d)
is a yes-instance or a no-instance.
Running time. To evaluate the running time, note that Steps 1 and 2 can be done in
polynomial time. In Step 3, we consider d + 1 ≤ k + 1 values of h and for each h, perform Steps 3 (i)–(iii).p Because p ≤ r,pStep 3 (i) can be done in time 2O(r) · (nm)O(1) .
Since r0 ≤ r,
d log(2r + d) ≤
k log(2r + k) and p ≤ r in Step 3 (ii), we con√ |I| ≤
0

r

0

sider 2O(r(r+ k log(2 +k))) r0 -tuples
of vectors (x1 , . . . , xr ) and (y1 , . . . , yr ). It implies that
√
O(r(r+ k log(2r +k)))
Step
· (nm)O(1) . In Step 3 (iii), we have that h ≤ d/|I| ≤
p 3 (ii) takes time
p 2
d/ log(2r + d) ≤ k/ log(2r + k). Recall that A has at most 2r + k pairwise-distinct columns.
Hence, to construct s is Step 3 (iii), we consider at most 2r + k columns ai for i ∈ I. Recall
r
also that A has at
√ most 2 + k distinct rows. Since s agrees with A, by Lemma 5, there are at
O(log(2r +k) k/ log(2r +k)
most 2
vectors s at distance h from ai . It follows
that Step 3 (iii) without
√
O( k log(2r +k))
recursive√calls of Extend-Solution can be done in time 2
· (nm)O(1) and we
r
have 2O( k log(2 +k)) recursive calls of the algorithm. The√depth of the recursion is at most r.
r
Therefore, the total√running time of our algorithm is 2O(r k log(2 +k)) · (nm)O(1) which is upper
3/2 k log k)
bounded by 2O(r
· (nm)O(1)

6

Subexponential algorithms for P-Matrix Approximation and
Low Boolean-Rank Approximation

In this section we give a parameterized subexponential algorithm for Low Boolean-Rank
Approximation. This algorithm is more complicated than the one for Low GF(2)-Rank
Approximation. The main reason to that is that now the elements of the matrices along
with the boolean operations do not form a field and thus many nice properties of matrix-rank
cannot be used here. The way we handle this issue is to solve the P-Matrix Approximation
problem. As far as we obtain a subexponential algorithm for P-Matrix Approximation, a
simple reduction will provide an algorithm for Low Boolean-Rank Approximation.
30

Let (A, P, k) be an instance of P-Matrix Approximation. We say that a matrix B is a
solution for the instance if kA − Bk2F ≤ k and B is a P-matrix.We need the following lemma.
Lemma 8. Let (A, P, k) be a yes-instance of P-Matrix Approximation where P is a p × qmatrix. Then A has at most p + k pairwise-distinct rows and at most q + k pairwise-distinct
columns.
Proof. Let B be a solution to (A, P, k). Then by Observation 4, B has at most p pairwisedistinct rows and at most q pairwise-distinct columns. Since A and B differ in at most k
elements, the claim follows.
Similarly to the algorithms for Binary r-Means and Low GF(2)-Rank Approximation
in Theorems 5 and 6 respectively, we construct a recursive branching algorithm for P-Matrix
Approximation. Recall that in the algorithms for Binary r-Means and Low GF(2)-Rank
Approximation, we solved auxiliary problems. In these auxiliary problems one has to extend a
partial solution while reducing the set of “undecided” columns. In particular, if the set of these
undecided columns is sufficiently small, we use brute force algorithms to solve the problems.
Here we use a similar strategy, but the auxiliary extension problem is slightly more complicated.
Following is the auxiliary extension problem.
Extendable P-Matrix Approximation
Input:

Task:

An m × n binary matrix A, a pattern p × q-matrix P, a partition
{X, Y, Z} of {1, . . . , n}, where some sets could be empty, such that
|X| + |Y | = q, and a nonnegative integer k.
Decide whether there is an m × n-matrix B such that
i) B[{1, . . . , m}, X] = A[{1, . . . , m}, X], ii) B and B[{1, . . . , m}, X ∪ Y ]
are P-matrices, and iii) kA − Bk2F ≤ k.

We call a matrix B satisfying i)–iii) solution for Extendable P-Matrix Approximation.
The following lemma will be used in the algorithm when the sum |Y | + |Z| is sufficiently small.
Lemma 9. Extendable P-Matrix Approximation is solvable in time 2O(p(r+log k)+p log p+q log q) ·
(nm)O(1) , where r = |Y | + |Z|.
Proof. Let (A, P, {X, Y, Z}, k) be an instance of Extendable P-Matrix Approximation.
Let a1 , . . . , an be the columns and a1 , . . . , am be the rows of matrix A = (aij ) ∈ {0, 1}m×n .
If A has at least p + k + 1 pairwise-distinct rows or q + k + 1 pairwise-distinct columns we
return NO, and stop. This is correct by Lemma 8. Also if m < p or n < q, we have a trivial
no-instance and we again can safely return NO and stop. From now we assume that m ≥ p,
n ≥ q, and that A has at most p + k pairwise-distinct rows and at most q + k pairwise-distinct
columns.
Suppose that matrix B with the rows b1 , . . . , bm is a solution to (A, P, {X, Y, Z}, k). We
say that a set I ⊆ {1, . . . , m} represents P with respect to B if a) |I| = p, b) B[I, {1, . . . , n}]
and B[I, X ∪ Y ] are P-matrices, and c) for every i ∈ {1, . . . , m} \ I, there is j ∈ I such that
bi = bj . Clearly, for every solution B, there is I ⊆ {1, . . . , m} that represents P with respect
to B.
We say that two sets of indices I, I 0 ⊆ {1, . . . , m} are equivalent with respect to A if
the matrices A[I, {1, . . . , n}] and A[I 0 , {1, . . . , n}] are isomorphic. Observe that if I, I 0 are
equivalent with respect to A, then (A, P, {X, Y, Z}, k) has a solution B such that I represents
P with respect to B if and only if the same instance has a solution B0 such that I 0 represents
P with respect to B0 .
31

Since A has at most p + k pairwise-distinct rows, there are at most (p + k)p pairwise
nonequivalent with respect to A sets of indices I ⊆ {1, . . . , m} of size p. We consider such
sets and for each I, we check whether there is a solution B for (A, P, {X, Y, Z}, k) with I
representing P with respect to B. If we find that there is a solution, we return YES and stop,
and we return NO if there is no solution for every choice of I. From now we assume that I is
given.
Our aim now is to check the existence of a solution B = (bij ) ∈ {0, 1}m×n with I representing
P with respect to B. We denote by b1 , . . . , bm the rows of B.
We consider all possible matrices B[I, {1, . . . , n}]. Recall that for each i ∈ {1, . . . , m}, we
should have that bij = aij for j ∈ X. It implies that there are at most 2|Y |+|Z| possibilities to
restrict bi for i ∈ I, and there are at most 2(|Y |+|Z|)p possible matrices B[I, {1, . . . , n}]. Since
the matrix should satisfy the condition b), we use Observation 5 to check this condition in time
2O(p log p+q log q) · (nm)O(1) . If it is violated, we discard the current choice of B[I, {1, . . . , n}].
Otherwise, we check whether B[I, {1, . . . , n}] can be extended to a solution B satisfying c). For
i, j ∈ {1, . . . , m}, we define
(
dH (bi , aj ) if bih = ajh for h ∈ X,
d∗H (bi , aj ) =
+∞
otherwise.
Then we observe that B[I, {1, . . . , n}] can be extended to a solution B satisfying c) if and only
if
X
X
dH (bi , ai ) +
min{d∗H (bi , aj ) | i ∈ I} ≤ k.
i∈I

j∈{1,...,m}\I

We verify the condition and return YES and stop if it holds. Otherwise we discard the current
choice of B[I, {1, . . . , n}]. If we fail for all choices of B[I, {1, . . . , n}], we return NO and stop.
It remains to evaluate the running time. We can check in polynomial time whether A has
at most p + k rows and at most q + k columns. Then we construct at most (p + k)p pairwise
nonequivalent (with respect to A) sets of indices I ∈ {1, . . . , m} of size p and for each I, we
consider at most 2(|Y |+|Z|)p possible matrices B[I, {1, . . . , n}]. Then for each choice of matrix
B[I, {1, . . . , n}], we first check in time 2O(p log p+q log q) · (nm)O(1) whether this matrix satisfies
b) and then check in polynomial time whether B[I, {1, . . . , n}] can be extended to a solution.
We obtain that the total running time is 2O(p(log k+|Y |+|Z|)+p log p+q log q) · (nm)O(1) .
Now we are ready to prove the main technical result of this section.
√
Theorem 7. P-Matrix Approximation is solvable in 2O((p+q) k log(p+k)+p log p+q log q+q log(q+k)) ·
(nm)O(1) time.
Proof. Let (A, P, k) be an instance of P-Matrix Approximation. Denote by a1 , . . . , am and
a1 , . . . , an the rows and columns of A respectively, and let P be a p × q-matrix.
First, we preprocess the instance using Lemma 8. If A has at least p + k + 1 pairwise-distinct
rows or at least q + k + 1 pairwise-distinct columns, we return NO and stop. We do the same if
m < p or n < q. Assume from now that this is not the case, that is, p ≤ m, q ≤ n and A has at
most p + k pairwise-distinct rows and at most q + k distinct columns. Further, we exhaustively
apply the following reduction rule.
Reduction Rule 1. If A contains at least k + p + 1 rows that are pairwise equal, then delete
one of these rows.
To see that the rule is safe, let B be an m × n-matrix such that kA − Bk2F ≤ k. If for
I ⊆ {1, . . . , m} it holds that |I| ≥ p + k + 1 and the rows ai for i ∈ I are the same, then there
is J ⊆ I of size at least p + 1 such that the rows bi of B for i ∈ J are the same. Then B is a
32

P-matrix if and only if the matrix obtained by the deletion of an arbitrary row bi for i ∈ J is
a P-matrix.
For simplicity, we keep the same notations for the matrix obtained from A by the exhaustive
application of the rule, i.e., we assume that A is an m × n-matrix with the columns a1 , . . . , an .
Note that now we have that m ≤ (p + k)2 .
Let B = (b1 , . . . , bn ) be a solution to (A, P, k). We say that a set J ⊆ {1, . . . , n} represents
P with respect to B if a) |J| = q, b) B[{1, . . . , m}, J] is a P-matrix, c) for each j ∈ {1, . . . , n}\J,
bj = bi for some i ∈ J, and d) the value of kA[{1, . . . , m}, J] − B[{1, . . . , m}, J]k2F is minimum
over all J ⊆ {1, . . . , n} satisfying a)–c). Observe that for every solution B, there is J ⊆
{1, . . . , n} that represents P with respect to B.
We say that two sets of indices J, J 0 ⊆ {1, . . . , n} are equivalent with respect to A if the
matrices A[{1, . . . , m}, J] and A[{1, . . . , n}, J 0 ] are isomorphic. Observe that if J, J 0 are equivalent with respect to A, then (A, P, k) has a solution B such that J represents P with respect
to B if and only if the same instance has a solution B0 such that J 0 represents P with respect
to B0 .
Because A has at most q + k pairwise-distinct columns, there are at most (q + k)q sets
of indices J ∈ {1, . . . , n} of size q which are pairwise nonequivalent with respect to A. We
consider such sets and for each J, we check whether there is a solution B for (A, P, k) with J
representing P with respect to B. If we find that there is a solution, we return YES and stop,
and we return NO if there is no solution for every choice of I. From now we assume that J is
given.
We construct the instance (A, P, {X, Y, Z}, k) of Extendable P-Matrix Approximation
with X = ∅, Y = J and Z = {1, . . . , n} \ J. We have that B is a solution to (A, P, {X, Y, Z}, k)
of Extendable P-Matrix Approximation if and only if B is a solution for the instance
(A, P, k) of P-Matrix Approximation with J representing P with respect to B. Therefore,
in order to solve P-Matrix Approximation it suffices to solve Extendable P-Matrix
Approximation.
We construct the recursive branching algorithm for Extendable P-Matrix Approximation called Extend-P-Solution. The algorithm takes as an input matrix A, disjoint sets of
indices X, Y, Z ⊆ {1, . . . , n} such that |X| + |Y | = q, and a nonnegative integer k. Extend-PSolution executes in three steps.
Step 1. If Y = ∅, then do the following.
(i) Check whether A[{1, . . . , m}, X] is a P-matrix using Observation 5. If it’s not, then return
NO and stop.
(ii) If Z = ∅, then return YES and stop.
(iii) Verify whether
X

min{dH (ai , aj ) | j ∈ X} ≤ k,

(3)

i∈Z

return YES if (3) holds, return NO otherwise; then stop.
Step 2. For every h = 0, . . . , k, do the following.
(i) For every i ∈ Z, if ` = min{dH (ai , aj ) | j ∈ X} ≤ h, then set Z = Z \ {i} and k = k − `.
p
(ii) If |Y | + |Z| ≤ k log(p + k), then solve (A[{1, . . . , m}, X ∪ Y ∪ Z], P, {X, Y, Z}, k) using
Lemma 9.

33

(iii) If h ≤ k/(|Y |+|Z|), then for each i ∈ Y and each vector âi ∈ {0, 1}m such that dH (ai , âi ) =
h, let Â be the matrix obtained from A by t replacing column ai by âi , call ExtendP-Solution(Â, X ∪ {i}, Y \ {i}, Z, k − h) and if the algorithm returns YES, then return
YES and stop.
Step 3. Return NO and stop.
We call Extend-P-Solution(A, ∅, J, {1, . . . , n}\J, k) to solve the instance of Extendable
P-Matrix Approximation that was constructed above for the considered set of indices J.
Correctness. To prove correctness, we show first that if the algorithm returns YES, then
(A[{1, . . . , m}, X ∪ Y ∪ Z], P, {X, Y, Z}, k) is a yes-instance of Extendable P-Matrix Approximation.
Suppose that Y = ∅. This case is considered in Step 1. If the algorithms returns YES, then
it does not stop in Step 1 (i). Hence, A[{1, . . . , m}, X] is a P-matrix. If Z = ∅, we have that
B = A[{1, . . . , m}, X] is a solution for the instance (A[{1, . . . , m}, X ∪ Y ∪ Z], P, {X, Y, Z}, k)
of Extendable P-Matrix Approximation and the algorithm correctly returns YES. Let
Z 6= ∅. For every i ∈ X, we set bi = ai , and for each i ∈ Z, we define the vector bi = ah
for h ∈ X, where dH (ai , ah ) = min{dH (ai , aj ) | j ∈ X}. Consider matrix B composed of the
columns bi for i ∈ X ∪ Y ∪ Z. It is easy to verify that B is a solution to (A[{1, . . . , m}, X ∪ Y ∪
Z], P, {X, Y, Z}, k). Hence, if the algorithm returns YES in Step 1 (iii), then (A[{1, . . . , m}, X ∪
Y ∪ Z], P, {X, Y, Z}, k) is a yes-instance of Extendable P-Matrix Approximation.
Let Y 6= ∅. Assume that the algorithm returns YES for some h ∈ {0, . . . , k} in Step 2.
Denote by Z 0 the set obtained from Z in Step 2 (i) and let k 0 be the value of k obtained
in Step 2 (i). Observe that if (A[{1, . . . , m}, X ∪ Y ∪ Z 0 ], P, {X, Y, Z 0 }, k 0 ) is a yes-instance of
Extendable P-Matrix Approximation, then (A[{1, . . . , m}, X ∪Y ∪Z], P, {X, Y, Z}, k) is a
yes-instance as well. Indeed, let B̂ be a solution to (A[{1, . . . , m}, X ∪ Y ∪ Z 0 ], P, {X, Y, Z 0 }, k 0 )
with the columns b̂i for i ∈ X ∪ Y ∪ Z 0 . We define B with the columns bi for i ∈ X ∪ Y ∪ Z
as follows: for i ∈ X ∪ Y ∪ Z 0 , bi = b̂i , and for i ∈ Z \ Z 0 , bi = ah = b̂h for h ∈ X
such that dH (ai , ah ) = min{dH (ai , aj ) | j ∈ X}. It is easy to see that B is a solution for
(A[{1, . . . , m}, X ∪ Y ∪ Z], P, {X, Y, Z}, k).
Suppose that the algorithm returns YES in Step 2 (ii). Then (A[{1, . . . , m}, X ∪ Y ∪
0
Z ], P, {X, Y, Z 0 }, k 0 ), and therefore (A[{1, . . . , m}, X ∪Y ∪Z], P, {X, Y, Z}, k), are yes-instances
of Extendable P-Matrix Approximation.
Suppose that the algorithm returns YES in Step 2 (iii) for i ∈ Y . Then (Â[{1, . . . , m}, X ∪
Y ∪ Z], P, {X ∪ {i}, Y \ {i}, Z 0 }, k 0 ) is a yes-instance of Extendable P-Matrix Approximation. Since dH (ai , âi ) = h, we have that every solution to (Â[{1, . . . , m}, X ∪ Y ∪ Z], P, {X ∪
{i}, Y \ {i}, Z 0 }, k 0 ) is also a solution to (A[{1, . . . , m}, X ∪ Y ∪ Z], P, {X, Y, Z 0 }, k 0 ). This implies that (A[{1, . . . , m}, X ∪ Y ∪ Z 0 ], P, {X, Y, Z 0 }, k 0 ) and, therefore, (A[{1, . . . , m}, X ∪ Y ∪
Z], P, {X, Y, Z}, k) is a yes-instance of Extendable P-Matrix Approximation.
We proved that if the algorithm returns the answer YES, then (A[{1, . . . , m}, X ∪ Y ∪
Z], P, {X, Y, Z}, k) is a yes-instance of Extendable P-Matrix Approximation. Recall that
we call Extend-P-Solution(A, ∅, J, {1, . . . , n} \ J, k) to solve the instance of Extendable
P-Matrix Approximation constructed for the considered set of indices J ⊆ {1, . . . , n} of size
q from the instance (A, P, k) of P-Matrix Approximation. It follows that if Extend-PSolution(A, ∅, J, {1, . . . , n} \ J, k) outputs YES, then (A, P, k) is a yes-instance of P-Matrix
Approximation.
Let us note that Extend-P-Solution(A, X, Y, Z, k) can return NO even if
(A[{1, . . . , m}, X ∪ Y ∪ Z], P, {X, Y, Z}, k) is a yes-instance of Extendable P-Matrix Approximation. This can occur when X, Y and Z are arbitrary disjoint subsets of {1, . . . , n} such
that |X| + |Y | = q. Nevertheless, because we call call Extend-P-Solution(A, ∅, J, {1, . . . , n} \
J, k), we are able to show the following claim.
34

Claim 6.1. If (A, P, k) is a yes-instance of P-Matrix Approximation and a set J ⊆
{1, . . . , n} of size q is selected such that (A, P, k) has a solution B and J represents P with
respect to B, then Extend-P-Solution(A, ∅, J, {1, . . . , n} \ J, k) returns YES.
Proof of Claim 6.1. By
making
use
of
induction
on
|Y |,
we
show
that
Extend-P-Solution(Â, X, Y, Z, k 0 ) returns YES if (Â[{1, . . . , m}, X ∪Y ∪Z], P, {X, Y, Z}, k 0 )
is a yes-instance of Extendable P-Matrix Approximation, where
• X ∪ Y = J,
• Â is the matrix with the columns âi for i ∈ X ∪ Y ∪ Z, where âi = bi for i ∈ X and
âi = ai for i ∈ Y ∪ Z, and
P
• k 0 ≥ k − i∈X∪({1,...,n}\(X∪Y ∪Z)) dH (ai , bi ).
Note that for X = ∅, this would imply the claim.
The base of the induction is the case |Y | = 0, i.e., Y = ∅. This case is considered in
Step 1 of Extend-P-Solution. Since Â[{1, . . . , m}, X] = B[{1, . . . , m}, X], we have that
B[{1, . . . , m}, X] is a P-matrix. In particular, the algorithm does not stop in Step 1 (i). If
Z = ∅, then the algorithm returns YES. Let Z 6= ∅. Notice that because Â[{1, . . . , m}, X] =
B[{1, . . . , m}, X] and J represents P with respect to B, we have that
X
X
min{dH (ai , aj ) | j ∈ X} ≤
dH (ai , bi ) ≤ k 0 .
i∈Z

i∈Z

Hence, the algorithm returns YES in Step 2 (iii).
Assume that |Y | > 0 and we proved our statement for smaller sets Y . Let h∗ = min{dH (ai , bi ) |
∗
∗
i ∈ Y }. Let also i∗ ∈ Y be such that h∗ = dH (ai , bi ). We claim that Extend-P-Solution
returns YES in Step 3 for h = h∗ unless it does not return YES before.
Denote by Z ∗ the set obtained from Z in Step 2 (i) and let k ∗ the value of k obtained in the
same step for h = h∗ .
Recall that J represents P with respect to B. By the condition d) of the definition, we have
that the value of kA[{1, . . . , m}, J] − B[{1, . . . , m}, J]k2F is minimum over all J ⊆ {1, . . . , n}
satisfying a)–c). In particular, it implies that for each i ∈ Z, either bi = bj for some j ∈ X or
dH (ai , bi ) ≥ h∗ . It follows that (Â[{1, . . . , m}, X ∪ Y ∪ Z ∗ ],P
P, {X, Y, Z}, k ∗ ) is a yes-instance of
∗
Extendable P-Matrix Approximation and k ≥ k − i∈X∪({1,...,n}\(X∪Y ∪Z ∗ )) dH (ai , bi ).
p
If |Y | + |Z ∗ | ≤ k ∗ log(p + k ∗ ), we solve Extendable P-Matrix Approximation for
(A[{1, . . . , m}, X ∪ Y ∪ Z ∗ ], P, {X, Y, Z ∗ }, k ∗ ) directly using Lemma 9. Hence, the algorithm
returns YES.
p
Assume that |Y | + |Z ∗ | > k ∗ log(p + k ∗ ). Notice that for each i ∈ Z ∗ , we have that
dH (ai , bi ) ≥ h∗ . Hence,
X
k∗ ≥
dH (ai , bi ) ≥ h∗ · (|Y | + |Z|)
i∈Y ∪Z

p
and h∗ ≤ k ∗ /(|Y | + |Z|) ≤ k ∗ / log(p + k ∗ ). In Step 2 (iii), we consider every i ∈ Y and each
∗
∗
vector âi ∈ {0, 1}m such that dH (ai , âi ) = h∗ . In particular, we consider i = i∗ and âi = bi .
Then (Â[{1, . . . , m}, X ∪ Y ∪ Z ∗ ], P, {X ∪ {i∗ }, Y \ {i∗ }, Z ∗ }, k ∗ − h∗ ) for the matrix Â∗ obtained
∗
∗
∗
from Â by the replacing column âi = ai by bi is a yes-instance of Extendable P-Matrix
Approximation. By the inductive assumption, we have that the algorithms returns YES for
this branch. Recall that whenever the algorithm in Step 2 (iii) obtains YES for some branch,
it returns YES and stops. Since we have such an answer for at least one branch, the algorithm
returns YES. This concludes the proof of Claim.
35

Summarizing, we obtain that (A, P, k) is a yes-instance of P-Matrix Approximation
if and only if Extend-P-Solution(A, ∅, J, {1, . . . , n} \ J, k) returns YES for some choice of
J ⊆ {1, . . . , n} of size q. This competes the correctness proof.
Running time. Now we evaluate the running time. The preprocessing is done in polynomial time. Then we consider all pairwise nonequivalent with respect to A sets of indices
J ∈ {1, . . . , n} of size q. There are at most (q + k)q such sets. Then for each J, we run
Extend-P-Solution(A, ∅, J, {1, . . . , n} \ J, k). By Observation 5, Step 1 (i) can be done in
time 2O(p log p+q log q) · (nm)O(1) . Parts (ii) and (iii) of Step 1 are performed in polynomial time.
In Step 2, we consider k + 1 values of h and for each h perform
Step 2 (i)–(iii). Step 2 (i) takes
√
O(p( k log(p+k)+log k)+p log p+q log q)
polynomial time. Step 2 (ii) can be done in time 2
· (nm)O(1)
by Lemma 9. In Step 2 (iii), we consider at most |Yp
| ≤ q values of i, and for each i construct
i
m
i
i
all vectors â ∈ {0, 1} such that dH (a , â ) = h ≤ k/ log(p + k). Recall
√ that after the pre-

processing, we have that m ≤ (p + k)2 . √
Hence, we have at most (p + k)2 k/ log(p+k) vectors âi .
It means that in Step 2 (iii) we have 2O( k log(p+k)) branches. On each recursive call, we reduce
the size of Y . It means that the depth of the recursion is at most q. Then the total running
time is
√
√
2O(p k log(p+k)+q log k log(p+k)+p log p+q log q+q log(q+k)) · (nm)O(1) .

Note that the running time in Theorem 7 is asymmetric in p and q due to the fact that we
treat rows and columns in different way but, trivially, the instances (A, P, k) and (A| , P| , k)
of P-Matrix Approximation are equivalent. If p√ and q are assumed to be constants, then
P-Matrix Approximation is solvable in time 2O( k log k) · (nm)O(1) .
Notice that we can invoke Theorem 7 to solve Low GF(2)-Rank Approximation as
follows. We use Observation 2 and observe that (A, r, k) is a yes-instance of Low GF(2)Rank Approximation if and only if there is a 2r × 2r -matrix P of GF(2)-rank at most r such
that (A, P, k) is a yes-instance of P-Matrix Approximation. Matrix P is of GF(2)-rank r if
and only if it can be represented as a product P = U · V, where U is 2r × r and V is r × 2r
r
binary matrix and arithmetic operations are over GF(2). There are at most 2r2 different binary
r
2r × r-matrices U, and at most 2r2 different binary r × 2r -matrices V. Thus there are at
r
most 22r2 candidate matrices P. For each such matrix P, we check whether (A, P, k) is a yesinstance of P-Matrix Approximation by invoking Theorem 7. However this approach gives
a double exponential dependence in r, which is much worse the bound provided by Theorem 6.
Still, this approach is useful if we consider the variant of Low GF(2)-Rank Approximation
for Boolean matrices.
Let us remind that binary matrix A has the Boolean rank 1 if A = x ∧ y| where x ∈ {0, 1}m
and y ∈ {0, 1}n are nonzero vectors and the product is Boolean and that the Boolean rank of
A is the minimum integer r such that A = A(1) ∨ · · · ∨ A(r) where A(1) , . . . , A(r) are matrices
of Boolean rank 1 and the sum is Boolean.
r

Theorem 8. Low Boolean-Rank Approximation is solvable in 2O(r2
time.

√

k log k)

· (nm)O(1)

Proof. Let A be a Boolean m×n-matrix with the Boolean rank r ≥ 1. Then A = A(1) ∨. . .∨A(r)
where A(1) , . . . , A(r) are matrices of Boolean rank 1. It implies that A has at most 2r pairwisedistinct rows and at most 2r pairwise-distinct columns. Hence, the Boolean rank of A is at
most r if and only if there is a 2r × 2r -matrix P of Boolean rank at most r such that A is a Pmatrix. Respectively, the Low Boolean-Rank Approximation problem can be reformulated
as follows: Decide whether there is a 2r × 2r -pattern matrix P with the Boolean rank at most
r and an m × n P-matrix B such that kA − Bk2F ≤ k.
36

We generate all 2r × 2r -matrices P of Boolean rank at most r, and then for each matrix P,
we solve P-Matrix Approximation for the instance (A, P, k). We return YES if we obtain
at least one yes-instance of P-Matrix Approximation, and we return NO otherwise.
By definition, the Boolean rank of P is r if and only if P = U∧V for a Boolean 2r ×r matrix
r
U and a Boolean r×2r matrix V Since there are at most 2r2 2r ×r-matrices, we construct all the
r
2r ×2r -matrices P with the Boolean rank at most r in time 2O(r2 ) . By
√ Theorem 7, the considered
r k log k)
O(r2
instances of P-Matrix Approximation is solvable in time 2
· (nm)O(1) .
In the conclusion of the section we observe that we hardly can avoid the double exponential
dependence on r for Low Boolean-Rank Approximation. Chandran, Issac and Karrenbauer
proved in [13] that the Biclique Cover problem that asks, given a bipartite graph G, whether
the set of edges of G could be covered by at most r bicliques (that is, complete bipartite graphs)
o(r)
cannot be solved in time 22
· |V (G)|O(1) unless the Exponential Time Hypothesis (ETH) is
false (we refer to [18] for the introduction to the algorithmic lower bounds based on ETH). Since
Biclique Cover is equivalent to deciding whether the bipartite adjacency matrix of G has
the Boolean rank at most r, Low Boolean-Rank Approximation cannot be solved in time
o(r)
22
· (nm)O(1) for k = 0 unless ETH fails.

7

Conclusion and open problems

In this paper we provide a number of parameterized algorithms for a number of binary matrixapproximation problems. Our results uncover some parts of the complexity landscape of these
fascinating problems. We hope that our work will facilitate further investigation of this important and exciting area. We conclude with the following concrete open problems about bivariate
complexity of Binary r-Means, Low GF(2)-Rank Approximation, and Low BooleanRank Approximation.
For Binary r-Means we have shown that the problem is solvable in time 2O(k log k) ·(nm)O(1) .
A natural question is whether this running time is optimal. While the lower bound of the kind
2o(k) · (nm)O(1) or 2o(k log k) · (nm)O(1) seems to be most plausible here, we do not know any
strong argument against, say a 2o(k) · (nm)O(1) -time algorithm. At least for the number of
distinct columns r ∈ O(k 1/2−ε ) with ε > 0, we have a subexponential in k algorithm, so maybe
we can solve the problem in time subexponential in k for any value of r?
For Low√ GF(2)-Rank Approximation we have an algorithm solving the problem in
√
3/2
time 2O(r · k log k) (nm)O(1) . Here, shaving off the log k factor in the exponent seems to be
a reasonable thing. However, we do not know how to do it even by the cost
√ of the worse
O(f
(r)·
k) (nm)O(1) for
dependence in r. In other words, could the problem be solvable in time 2
some function f ? On the other hand, we also do not know how to rule out algorithms running
in time 2o(r)·o(k)) (nm)O(1) .
√
r
For Low Boolean-Rank Approximation, how far is our upper bound 2O(r2 · k log k) (nm)O(1)
from the optimal? For example, we know that for any function f , the solvability
√ of the problem
o(r)
2
O(1)
o(
in time 2
f (k)(nm)
implies the failure of ETH. Could we rule out 2 k) f (r)(nm)O(1)
algorithm?
From kernelization perspective, we proved that Binary r-Means admits a polynomial kernel
when parameterized by k + r. On the other hand, due to its connection to Biclique Cover,
we know that already for k = 0, Low Boolean-Rank Approximation does not admit a
subexponential kernel when parameterized by r [13]. This rules out the existence of a polynomial
in r + k kernel for Low Boolean-Rank Approximation. However, for Low GF(2)-Rank
Approximation the existence of a polynomial in r + k kernel is open.

37

Acknowledgments. We thank Daniel Lokshtanov, Syed Mohammad Meesum and Saket
Saurabh for helpful discussions on the topic of the paper.

References
[1] P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan, Approximating extent measures of points, J. ACM, 51 (2004), pp. 606–635. 3, 5
[2] A. V. Aho, J. D. Ullman, and M. Yannakakis, On notions of information transfer in VLSI circuits, in Proceedings of the 15th Annual ACM Symposium on Theory of
Computing (STOC), ACM, 1983, pp. 133–139. 4
[3] N. Alon and B. Sudakov, On two segmentation problems, J. Algorithms, 33 (1999),
pp. 173–184. 3, 5
[4] N. Alon, R. Yuster, and U. Zwick, Color-coding, J. ACM, 42 (1995), pp. 844–856. 7,
12, 15, 17
[5] S. Arora, R. Ge, R. Kannan, and A. Moitra, Computing a nonnegative matrix
factorization - provably, in Proceedings of the 44th Annual ACM Symposium on Theory
of Computing (STOC), ACM, 2012, pp. 145–162. 6
[6] M. Badoiu, S. Har-Peled, and P. Indyk, Approximate clustering via core-sets, in
Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), ACM,
2002, pp. 250–257. 3, 5
[7] E. Bartl, R. Belohlávek, and J. Konecny, Optimal decompositions of matrices with
grades into binary and graded matrices, Annals of Mathematics and Artificial Intelligence,
59 (2010), pp. 151–167. 4
[8] A. Basu, M. Dinitz, and X. Li, Computing approximate PSD factorizations, CoRR,
abs/1602.07351 (2016). 6
[9] R. Belohlávek and V. Vychodil, Discovery of optimal factors in binary data via a
novel method of matrix decomposition, J. Computer and System Sciences, 76 (2010), pp. 3–
20. 4
[10] H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin, On problems
without polynomial kernels, J. Computer and System Sciences, 75 (2009), pp. 423–434. 21,
22
[11] C. Boucher, C. Lo, and D. Lokshtanov, Outlier detection for DNA fragment assembly,
CoRR, abs/1111.0376 (2011). 21
[12] K. Bringmann, P. Kolev, and D. P. Woodruff, Approximation algorithms for `0 low rank approximation, in Advances in Neural Information Processing Systems 30 (NIPS),
2017, pp. 6651–6662. 5, 6
[13] L. S. Chandran, D. Issac, and A. Karrenbauer, On the parameterized complexity of biclique cover and partition, in Proceedings of the 11th International Symposium
on Parameterized and Exact Computation (IPEC), vol. 63 of LIPIcs, Schloss Dagstuhl Leibniz-Zentrum fuer Informatik, 2016, pp. 11:1–11:13. 6, 7, 37

38

[14] A. Cichocki, R. Zdunek, A. H. Phan, and S.-i. Amari, Nonnegative matrix and
tensor factorizations: applications to exploratory multi-way data analysis and blind source
separation, John Wiley & Sons, 2009. 4
[15] R. Cilibrasi, L. van Iersel, S. Kelk, and J. Tromp, The complexity of the single
individual SNP haplotyping problem, Algorithmica, 49 (2007), pp. 13–36. 3
[16] K. L. Clarkson and D. P. Woodruff, Input sparsity and hardness for robust subspace
approximation, in Proceedings of the 56th Annual Symposium on Foundations of Computer
Science (FOCS), IEEE Computer Society, 2015, pp. 310–329. 6
[17] J. E. Cohen and U. G. Rothblum, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra and its Applications, 190 (1993), pp. 149–168.
4, 6
[18] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk,
M. Pilipczuk, and S. Saurabh, Parameterized Algorithms, Springer, 2015. 7, 15, 17,
21, 37
[19] C. Dan, K. A. Hansen, H. Jiang, L. Wang, and Y. Zhou, On low rank approximation
of binary matrices, CoRR, abs/1511.01699 (2015). 3, 4, 5, 6, 7
[20] R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity, Texts
in Computer Science, Springer, 2013. 7
[21] P. G. Drange, F. Reidl, F. S. Villaamil, and S. Sikdar, Fast biclustering by dual
parameterization, CoRR, abs/1507.08158 (2015). 6
[22] U. Feige, NP-hardness of hypercube 2-segmentation, CoRR, abs/1411.0821 (2014). 5, 7
[23] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf, Exponential
lower bounds for polytopes in combinatorial optimization, J. ACM, 62 (2015), p. 17. 4
[24] F. V. Fomin, S. Kratsch, M. Pilipczuk, M. Pilipczuk, and Y. Villanger, Tight
bounds for parameterized complexity of cluster editing with a small number of clusters, J.
Computer and System Sciences, 80 (2014), pp. 1430–1447. 6
[25] F. V. Fomin, D. Lokshtanov, S. M. Meesum, S. Saurabh, and M. Zehavi, Matrix
rigidity from the viewpoint of parameterized complexity, in Proceedings of the 34th International Symposium on Theoretical Aspects of Computer Science (STACS), vol. 66 of Leibniz
International Proceedings in Informatics (LIPIcs), 2017, pp. 32:1–32:14. 5, 6, 7, 8, 10
[26] Y. Fu, Low-Rank and Sparse Modeling for Visual Analysis, Springer International Publishing, 1 ed., 2014. 4
[27] F. Geerts, B. Goethals, and T. Mielikäinen, Tiling databases, in , Proceedings of
the 7th International Conference on Discovery Science, (DS), 2004, pp. 278–289. 5
[28] N. Gillis and S. A. Vavasis, On the complexity of robust PCA and `1 -norm low-rank
matrix approximation, CoRR, abs/1509.09236 (2015). 5, 6, 7
[29] J. Gramm, J. Guo, F. Hüffner, and R. Niedermeier, Data reduction and exact
algorithms for clique cover, ACM Journal of Experimental Algorithmics, 13 (2008). 6
[30] D. A. Gregory, N. J. Pullman, K. F. Jones, and J. R. Lundgren, Biclique coverings
of regular bigraphs and minimum semiring ranks of regular matrices, J. Combinatorial
Theory Ser. B, 51 (1991), pp. 73–89. 6
39

[31] D. Grigoriev, Using the notions of separability and independence for proving the lower
bounds on the circuit complexity (in russian), Notes of the Leningrad branch of the Steklov
Mathematical Institute, Nauka, (1976). 3
[32]

, Using the notions of separability and independence for proving the lower bounds on
the circuit complexity, Journal of Soviet Math., 14 (1980), pp. 1450–1456. 3

[33] H. W. Gutch, P. Gruber, A. Yeredor, and F. J. Theis, ICA over finite fields separability and algorithms, Signal Processing, 92 (2012), pp. 1796–1808. 3
[34] A. E. Guterman, Rank and determinant functions for matrices over semirings, in Surveys
in contemporary mathematics, vol. 347 of London Math. Soc. Lecture Note Ser., Cambridge
Univ. Press, Cambridge, 2008, pp. 1–33. 4
[35] M. Inaba, N. Katoh, and H. Imai, Applications of weighted voronoi diagrams and
randomization to variance-based k-clustering, in Proceedings of the 10th annual symposium
on Computational Geometry, ACM, 1994, pp. 332–339. 5
[36] P. Jiang and M. T. Heath, Mining discrete patterns via binary matrix factorization, in
ICDM Workshops, IEEE Computer Society, 2013, pp. 1129–1136. 5
[37] P. Jiang, J. Peng, M. Heath, and R. Yang, A Clustering Approach to Constrained
Binary Matrix Factorization, Springer Berlin Heidelberg, Berlin, Heidelberg, 2014, pp. 281–
303. 3, 5
[38] R. Kannan and S. Vempala, Spectral algorithms, Foundations and Trends in Theoretical
Computer Science, 4 (2009), pp. 157–288. 5
[39] J. Kleinberg, C. Papadimitriou, and P. Raghavan, Segmentation problems, J. ACM,
51 (2004), pp. 263–280. 3
[40] M. Koyutürk and A. Grama, Proximus: A framework for analyzing very high dimensional discrete-attributed datasets, in Proceedings of the 9th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining (KDD), New York, NY, USA, 2003,
ACM, pp. 147–156. 3, 5
[41] A. Kumar, Y. Sabharwal, and S. Sen, Linear-time approximation schemes for clustering problems in any dimensions, J. ACM, 57 (2010), pp. 5:1–5:32. 3, 5
[42] D. D. Lee and H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature, 401 (1999), pp. 788–791. 3
[43] S. V. Lokam, Complexity lower bounds using linear algebra, Found. Trends Theor. Comput. Sci., 4 (2009), pp. 1–155. 3
[44] L. Lovász and M. E. Saks, Lattices, möbius functions and communication complexity, in
Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS),
IEEE, 1988, pp. 81–90. 4
[45] H. Lu, J. Vaidya, and V. Atluri, Optimal boolean matrix decomposition: Application to
role engineering, in Proceedings of the 24th International Conference on Data Engineering,
(ICDE), 2008, pp. 297–306. 6
[46] H. Lu, J. Vaidya, V. Atluri, and Y. Hong, Constraint-aware role mining via extended
boolean matrix decomposition, IEEE Trans. Dependable Sec. Comput., 9 (2012), pp. 655–
669. 4
40

[47] M. W. Mahoney, Randomized algorithms for matrices and data, Foundations and Trends
in Machine Learning, 3 (2011), pp. 123–224. 5
[48] D. Marx, Closest substring problems with small distances, SIAM J. Comput., 38 (2008),
pp. 1382–1410. 7, 12, 13, 15
[49] S. M. Meesum, P. Misra, and S. Saurabh, Reducing rank of the adjacency matrix by
graph modification, Theoret. Comput. Sci., 654 (2016), pp. 70–79. 6
[50] S. M. Meesum and S. Saurabh, Rank reduction of directed graphs by vertex and edge
deletions, in Proceedings of the 12th Latin American Symposium on (LATIN), vol. 9644 of
Lecture Notes in Comput. Sci., Springer, 2016, pp. 619–633. 6
[51] P. Miettinen, T. Mielikäinen, A. Gionis, G. Das, and H. Mannila, The discrete
basis problem, IEEE Trans. Knowl. Data Eng., 20 (2008), pp. 1348–1362. 3, 4
[52] P. Miettinen and J. Vreeken, Model order selection for boolean matrix factorization, in
Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining (KDD), ACM, 2011, pp. 51–59. 4
[53] B. Mitra, S. Sural, J. Vaidya, and V. Atluri, A survey of role mining, ACM Comput.
Surv., 48 (2016), pp. 50:1–50:37. 4
[54] A. Moitra, An almost optimal algorithm for computing nonnegative rank, SIAM J. Comput., 45 (2016), pp. 156–173. 6
[55] G. R. Naik, Non-negative Matrix Factorization Techniques, Springer, 2016. 4
[56] M. Naor, L. J. Schulman, and A. Srinivasan, Splitters and near-optimal derandomization, in Proceedings of the 36th Annual Symposium on Foundations of Computer Science
(FOCS), IEEE, 1995, pp. 182–191. 17
[57] J. Orlin, Contentment in graph theory: covering graphs with cliques, Nederl. Akad. Wetensch. Proc. Ser. A 80=Indag. Math., 39 (1977), pp. 406–424. 6, 7
[58] R. Ostrovsky and Y. Rabani, Polynomial-time approximation schemes for geometric
min-sum median clustering, J. ACM, 49 (2002), pp. 139–156. 3, 5
[59] A. Painsky, S. Rosset, and M. Feder, Generalized independent component analysis
over finite alphabets, IEEE Trans. Information Theory, 62 (2016), pp. 1038–1053. 3
[60] A. A. Razborov, On rigid matrices, Manuscript in russian, (1989). 3
[61] I. P. Razenshteyn, Z. Song, and D. P. Woodruff, Weighted low rank approximations
with provable guarantees, in Proceedings of the 48th Annual ACM Symposium on Theory
of Computing (STOC), ACM, 2016, pp. 250–263. 6
[62] B.-H. Shen, S. Ji, and J. Ye, Mining discrete patterns via binary matrix factorization, in
Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining (KDD), New York, NY, USA, 2009, ACM, pp. 757–766. 3, 5
[63] J. Vaidya, Boolean matrix decomposition problem: Theory, variations and applications
to data engineering, in Proceedings of the 28th IEEE International Conference on Data
Engineering (ICDE), IEEE Computer Society, 2012, pp. 1222–1224. 4

41

[64] J. Vaidya, V. Atluri, and Q. Guo, The role mining problem: finding a minimal descriptive set of roles, in Proceedings of the 12th ACM Symposium on Access Control Models
and (SACMAT), 2007, pp. 175–184. 4
[65] L. G. Valiant, Graph-theoretic arguments in low-level complexity, in Mathematical Foundations of Computer Science (MFCS), vol. 53 of Lecture Notes in Comput. Sci., Springer,
1977, pp. 162–176. 3
[66] D. P. Woodruff, Sketching as a tool for numerical linear algebra, Foundations and Trends
in Theoretical Computer Science, 10 (2014), pp. 1–157. 5
[67] S. Wulff, R. Urner, and S. Ben-David, Monochromatic bi-clustering, in Proceedings of the 30th International Conference on Machine Learning, (ICML), vol. 28 of JMLR
Workshop and Conference Proceedings, JMLR.org, 2013, pp. 145–153. 5
[68] M. Yannakakis, Expressing combinatorial optimization problems by linear programs, J.
Comput. Syst. Sci., 43 (1991), pp. 441–466. 4
[69] A. Yeredor, Independent component analysis over Galois fields of prime order, IEEE
Trans. Information Theory, 57 (2011), pp. 5342–5359. 3

42

