Perfect phylogenies via branchings in acyclic digraphs
and a generalization of Dilworth’s theorem
Ademir Hujdurovića,b∗

Edin Husićc,b†

Martin Milaniča,b‡

Romeo Rizzid§

arXiv:1701.05492v3 [cs.DM] 27 Jan 2018

Alexandru I. Tomescue¶
January 30, 2018
a

University of Primorska, UP IAM, Koper, Slovenia
University of Primorska, UP FAMNIT, Koper, Slovenia
c London School of Economics, Department of Mathematics, London, United Kingdom
d University of Verona, Department of Computer Science, Verona, Italy
e Helsinki Institute for Information Technology HIIT, Department of Computer Science,
University of Helsinki, Finland
b

Abstract
Motivated by applications in cancer genomics and following the work of Hajirasouliha and
Raphael (WABI 2014), Hujdurović et al. (IEEE TCBB, to appear) introduced the minimum
conflict-free row split (MCRS) problem: split each row of a given binary matrix into a bitwise
OR of a set of rows so that the resulting matrix corresponds to a perfect phylogeny and has
the minimum possible number of rows among all matrices with this property. Hajirasouliha
and Raphael also proposed the study of a similar problem, in which the task is to minimize the
number of distinct rows of the resulting matrix. Hujdurović et al. proved that both problems
are NP-hard, gave a related characterization of transitively orientable graphs, and proposed a
polynomial-time heuristic algorithm for the MCRS problem based on coloring cocomparability
graphs.
We give new, more transparent formulations of the two problems, showing that the problems
are equivalent to two optimization problems on branchings in a derived directed acyclic graph.
Building on these formulations, we obtain new results on the two problems, including: (i) a
strengthening of the heuristic by Hujdurović et al. via a new min-max result in digraphs generalizing Dilworth’s theorem, which may be of independent interest, (ii) APX-hardness results
for both problems, (iii) approximation algorithms, and (iv) exponential-time algorithms solving
the two problems to optimality faster than the naı̈ve brute-force approach. Our work relates to
several well studied notions in combinatorial optimization: chain partitions in partially ordered
sets, laminar hypergraphs, and (classical and weighted) colorings of graphs.

Keywords: Perfect phylogeny, Minimum Conflict-Free Row Split problem, branching, acyclic
digraph, chain partition, Dilworth’s theorem, min-max theorem, approximation algorithm, APXhardness
∗

E-mail:
E-mail:
‡
E-mail:
§
E-mail:
¶
E-mail:
†

ademir.hujdurovic@upr.si
e.husic@lse.ac.uk
martin.milanic@upr.si
romeo.rizzi@univr.it
tomescu@cs.helsinki.fi

1

1

Introduction

A perfect phylogeny is a rooted tree representing the evolutionary history of a set of m objects. The
objects bijectively label the leaves of the tree and there are n binary variables called characters,
each labeling exactly one edge of the tree. For each leaf, the set of characters that appear on
the unique root-to-leaf path is the set of characters taking value 1 at the object labeling the leaf.
While every perfect phylogeny naturally corresponds to an m × n binary matrix having objects as
rows and characters as columns, the perfect phylogeny problem asks the opposite question: Does
a given binary matrix correspond to a perfect phylogeny? The perfect phylogeny problem and
various generalizations of it have been extensively studied in computational biology. In this paper
we study two combinatorial optimization problems, both generalizations of the perfect phylogeny
problem, first considered by Hajirasouliha and Raphael [18] and motivated by applications in cancer
genomics.
Following the work [18], Hujdurović et al. [20] introduced the minimum conflict-free row split
problem, which can be informally stated as follows: given a binary matrix M , split each row of M
into a bitwise OR1 of a set of rows so that the resulting matrix corresponds to a perfect phylogeny
and has the minimum number of rows among all matrices with this property. To state the problem
formally, we need two definitions.
Definition 1.1. Given a matrix M , three distinct rows r, r0 , r00 of M and two distinct columns i
and j of M , we denote by M [(r, r0 , r00 ), (i, j)] the 3 × 2 submatrix of M formed by rows r, r0 , r00 and
columns i, j (in this order). Two columns i and j of a binary matrix M are said to be in conflict
if there exist rows r, r0 , r00 of M such that


1 1
M [(r, r0 , r00 ), (i, j)] =  1 0  .
0 1
We say that a binary matrix M is conflict-free if no two columns of M are in conflict.
Definition 1.2. Let M ∈ {0, 1}m×n . Label the rows of M as r1 , r2 , . . . , rm . A binary matrix
0
M 0 ∈ {0, 1}m ×n is a row split of M if there exists a partition of the set of rows of M 0 into m sets
R1 , R2 , . . . Rm such that for all i ∈ {1, . . . , m}, ri is the bitwise OR of the binary vectors in Ri .
The set Ri of rows of M 0 is said to be the set of split rows of row ri (with respect to M 0 ).
For simplicity, we defined a row split as a binary matrix M 0 for which a suitable partition of rows
exists. However, throughout the paper we will make a slight technical abuse of this terminology
by considering any row split M 0 of M as already equipped with an arbitrary (but fixed) partition
of its rows R1 , . . . , Rm satisfying the above condition. For an example of these notions, see Fig. 1.
For the sake of clarity, from now on we omit displaying the zeros in binary matrices.
We denote by γ(M ) the minimum number of rows in a conflict-free row split M 0 of M . Formally,
the minimum conflict-free row split problem is defined as follows:
MinimumConflict-FreeRowSplit (MCRS):
Input:
Task:

A binary matrix M .
Compute γ(M ).

1

Here, OR denotes the usual binary OR function, assuming that value true is represented by 1 and value false by
0, that is, x OR y = 1 if and only if at least one of x and y has value 1.

2

M0
M

c1 c2 c3 c4 c5 c6



1
r1
r2 

r3 
r4


1 1 1

1 1

1
1 1 
1

1
1

c1 c2 c3 c4 c5 c6


 1
R1 



R2  



R3 



R4

1
1
1
1

1
1

1
1

1
1


1
1 





1 




1

Figure 1: An example of a binary matrix M and a conflict-free row split M 0 of M .
We will also consider a variant of the problem, proposed by Hajirasouliha and Raphael [18], in
which the task is to compute a row split M 0 of M such that the number of distinct rows in M 0 is
minimized. Let η(M ) denote the minimum number of distinct rows in a conflict-free row split M 0
of M . Similarly as above, we consider the corresponding optimization problem.
MinimumDistinctConflict-FreeRowSplit (MDCRS):
Input:
Task:

A binary matrix M .
Compute η(M ).

The connection between conflict-free matrices and perfect phylogenies is well known: the rows of
a binary matrix M are the leaves of a perfect phylogeny if and only if M is conflict-free (see [9,17]).
Moreover, if this is the case, then the corresponding tree can be retrieved from M in time linear
in the size of M [16]. The intuition behind the fact that a conflict-free matrix corresponds to a
perfect phylogeny is that one can map each row to a leaf of a tree, and each column to an edge,
so that each row has a 1 exactly on those columns that are mapped to the edges on the path from
the root to the leaf corresponding to the row. The forbidden 3 × 2 matrix from Definition 1.1 as
a submatrix leads a contradiction, since then the two distinct edges ei and ej to which columns i
and j are mapped, respectively, are such that ei appears both before, and after, ej on a root-to-leaf
path. We refer to [18, 20] and to references therein for further details on the biological aspects of
the MCRS and the MDCRS problems.
Another well studied family of combinatorial objects closely related to the MCRS and the
MDCRS problems are laminar set families. A set family F is said to be laminar if every two sets
A, B ∈ F satisfy A ∩ B = ∅, A ⊆ B, or B ⊆ A. The connection with laminar families follows
from the fact that a binary matrix M is conflict-free if and only if the sets of rows indicating the
positions of ones in the columns of M form a laminar family. This connection will be exploited in
Section 4.2. Laminar families of sets play an important role in network design problems [22], in
the study of packing and covering problems [5, 13, 27], and in several other areas of combinatorial
optimization, see, e.g., [28].
In [20], the MCRS and the MDCRS problems were proved NP-hard, a related characterization
of transitively orientable graphs was given, and a polynomial-time heuristic algorithm was proposed for the MCRS problem based on coloring cocomparability graphs (that is, complements of
3

transitively orientable graphs). Following [20], the main aim of this paper is to further advance the
understanding of structural and computational aspects of the MCRS and the MDCRS problems.
Our results and techniques. The first and main result of this paper is a result showing that the
MCRS and the MDCRS problems can be equivalently formulated as two optimization problems
on branchings in a directed acyclic graph derived from the given binary matrix, the so-called
containment digraph. (Precise definitions of these notions and the corresponding problems will
be given in Section 2.) These equivalencies lead to more transparent formulations of the two
problems. We will ascertain the applicability and usefulness of these novel formulations by deriving
the following results and insights about the MCRS and the MDCRS problems:
• We prove a new min-max result on digraphs strengthening Dilworth’s theorem on chain
partitions and antichains in partially ordered sets. This result is described in Section 3.1,
which can be read independently of the rest of the paper. This result, besides being interesting
on its own as a generalization of a classical min-max result, connects well to the MCRS
problem via the problem’s branching formulation. The constructive, algorithmic proof of
the result shows that a related problem is polynomially solvable: a problem in which only
a subset of all branchings of the containment digraph is examined, namely the so-called
linear branchings (branchings corresponding to chain partitions of the partial order underlying
the containment digraph). This approach leads to a new heuristic for the MCRS problem,
improving on a previous heuristic from [20].
• We strengthen the NP-hardness results for the two problems to APX-hardness results.
• We complement the inapproximability results with three approximation algorithms:
a 2-approximation algorithm for the MDCRS problem (implying that the problem is APXcomplete) and two approximation algorithms for the MCRS problem, the approximation ratios
of which are expressed in terms of two parameters of the containment digraph, corresponding
to the height and the width of the underlying partial order, respectively.
• The branching formulations allow for the development of faster exact exponential-time solutions for the two problems, when compared to a direct brute-force approach that follows
directly from the problems’ definitions.
Comparison with related work. In [18], Hajirasouliha and Raphael introduced the so-called
Minimum-Split-Row problem, in which only a given subset of rows of the input matrix needs to be
split and, roughly speaking, the task is to minimize the number of additional rows in the resulting
conflict-free row split. All results from [18] actually deal with the variant of the problem in which all
rows need to be split (some perhaps trivially by setting Ri = {ri }); in this case, the optimal value
of the Minimum-Split-Row problem coincides with the difference γ(M ) − r(M ), where r(M ) is the
number of rows of M . In the same paper, a lower bound on the value of γ(M ) was derived and, in
the concluding remarks of the paper, a study of the MDCRS problem was suggested. In subsequent
works by Hujdurović et al. [20], the MCRS problem was introduced and several claims from [18]
were proved incorrect, including an NP-hardness proof of the Minimum-Split-Row problem (which
would imply NP-hardness of the MCRS problem). However, it was shown in [20] that the MCRS
problem is indeed NP-hard, as is the MDCRS problem. Moreover, a polynomially solvable case of
the MCRS problem was identified and an efficient heuristic algorithm for the problem on general
instances was proposed, based on coloring cocomparability graphs.
4

The results of this paper improve on the previously known results about the two problems:
NP-hardness results are strengthened to APX-hardness results, approximation algorithms for the
two problems are proposed, and the heuristic algorithm for the MCRS problem given by Hujdurović
et al. from [20] is improved. The key tools leading to most of these results are the newly proposed
branching formulations and the new min-max theorem strengthening Dilworth’s theorem. The
min-max theorem has a constructive algorithmic proof, leading to a polynomial-time algorithm to
compute a chain partition of a given partially ordered set equipped with a monotone weight function
such that the of sum of the maximum weights in the chains is minimized. This result contrasts
with known results in the literature implying that two natural variants of the problem are NP-hard:
(i) the variant in which the chains used in the partition have to be of bounded size [25, 29], and
(ii) the variant in which the weight function is not necessarily monotone, which corresponds to a
variant of the graph coloring problem known as Weighted Coloring (see, e.g., [3, 6, 8, 15]), in the
class of cocomparability graphs. We refer to the remarks following Corollary 3.5 in Section 3.1
for more details. See also Figure 10 in Section 5, where we summarize the relations between the
problems introduced in this paper and several problems studied in the literature, along with the
corresponding complexity results.
Structure of the paper. The branching formulations of the two problems are given in Section 2.
A strengthening of Dilworth’s theorem and its connection to the MCRS problem is discussed in
Section 3. APX-hardness proofs and approximation algorithms are presented in Section 4. We
conclude the paper with a summary and some questions for future research in Section 5.
Remark on notation. A binary matrix M ∈ {0, 1}m×n is a matrix having m rows and n columns,
and all entries 0 or 1. Each row of such a matrix is a vector in {0, 1}n ; each column is a vector
in {0, 1}m . We will usually denote by RM = {r1 , . . . , rm } and CM = {c1 , . . . , cn } the (multi)sets
of rows and columns of M , respectively. The entry of M at row ri and column cj will be denoted
by Mi,j or Mri ,j when appropriate. For brevity, we will often write “the number of distinct rows
(resp., columns) of M ” to mean “the maximum number of pairwise distinct rows (resp., columns)
of M ”. Two rows (resp., columns) are considered distinct if they differ as binary vectors. All binary
matrices in this paper will be assumed to contain no row whose all entries are 0.
In our proofs and constructions we will often simplify the binary matrix M under consideration
by working instead with the matrix denoted by Red(M ), obtained by taking from M exactly one
copy from each set of identical columns.
An extended abstract of this work appeared in the proceedings of WG 2017 [19].

2

Formulations in Terms of Branchings in Directed Acyclic Graphs

In this section, we are going to formulate the MCRS and the MDCRS problems in terms of branchings in directed acyclic graphs (DAGs). First, we give the necessary definitions.
Definition 2.1. Let D = (V, A) be a DAG. A branching of D is a subset B of A such that (V, B)
is a digraph in which for each vertex v there is at most one arc leaving v.
The following construction (see, e.g., [18]) can be performed on any given binary matrix M and
results in a directed acyclic graph. Given a column cj ∈ CM , the support of cj is the set defined
as {ri ∈ RM : Mi,j = 1} and denoted by suppM (cj ). Given a binary matrix M ∈ {0, 1}m×n , the
containment digraph DM of M is the directed acyclic graph with vertex set V = {suppM (c) : c ∈
5

CM } and arc set A = {(v, v 0 ) : v, v 0 ∈ V ∧ v ⊂ v 0 } where ⊂ is the relation of proper inclusion of
sets. See Fig. 2 for an example.

M

DM

c1 c2 c3 c4 c5 c6



1
r1

r2 
r3 
r4

1

v5 = {r1 , r2 , r3 }

v6 = {r1 , r3 , r4 }



1 1 1

1 1

1 1
1 1 
1

v3 = {r1 , r3 }

v4 = {r1 , r2 }
v1 = {r1 }

v2 = {r3 }

Figure 2: An example of a binary matrix M and its containment digraph DM .
Let M ∈ {0, 1}m×n be a binary matrix, let DM = (V, A) be the containment digraph of M ,
and let B be a branching of DM . For a vertex v ∈ V , we denote by NB− (v) the set of all vertices
v 0 ∈ V such that (v 0 , v) ∈ B. A source of B is a vertex not entered by any arc of B. For a vertex
v ∈ V , an element r ∈ v (that is, a row of M ) is said to be covered in v with respect to B (or just
B-covered) if r ∈ ∪ NB− (v). (When it is clear to which branching we are referring to, we will say
just that “r is covered in v”.) Analogously, we say that r ∈ v is uncovered in v with respect to B if
r is not covered in v. A B-uncovered pair is a pair (r, v) such that r is a row of M , v is a vertex of
DM (that is, the support of a column of M ), r ∈ v, and r is uncovered in v with respect to B. For
a row r of M , we will denote by UB (r) the set of all B-uncovered pairs with first coordinate r, and
by U (B) the set of all B-uncovered pairs. To illustrate these notions, we elaborate further on the
example from Fig. 2 in Fig. 3, where two branchings B1 and B2 of the arc set of DM are depicted,
together with uncovered pairs (r, v) with respect to each of the two branchings.
For a branching B ⊆ A, we say that a vertex v ∈ V is B-irreducible if there exists some element
r ∈ v that is uncovered in v with respect to B (equivalently, if v 6∈ ∪ NB− (v)). In particular, every
source of B is B-irreducible. We denote by I(B) the set of all B-irreducible vertices; see Fig. 3 for
an example.
We denote by β(M ) the minimum number of elements in U (B) over all branchings B of DM .
Similarly, we denote with ζ(M ) the minimum number of elements in I(B) over all branchings B of
DM . The corresponding optimization problems are the following:
MinimumUncoveringBranching (MUB):
Input:
Task:

MinimumIrreducingBranching (MIB):

A binary matrix M .
Compute β(M ).

Input:
Task:

A binary matrix M .
Compute ζ(M ).

The announced equivalence between the MCRS and the MUB problems, and between the
MDCRS and the MIB problems is captured in the following theorem. We denote by ω any real
number such that there exists an O(nω ) algorithm for multiplying two n × n binary matrices (e.g.,
ω = 2.3728639 [23]).
Theorem 2.1. For every binary matrix M ∈ {0, 1}m×n with exactly k distinct columns, the following holds:
1. Any branching B of DM can be transformed in time O(kmn) to a conflict-free row split of M
with exactly |U (B)| rows and with exactly |I(B)| distinct rows.
6

M

DM

c1 c2 c3 c4 c5 c6



1
r1
r2 

r3 
r4

1
1

v5 = {r1 , r2 , r3 }

v6 = {r1 , r3 , r4 }



1 1 1

1 1

1
1 1 
1

v3 = {r1 , r3 }

v4 = {r1 , r2 }
v1 = {r1 }

v2 = {r3 }

B1
v5 = {r1 , r2 , r3 }

B2

v3 = {r1 , r3 }

v4 = {r1 , r2 }

v3 = {r1 , r3 }

v4 = {r1 , r2 }
v1 = {r1 }

v1 = {r1 }

v2 = {r3 }

M B1

v2 = {r3 }

M B2
c1 c2 c3 c4 c5 c6

c1 c2 c3 c4 c5 c6


(r1 , v1 )




(r

1 , v4 )


(r2 , v4 )
U (B1 )
(r3 , v2 )




(r3 , v5 )



(r4 , v6 )

v6 = {r1 , r3 , r4 }

v5 = {r1 , r2 , r3 }

v6 = {r1 , r3 , r4 }










1

1

1
1 1
1 1

1

1







1 


1
1


(r1 , v1 )




(r1 , v4 )




 (r1 , v6 )
(r2 , v4 )
U (B2 )


(r3 , v2 )




(r3 , v6 )



(r4 , v6 )












1

1

1

1

1
1 1
1 1
1




1 





1 
1

I(B2 ) = {v1 , v2 , v4 , v6 }

I(B1 ) = {v1 , v2 , v4 , v5 , v6 }

Figure 3: An example of a binary matrix M , its containment digraph DM with two branchings B1
and B2 , and the resulting row splits of M (the B1 -split and B2 -split). The row split M B1 is an
optimal solution to the MCRS problem given M . The row split M B2 is an optimal solution to the
MDCRS problem given M . Pairs (r, v) for which r is underlined as an element of v in the figure
showing B1 (respectively, B2 ) are exactly the uncovered elements with respect to B1 (respectively,
B2 ).
0

2. Any conflict-free row split M 0 ∈ {0, 1}m ×n of M can be transformed in time
O(mn + m0 k 2 + k ω ) to a branching B of DM such that |U (B)| is at most the number of
rows of M 0 and |I(B)| is at most the number of distinct rows of M 0 .
Consequently, for every binary matrix M , we have γ(M ) = β(M ) and η(M ) = ζ(M ).
Results presented in Sections 3.2, 4.1, and 4.3 will rely on Theorem 2.1. Before giving a proof of
the theorem, let us discuss one further consequence of it. The theorem allows for the development
of faster exact exponential-time solutions for the two problems, when compared to a direct bruteforce approach that follows directly from the problems’ definitions. Consider the simple approach
7

of enumerating all possible branchings of DM and selecting the best one. Denoting by W the set
of vertices u of DM of out-degree d+ (u) at least
Qone and disregarding polynomial factors, the time
complexity of this approach is of the order O( u∈W d+ (u)) = O(nn ) = O(2n log n ), where n is the
number of distinct columns of the input matrix M . On the other hand, the time complexity of
the straightforward approach to the two problems based on generating all possible row splits of M
cannot even be expressed as a function of n only. A row with k ones has at least as many splits
as the number of partitions of a k-element set, which is the quantity counted by the Bell number
Bk and clearly bounded from below by 2k . Thus, for a matrix with m rows, each with at least n/2
ones, the total number of row splits of M is at least 2mn/2 .
Theorem 2.1 will be proved in two steps. First, we show how to split the input matrix M
in a conflict-free way, given a branching B of its containment digraph; the number of rows (resp.,
distinct rows) of the resulting row split equals the number of B-uncovered pairs (resp., B-irreducible
vertices). Second, we show that any conflict-free row split M 0 of M can be reduced, by possibly
deleting some rows, into a row split of M obtained from some branching of DM (as in the first
step).
The proof of the first part of Theorem 2.1 relies on the notion of a B-split, defined as follows.
Definition 2.2. Let M be a binary matrix with rows r1 , . . . , rm and columns c1 , . . . , cn . For a
branching B of DM , we define the B-split of M , denoted by M B , as the matrix with rows indexed
by the elements of the set U (B), and columns c01 , . . . , c0n , as follows. Let V = V (DM ) and for all
j ∈ {1, . . . , n}, let vj = suppM (cj ) (so vj ∈ V ). For a vertex v ∈ V , we denote by B + (v) the set
of all vertices in V reachable by a directed path from v in (V, B) (note that v ∈ B + (v)). For all
(r, v) ∈ U (B) and all j ∈ {1, . . . , n}, set:

1, if vj ∈ B + (v);
B
M(r,v),j =
0, otherwise.
B
Note that if M(r,v),j
= 1, then r ∈ vj . See Fig. 3 for an example of a binary matrix M with two
branchings B1 and B2 of its containment digraph and the corresponding row splits.
In the following lemma we show that the B-split of M is a conflict-free row split of M and
compute the number of rows (resp., the number of distinct rows) of M B .

Lemma 2.2. Let M be a binary matrix without duplicated columns, B a branching of DM , and
let M B be the B-split of M . Then M B is a conflict-free row split of M with |U (B)| rows, splitting
each row ri of M into rows of M B indexed by UB (ri ). Moreover, the number of distinct rows in
M B is |I(B)|.
Proof. It is clear that the number of rows in M B is |U (B)|. For a row r of M , we claim that r is the
bitwise OR of the rows of M B indexed by the set UB (r). Suppose that Mr,j = 1. Then r ∈ vj . We
B
claim that there exists a vertex v ∈ V such that (r, v) ∈ UB (r) and M(r,v),j
= 1. If (r, vj ) ∈ UB (r),
we can choose v = vj and we are done. If this is not the case, then r is covered in vj , and hence
r ∈ vk for some vk such that (vk , vj ) ∈ B. Now if (r, vk ) 6∈ UB (r), then we repeat the argument
with vk replaced by a “covering” in-neighbor. The procedure has to terminate after finitely many
B
steps. Hence, we may assume that (r, vk ) ∈ UB (r). This implies that M(r,v
= 1. Suppose now
k ),j
B
that Mr,j = 0. Then r 6∈ vj and therefore M(r,v),j = 0, for every (r, v) ∈ UB (r). This shows that r
is bitwise OR of the rows of M B indexed by UB (r), and therefore M B is row split of matrix M .
8

Suppose that two columns c0p and c0q of M B are in conflict. Then there exist row indices,
B
B
B
B
(ri , vi0 ), (rj , vj 0 ) and (rk , vk0 ) in U (B) such that M(r
= M(r
= M(r
= M(r
=1
i ,v 0 ),p
i ,v 0 ),q
j ,v 0 ),p
k ,v 0 ),q
i

B
and M(r
j ,v

j 0 ),q

B + (v

B
= M(r
k ,v

k0 ),p

i

j

k

B
B
= 0. Since M(r
= M(r
= 1, we have vp ∈ B + (vi0 ) and
i ,v 0 ),p
i ,v 0 ),q
i

i

vq ∈
), that is, vp and vq are reachable by a directed path from vi0 in (V, B). Since B is
a branching, this is only possible if vq ∈ B + (vp ) or vp ∈ B + (vq ); we may assume without loss
B
of generality that vq ∈ B + (vp ). Since M(r
= 1, it follows that vp ∈ B + (vj 0 ). This further
j ,v 0 ),p
i0

j

implies that vq ∈ B + (vj 0 ). Since rj ∈ vj 0 , it follows that rj ∈ vq , which contradicts the fact that
B
M(r
= 0. The obtained contradiction shows that M B is conflict-free.
j ,v 0 ),q
j

It remains to prove that the number of distinct rows in M B is |I(B)|. Note that for any row
(r, v) in M B we have v ∈ I(B). Let v ∈ I(B). It is not difficult to see that for ri , rj ∈ V such that
(ri , v) ∈ U (B) and (rj , v) ∈ U (B), the rows of M B indexed by (ri , v) and (rj , v) are equal. Hence
the number of distinct rows in M B is at most |I(B)|. To complete the proof we construct a set of
size |I(B)| of pairwise distinct rows of M B . For every vi ∈ I(B), let ri be an arbitrary element of
the (non-empty) set vi \ ∪NB− (vi ). Since ri is uncovered in vi with respect to B, the pair (ri , vi )
is an element of U (B). We claim that the rows of M B indexed by (ri , vi ) over all vi ∈ I(B) are
pairwise distinct. Suppose that there exist vi and vj in I(B) such that vi 6= vj and the rows of
B
B
M B indexed by (ri , vi ) and (rj , vj ) are equal. Since M(r
i ,v ),i = M(r j ,v ),j = 1 and the two rows are
i
j
B
B
+
+
equal, we infer that M(r
i ,v ),j = M(r j ,v ),i = 1. Therefore vj ∈ B (vi ) and vi ∈ B (vj ). Since B is
i
j
a DAG, it follows that vi = vj , a contradiction. This shows that there are exactly |I(B)| distinct
rows in M B .

The following lemma, exemplified in Fig. 4, is the key to the converse direction.
Lemma 2.3. There exists an algorithm that takes as input a binary matrix M without duplicated
0
columns and a conflict-free row split M 0 ∈ {0, 1}m ×n of M , and computes in time O(m0 n2 + nω )
a branching B of DM such that M B can be obtained from M 0 by removing some rows.
Proof. Denote the rows of M with r1 , . . . , rm and the columns with c1 , . . . , cn . Let Ri be the set
of split rows of ri , and let c0i be the column of M 0 corresponding to ci . For i ∈ {1, . . . , n}, let
vi = suppM (ci ) and vi0 = suppM 0 (c0i ). We claim that for every i, j ∈ {1, . . . , n}, if (vi0 , vj0 ) is an arc
in DM 0 then (vi , vj ) is an arc in DM . Suppose that (vi0 , vj0 ) is an arc in DM 0 and (vi , vj ) is not an
arc in DM . It follows that vi0 ⊆ vj0 and vi 6⊆ vj . Let rk ∈ vi \ vj . Then Mr0 0 ,i = 1 for some r0 ∈ Rk .
Since vi0 ⊆ vj0 , it follows that Mr0 0 ,j = 1 and consequently rk ∈ vj , a contradiction.
We say that an arc (vi0 , vj0 ) is elementary in DM 0 if there exists no k ∈ {1, . . . , n} such that
both (vi0 , vk0 ) and (vk0 , vj0 ) are arcs of DM 0 . Let B be the subset of the arc set of DM defined by
(vi , vj ) ∈ B if and only if vi0 6= ∅ and (vi0 , vj0 ) is an elementary arc of DM 0 . We claim that B is
a branching of DM . Suppose that (vi , vj ) ∈ B and (vi , vk ) ∈ B, for j 6= k. Then, both (vi0 , vj0 )
and (vi0 , vk0 ) are elementary arcs of DM 0 , which implies that vi0 ⊆ vj0 ∩ vk0 . Since vi0 6= ∅ and M 0
is conflict-free, it follows that vj0 ⊆ vk0 or vice versa. By definition of B, we obtain that vj0 = vk0 .
However, since vj 6= vk , we may assume that there exists some rp ∈ vj \ vk , and therefore, there
exists r0 ∈ Rp , such that r0 ∈ vj0 . Since rp 6∈ vk we have Rp ∩ vk0 = ∅, contrary to the fact that
r0 ∈ Rp ∩ vj0 = Rp ∩ vk0 . We conclude that B is a branching.
Next, we prove that M B can be obtained from M 0 by removing some rows, or, equivalently,
that there exists a one-to-one mapping assigning to each row of M B an identical row of M 0 . Every
row of M B is indexed by an element of U (B). Every element of U (B) is of the form (ri , vk ) with
9

M0
M

r10
r100
r1000
r20
r200
r30
r300

c1 c2 c3 c4 c5 c6



1
r1
r2 

r3 
r4

1
1



1 1 1

1 1

1
1 1 
1

c01 c02 c03 c04 c05 c06



1

1

1

1
1

1
1
1

1













1

1

r4

DM

v5 = {r1 , r2 , r3 }

v6 = {r1 , r3 , r4 }

v1 = {r1 }

v5 = {r1 , r2 , r3 }

v30 = {r100 , r30 }
v10 = {r10 }

MB

v6 = {r1 , r3 , r4 }

(r1 , v1 )
(r1 , v3 )
(r2 , v4 )
(r3 , v2 )
(r3 , v5 )
(r4 , v6 )

v3 = {r1 , r3 }
v1 = {r1 }

v60 = {r100 , r300 , r4 }

v50 = {r10 , r1000 , r20 , r200 , r300 }

v2 = {r3 }

v4 = {r1 , r2 }

1 







1 


1
1

v40 = {r10 , r1000 , r20 }

v3 = {r1 , r3 }

v4 = {r1 , r2 }

B

DM 0



v2 = {r3 }

v20 = {r30 }

c1 c2 c3 c4 c5 c6










1

1
1
1
1

1

1



1 


1

1 


1
1

= r10
= r100
= r20
= r30
= r300
= r4

Figure 4: An example of a binary matrix M , a conflict-free row split M 0 of M , with their contain0 , the resulting branching B of D , and the resulting B-split M B .
ment digraphs DM and DM
M
(ri , vk ) ∈ UB (ri ) for some i ∈ {1, . . . , m} and ri ∈ vk . To define a mapping as above, it suffices to
show that there exists a row r0 of M 0 such that r0 ∈ Ri and r0 is equal to the row of M B indexed
by (ri , vk ), or more precisely that Mr0 0 ,j = 1 if and only if vj ∈ B + (vk ). First, observe that ri ∈ vk
implies that there exists some r0 ∈ Ri such that Mr0 0 ,k = 1.
Assume that Mr0 0 ,j = 1. Since Mr0 0 ,k = Mr0 0 ,j = 1 and M 0 is conflict-free, it follows that either
0
vj ⊆ vk0 or vk0 ⊆ vj0 . Suppose that vj0 is a proper subset of vk0 and therefore there exists a non-trivial
vj0 , vk0 -path P 0 consisting only of elementary arcs of DM 0 . Since r0 is an element of vj0 , the set vj0 is
non-empty, which implies that the path P 0 corresponds to a non-trivial vj , vk -path P in B, therefore
vk ∈ B + (vj ). Since Mr0 0 ,j = 1, and r0 ∈ Ri , it follows that ri ∈ vj . However, this contradicts the
fact that (ri , vk ) ∈ UB (ri ). Therefore, vk0 ⊆ vj0 and consequently vj ∈ B + (vk ). We proved that
Mr0 0 ,j = 1 implies that vj ∈ B + (vk ).
Suppose now that vj ∈ B + (vk ). If vj = vk , then j = k and Mr0 0 ,j = Mr0 0 ,k = 1, as desired.
If vj 6= vk , then since vj ∈ B + (vk ), it follows that vk0 ⊆ vj0 . Combining this with the fact that
Mr0 0 ,k = 1, we conclude that Mr0 0 ,j = 1. This completes the proof that the row r0 of M 0 is equal to
the row of M B indexed by (ri , vk ).

10

The above considerations imply the existence of a mapping assigning to each row of M B an
identical row of M 0 . In fact, any mapping as defined above is also one-to-one, which can be seen as
follows. First, two rows of M B indexed by elements of U (B) with distinct first coordinates, say ri
and rj , will be mapped to rows of M 0 from Ri and Rj , respectively, and by construction the sets
Ri and Rj are disjoint. Second, suppose we have two rows of M B indexed by elements of U (B)
with identical first coordinates but distinct second coordinates, say (ri , vj ) and (ri , vk ). The last
part of the proof of Lemma 2.2 implies that no two rows of M B indexed by pairs that differ in the
values of their second coordinates are identical. Consequently, the images of rows of M B indexed
by (ri , vj ) and (ri , vk ) are also not identical (as binary vectors), and therefore they correspond to
different rows of M 0 .
We conclude that M B can be obtained from M 0 by deleting some rows.
It remains to estimate the time complexity of computing branching B. First, we compute the
containment digraph DM 0 in time O(m0 n2 ). Second, we compute the set A0 of elementary arcs of
DM 0 in time O(nω ) using the algorithm of Aho et al. [1]. Finally, branching B can be computed
from A0 in time O(|A0 |) = O(n2 ). The claimed running time follows.
Now we have everything ready to prove Theorem 2.1.
Theorem 2.1 (restated). For every binary matrix M ∈ {0, 1}m×n with exactly k distinct columns,
the following holds:
1. Any branching B of DM can be transformed in time O(kmn) to a conflict-free row split of M
with exactly |U (B)| rows and with exactly |I(B)| distinct rows.
0

2. Any conflict-free row split M 0 ∈ {0, 1}m ×n of M can be transformed in time
O(mn + m0 k 2 + k ω ) to a branching B of DM such that |U (B)| is at most the number of
rows of M 0 and |I(B)| is at most the number of distinct rows of M 0 .
Consequently, for every binary matrix M , we have γ(M ) = β(M ) and η(M ) = ζ(M ).
Proof. Let B be a branching of DM . By Lemma 2.2, it suffices to show that M B , the B-split of
M , can be computed in time O(kmn). This can be achieved as follows. First, we compute the
reduced matrix Red(M ) in time O(mn) using radix sort. Second, we compute the containment
digraph DM in time O(k 2 m) = O(kmn) by performing pairwise comparisons of columns of Red(M ).
Third, we compute the set U (B) in time O(k 2 m) = O(kmn) by checking for each of the k vertices
v ∈ V (DM ), each of the O(m) elements r ∈ v, and each of the O(k) in-neighbors u of v in DM
whether r ∈ u. Fourth, in time O(k 2 ) we compute for each v ∈ V (DM ) the set B + (v). Finally, in
time O(|U (B)|n) we compute the matrix M B using the definition. Note that |U (B)| ≤ km, hence
O(|U (B)|n) = O(kmn) and the claimed time complexity follows.
0
Now, let M 0 ∈ {0, 1}m ×n be a conflict-free row split of M .
Consider first the case when M is without duplicated columns. In this case k = n and by
Lemma 2.3, in time O(m0 n2 + nω ) a branching B of DM can be computed such that M B , the
B-split of M , can be obtained from M 0 by removing some rows. Since |U (B)| (resp., |I(B)|) equals
the number of rows (resp., the number of distinct rows) of M B , this implies that |U (B)| is at most
the number of rows of M 0 and |I(B)| is at most the number of distinct rows of M 0 .
Consider now the general case. Let X be a set of k columns of M such that the matrix
Red(M ) can be identified with the submatrix of M obtained by considering only the columns in
0
X. Let M 00 ∈ {0, 1}m ×k be the submatrix of M 0 obtained by considering only the k columns
11

in X. Then, M 00 is a conflict-free row split of Red(M ). Note that matrix M 00 can be computed
in time proportional to its size, m0 k, plus the number of columns, n, plus the time it takes to
compute Red(M ), which can be done in time O(mn) using radix sort. Since Red(M ) is without
duplicated columns, we have by the previous case that in time O(m0 k 2 + k ω )) a branching B of
DRed(M ) = DM can be computed such that |U (B)| is at most the number of rows of M 00 and
|I(B)| is at most the number of distinct rows of M 00 . Since the number of rows of M 00 equals the
number of rows of M 0 , this immediately implies that |U (B)| is at most the number of rows of M 0 .
Also, by construction, any two distinct rows of M 00 correspond to a pair of distinct rows of M 0
and hence the number of distinct rows of M 00 is at most the number of distinct rows of M 0 . This
implies that |I(B)| is at most the number of distinct rows of M 0 . The total time complexity is
O(m0 k + mn + m0 k 2 + k ω ) = O(mn + m0 k 2 + k ω ), which establishes the second part of the theorem.
Finally, we show that γ(M ) = β(M ) and η(M ) = ζ(M ). Let B be a branching of DM such that
|U (B)| = β(M ). By the first part of the theorem, there exists a conflict-free row split M 0 of M with
|U (B)| rows, therefore γ(M ) ≤ |U (B)| = β(M ). Conversely, if M 0 is a conflict-free row split of M
with γ(M ) rows, then there exists a branching B of DM such that |U (B)| is at most the number
of rows of M 0 (that is, γ(M )). This implies β(M ) ≤ |U (B)| ≤ γ(M ). Therefore, γ(M ) = β(M ).
The proof of equality η(M ) = ζ(M ) is analogous.

3

A Strengthening of Dilworth’s Theorem and its Connection to
the Minimum Conflict-Free Row Split Problem

By Theorem 2.1, the MCRS problem can be concisely formulated in terms of a problem on branchings in a derived digraph. As shown by Hujdurović et al. in [20], the MCRS problem is NP-hard;
consequently, the MUB problem is also NP-hard. In this section we show that a related problem
in which we examine only a subset of all the branchings of the containment digraph of the input
binary matrix is polynomially solvable. This will be achieved by deriving, in Section 3.1, a min-max
theorem generalizing the classical Dilworth’s theorem on partially ordered sets, which may be of
independent interest. The resulting heuristic algorithm will be described in Section 3.2 (see also
Remark 4.13 on p. 24).

3.1

A Min-Max Relation Strengthening Dilworth’s Theorem

This section can be read independently of the rest of the paper.
Consider a pair (D, f ) where D = (V, A) is a DAG and f : V → Z+ is a weight function of
D. (We use Z+ for the set of non-negative integers.) The weight function f is called monotone if
fu ≤ fv for every (u, v) ∈ A.
In D, a non-trivial path is a directed path with at least one arc. We denote by Dt the transitive
closure of D, that is, the DAG (V, At ) on the same vertex set as D having an arc (u, v) ∈ At
if and only if there exists a non-trivial path in D from u to v. A chain in D is a sequence
of vertices C = (v1 , v2 , . . . , vs ) such that (vi , vi+1 ) ∈ At for all i ∈ {1, . . . , s − 1}; sometimes
we regard C as the set of its vertices C = {v1 , v2 , . . . , vs }. The price of chain C is given by
Π(C) = maxv∈C fv . A family of vertex-disjoint chains P = {C1 , . . . , Cp } is called a chain partition
of D if every vertex of
PD is contained in precisely one chain of P . The price of chain partition P
is defined as Π(P ) = pi=1 Π(Ci ). Consider the following problem.

12

MinimumPriceChainPartition:
Input: A DAG D = (V, A) and a monotone weight function f : V → Z+ of D.
Task: Compute a chain partition P of D such that the price Π(P ) is minimum possible.
In this section we give a polynomial-time algorithm and a min-max characterization for the
above problem. As can be expected, the notion of antichain will play a main role in this min-max
characterization. An antichain of D is a set of vertices N ⊆ V such that N is an independent set
(that is, a set of pairwise non-adjacent vertices) in Dt ; in other words, no non-trivial path of D has
both endpoints in N . Note that |C ∩ N | ≤ 1 for any chain C and any antichain N . The width of
D, denoted by wdt(D), is the maximum cardinality of an antichain in D.
A classical theorem of Dilworth states that wdt(D) equals the minimum number of chains in a
chain partition of D [7]. Moreover, a chain partition of D into wdt(D) chains can be computed in
e ω ) where n = |V (D)|, ω is any real number such that there exists an O(nω ) algorithm for
time O(n
e notation ignores logarithmic
multiplying two n × n binary matrices (e.g., ω = 2.373), and the O(·)
factors. Indeed, by applying the approach of Fulkerson [12] (see also [24, 26]), a minimum chain
partition of D can be computed by solving a maximum matching problem in a derived bipartite
e ω ) using the algorithm of [21].2
graph having 2n vertices. This can be done in time O(n
For later use, we summarize these facts as follows.
Theorem 3.1 (Dilworth’s theorem). Every DAG D admits a chain partition of size wdt(D). Such
e (D)|ω ).
a chain partition can be computed in time O(|V
Our characterization will be a refinement of Dilworth’s theorem and its algorithmic proof makes
use of Dilworth’s theorem as a subroutine. We must introduce one further notion however. A
tower of antichains of D is a sequence of antichains of D, T = (N1 , N2 , . . . , Nwdt(D) ), with |Ni | =
i. The value of an antichain N is given by val (N ) = minv∈N fv and the value of tower T =
Pwdt(D)
(N1 , N2 , . . . , Nwdt(D) ) is defined as val (T ) = i=1 val (Ni ).
To appreciate the purpose of this notion, we begin with a simple observation.
Lemma 3.2. Let D be a DAG, let P = {C1 , . . . , Cp } be a chain partition of D, and let T =
(N1 , N2 , . . . , Nwdt(D) ) be a tower of antichains of D. Then, Π(P ) ≥ val (T ) even if the weight
function f is not monotone.
Proof. For every chain C and every antichain N we have that |C ∩N | ≤ 1. Moreover, if |C ∩N | = 1,
then Π(C) ≥ val (N ). Indeed, if C ∩ N = {z}, then
Π(C) = max fv ≥ fz ≥ min fv = val (N ).
v∈C

v∈N

Since P is a chain partition of D, then |P | ≥ wdt(D), and we can always rename its chains as
C̃1 , C̃2 , . . . , C̃p in such a way that, for every i = 1, . . . , wdt(D), chain C̃i intersects the antichain Ni .
At this point,
Π(P ) =

p
X
i=1

Π(Ci ) =

p
X
i=1

wdt(D)

Π(C̃i ) ≥

X
i=1

2

wdt(D)

Π(C̃i ) ≥

X

val (Ni ) = val (T ).

i=1

Alternatively, one could use the bipartite matching algorithm from [10] to obtain the (incomparable) running
√
time of O( nm logn (n2 /m)) where m = |At | is the number of edges in the transitive closure of D. For the sake
of simplicity of presentation, we state the theorem with the running time resulting from using the Ibarra-Moran
algorithm.

13

For the case of monotone weight functions, the following min-max strengthening of Dilworth’s
theorem holds.
Theorem 3.3. Let D be a DAG and let f be a monotone weight function of D. Then D admits
a chain partition P = {C1 , . . . , Cwdt(D) } and a tower of antichains T = (N1 , N2 , . . . , Nwdt(D) ) such
e (D)|ω+1 ).
that Π(P ) = val (T ). Such a pair (P, T ) can be computed in time O(|V

Proof. The proof is by induction on n = |V (D)|. Clearly, the statement holds for n = 1. As for
the inductive step, let n > 1 and consider a vertex v ∈ V (D) without any incoming arcs and such
that fv ≤ fv0 for all v 0 ∈ V (D). Such a vertex exists since the subgraph of D induced by the set
of vertices achieving the minimum value of f is acyclic. Let D0 = D − v, and consider a chain
partition P 0 = {C1 , . . . , Cwdt(D0 ) } of D0 and a tower of antichains T 0 = (N1 , N2 , . . . , Nwdt(D0 ) ) of D0
such that Π(P 0 ) = val (T 0 ).
Two cases are possible. If wdt(D) > wdt(D0 ) then let P be obtained from P 0 by adding a chain
C comprising the sole vertex v and let T be obtained from T 0 by adding any antichain Nwdt(D) of
D such that |Nwdt(D) | = wdt(D). Since |Nwdt(D) | > wdt(D0 ), we infer that v ∈ Nwdt(D) and hence
minu∈Nwdt(D) fu = fv = Π(C). Therefore, Π(P ) = val (T ) closing the induction in this case.
Assume therefore that wdt(D) = wdt(D0 ). Let T be an antichain in D0 with |T | = wdt(D) and
let Tb be the set of vertices of D from which there is a non-trivial path to a vertex of T . Notice that
v ∈ Tb since T ∪ {v} is not an antichain and v is a source vertex of D. The DAG D[V (D) \ Tb] is an
acyclic subgraph of D0 of width at least |T | = wdt(D0 ), since T is a subset of its vertex set. Moreover,
while the width of an arbitrary induced subgraph can in general increase with vertex removal, this is
not the case for D[V (D) \ Tb], because any path in D between two vertices of V (D) \ Tb is also a path
in D[V (D) \ Tb], by the choice of Tb. It follows that the DAG D[V (D) \ Tb] is of width |T | = wdt(D0 );
T
hence, by the inductive hypothesis, it admits a chain partition P T = {C1T , . . . , Cwdt(D
0 ) } with
Π(P T ) ≤ Π(P 0 ) = val (T 0 ). (Indeed, we could just take CiT := Ci \ Tb for every i ∈ {1, . . . , wdt(D0 )}.)
Also the acyclic subgraph D[T ∪ Tb] of D has width |T | = wdt(D0 ); hence, by Dilworth’s theorem it
T
admits a chain partition P T = {C1T , C2T , . . . , Cwdt(D
0 ) } covering all its vertices. Now we construct
our chain partition for D: let T = {t1 , t2 , . . . , t|T | }. After a possible renaming of the chains
b

b

b

b

in the two chain partitions, we can assume that CiT ∩ T = {ti } and CiT ∩ T = {ti } for every
b
i = 1, . . . , wdt(D0 ) = wdt(D) = |T |, and hence define the chain C̃i = CiT ∪ CiT . (Indeed, ti will be
b
the last vertex of CiT and the first vertex of CiT , thus this chaining of chains can be performed.)
Note that P̃ := {C̃1 , . . . , C̃wdt(D) } is a chain partition of D with Π(P̃ ) = Π(P T ) ≤ Π(P 0 ) = val (T 0 )
Clearly, T 0 is a valid tower of antichains for D.
The above proof of the existence of a pair (P, T ) of a chain partition and a tower of antichains of
e (D)|ω+1 ) time algorithm
D satisfying Π(P ) = val (T ) is constructive and can be turned into a O(|V
for computing such a pair (P, T ). Indeed, at each step of the algorithm, we delete one vertex, make
one recursive call to the algorithm, compute the set Tb and the acyclic subgraph D[T ∪ Tb] together
b
b
b
Tb
with a chain partition P T = {C1T , C2T , . . . , Cwdt(D
0 ) } covering all its vertices. The time complexity
b
e (D)|ω ).
of each step is dominated by computing P T . By Theorem 3.1, this can be done in time O(|V
ω+1
e (D)|
The claimed time complexity of O(|V
) follows.
b

To see that Theorem 3.3 is a strengthening of Dilworth’s theorem, consider an arbitrary DAG
D = (V, A) and let f be the weight function of D that is constantly equal to 1. Then, the price of
14

any chain C is Π(C) = maxv∈C fv = 1 and the price of a chain partition P equals its cardinality.
Moreover, the value of any antichain N is val (N ) = minv∈N fv = 1, and consequently the value of
Pwdt(D)
any tower T = (N1 , N2 , . . . , Nwdt(D) ) of antichains is val (T ) = i=1 val (Ni ) = wdt(D). Since
wdt(D) is a lower bound on the cardinality of any chain partition, applying Theorem 3.3 to (D, f )
gives exactly the statement of Dilworth’s theorem for D.
We would also like to emphasize that due to the non-linearity of the definitions of the price
of a chain and the value of an antichain, Theorem 3.3 is incomparable with the classical weighted
generalization of Dilworth’s theorem due to Frank [11].
Remark 3.4. The monotonicity assumption in Theorem 3.3 is necessary. If we drop it, the
price minP Π(P ) and the value maxT val (T ) may diverge. Consider the DAG on vertex set
{a}, {b}, {a, b}, {b, c}, with f{a} = f{b,c} = z and f{b} = f{a,b} = Z, with 0 < z < Z < 2z, and where
the arcs are according to set inclusion. Here, minP Π(P ) = 2Z whereas maxT val (T ) = Z + z.
On the other hand, a simple application of Dilworth’s theorem shows that the monotonicity
assumption is not necessary in the case of 0, 1-weight functions.
Lemma 3.2 and Theorem 3.3 imply the following.
e (D)|ω+1 ).
Corollary 3.5. MinimumPriceChainPartition can be solved optimally in time O(|V
More specifically, in the stated time a minimum price chain partition P of D can be found with the
additional property that |P | = wdt(D) (hence P is simultaneously a minimum price chain partition
and a minimum size chain partition of D).
Two remarks are in order here, showing that the result of Corollary 3.5 is sharp in two ways.
First, let us note that the variant of the MinimumPriceChainPartition problem in which the
chains used in the partition have to be of bounded size was studied by Moonen and Spieksma in [25],
who described a practical application encountered at Bruynzeel Storage Systems, a manufacturing
company in the Netherlands, to a problem of optimally loading pallets on a truck.3 Moonen and
Spieksma referred to the problem as “Minimum Weight Partition into B-chains” (where B is the
upper bound on the size of the chains) and showed that the problem is APX-hard even in the case
of unit weights, strengthening the previous NP-hardness result from [29].
Second, the variant of MinimumPriceChainPartition where the weight function f is not
restricted to be monotone is NP-hard. This follows from the fact that the Weighted Coloring
problem is NP-hard in the class of interval graphs, as shown by Escoffier et al. [8]. The input to
the Weighted Coloring problem is a graph G = (V, E) and a weight function f : VP→ Z+ and the
task is to find a partition I of V into independent sets minimizing the value of I∈I maxv∈I fv .
The Weighted Coloring problem in interval graphs finds applications in distributed computing in
transportation networks and in dynamic storage allocation in computer processes [15]. Given an
interval graph G = (V, E) represented by an interval model (Iv = [av , bv ] : v ∈ V ) and a weight
function f : V → Z+ , the Weighted Coloring problem given (G, f ) is equivalent to the problem of
finding a chain partition of the DAG with vertex set V and arc set {(u, v) : bu < av } of minimum
price with respect to f . The claimed NP-hardness follows.

3.2

Connection with the Minimum Conflict-Free Row Split Problem

We will now describe a heuristic algorithm for the MCRS problem based on Theorem 3.3 and its
algorithmic proof. The basic idea is to search for an optimal solution only among linear branchings,
3

The upper bound on the size of chains relates to the fact that trucks are of bounded height.

15

where a branching of DM is said to be linear if it defines a subgraph of maximum in- and outdegree at most one, that is, a disjoint union of directed paths. Note that such branchings correspond
bijectively to chain partitions of DM .
We denote with β` (M ) the minimum number of elements in U (B) over all linear branchings
B of DM . We now introduce the following problem, referred to as MinimumUncoveringLinearBranching: Given a binary matrix M , compute a linear branching B of DM such that
|U (B)| = β` (M ).
For a binary matrix M , define a function f : V (DM ) → Z+ with f (v) = |v| (recall that
vertices of DM are pairwise distinct subsets or RM ). By definition of DM , we have u ⊂ v whenever
(u, v) is an arc in DM . This implies that f is a monotone weight function of DM . It is not
difficult to see that for a linear branching B and its corresponding chain partition P , we have
Π(P ) = |U (B)|. Since linear branchings correspond bijectively to chain partitions, it follows that
MinimumUncoveringLinearBranching is a special case of MinimumPriceChainPartition.
Using Theorem 3.3, we obtain that a linear branching B of DM with |U (B)| = β` (M ) can be
e (D)|ω+1 ). This proves the following theorem.
computed in time O(|V
Theorem 3.6. MinimumUncoveringLinearBranching can be solved to optimality in time
e (D)|ω+1 ).
O(|V
Note that Theorem 3.6 yields a heuristic polynomial-time algorithm for the MUB problem, and
consequently for the MCRS problem. We are now going to explain why this algorithm improves
on the heuristic for the latter problem by Hujdurović et al. from [20]. For the sake of simplicity of
exposition, suppose that the input matrix M does not have any pairs of identical columns. (It is
not difficult to see that this assumption is without loss of generality.) In this case, the algorithm
from [20] returns a row split of the input matrix naturally derived from an optimal coloring of
the complement of the underlying undirected graph of DM , which is a cocomparability graph
and thus an optimal coloring can be computed efficiently, see, e.g., [14]. Such optimal colorings
correspond bijectively to minimum chain partitions of DM ; each color class corresponds to a chain.
In the terminology of branchings, the conflict-free row split of the input matrix M returned by the
heuristic from [20] is exactly the B-split of M (cf. Definition 2.2) where B is the linear branching
of DM corresponding to a minimum chain partition of DM .
In the above approach, any proper coloring could be used instead of an optimal coloring of
the derived cocomparability graph. In branching terminology, choosing a proper coloring of the
derived cocomparability graph so that the number of rows of the output row split is minimized
corresponds exactly to MinimumUncoveringLinearBranching, which can be solved optimally
by Theorem 3.6. Thus, the heuristic algorithm for the MCRS problem that returns the B-split
of M where M is an optimal solution to MinimumUncoveringLinearBranching always returns solutions that are at least as good as those computed by the algorithm by Hujdurović et
al. from [20]. Moreover, note that by Corollary 3.5, digraph DM has a minimum price chain partition that is also minimum with respect to size. This implies the existence of an optimal solution to
MinimumUncoveringLinearBranching on M such that the corresponding chain partition is of
size wdt(M ) and, equivalently, the existence of an optimal coloring of the derived cocomparability
graph that minimizes the number of rows in the derived conflict-free row split of M over all proper
colorings of the derived graph.
Remark 3.7. As discussed in [18, 20], the main motivation for the MCRS problem comes from
cancer genomics, with the goal to reconstruct, from a set of given mixed tumor samples, a simplest
16

possible mutational history of the tumor, represented by a rooted tree (without any restriction on the
shape of the tree). Without going into details, let us note that the output of the heuristic algorithm
for the MCRS problem given by Theorem 3.6 corresponds to a simplest possible reconstruction of
the mutational history within a restricted space of rooted trees, namely within the space of rooted
trees such that the root is the only node that is allowed to have more than one non-leaf child.

4

(In)approximability Issues

In this section we will discuss (in)approximability properties of the four problems studied in this
paper, giving both APX-hardness results and approximation algorithms. The approximation ratios
of some of our algorithms will be described in terms of the following parameters of the input matrix.
Recall that the width of a DAG D is the maximum cardinality of an antichain in D. The height of
a DAG D is the maximum number of vertices in a directed path contained in D. The width and
the height of a binary matrix M are denoted by wdt(M ) and by h(M ), respectively, and defined as
the width, resp. the height, of the containment digraph of M .

4.1

Hardness Results

Our main inapproximability results are summarized in the following theorem, which shows hardness
already for very restricted input instances.
Theorem 4.1. The MUB and the MIB problems (and consequently the MCRS and the MDCRS
problems) are APX-hard, even for instances of height 2.
The above result implies that none of the four problems admits a polynomial-time approximation
scheme (PTAS), unless P = NP. Proving that a problem is APX-hard also provides a different proof
of NP-hardness.
The APX-hardness for the two branching problems is established by developing L-reductions
from the vertex cover problem in cubic graphs, which is known to be APX-hard [2]. The APXhardness of the other two problems then follows from Theorem 2.1. Recall that APX is a class
of problems approximable to within a constant factor in polynomial time. A problem Π is said
to be APX-hard if every problem in APX reduces to Π by an approximation-preserving reduction.
Another way to prove that a problem Π is APX-hard is to show that an APX-complete problem Π0
is L-reducible to Π. For the sake of self-containment, we recall the definition of L-reducibility; for
further background on APX-hardness, we refer to [4].
Definition 4.1. Let Π and Π0 be two NP-hard optimization problems. Problem Π is said to be
L-reducible to problem Π0 if there exists a polynomial-time transformation f mapping instances of
Π to instances of Π0 and constants a, b ∈ R+ such that for every instance x of Π the following
conditions hold:
• optΠ0 (f (x)) ≤ a · optΠ ,
• for every feasible solution y 0 of f (x) with objective value c2 we can compute in polynomial
time solution y for x with objective value c1 such that |optΠ (x) − c1 | ≤ b · |optΠ0 (f (x)) − c2 |.
To simplify the description of the hardness reductions of this section, we will use the notion of a
column hypergraph of a given binary matrix M . This notion is closely related to the containment
17

digraph of M and will find a further application in Section 4.2. Recall that a set family (or a
hypergraph) is a pair H = (V, E) where V = V (H) is a set and E = E(H) is a subset of the power
set P(V ). Elements of V (H) are the vertices of H; elements of E(H) are its hyperedges. The column
hypergraph HM of a binary matrix M is the hypergraph having the rows of M as vertices and the
support sets of the columns of M as hyperedges. Formally, HM has vertex set V (HM ) = RM and
hyperedge set E(HM ) = {suppM (c) : c ∈ CM }. Note that the set of hyperedges of the column
hypergraph of M equals the vertex set of the containment digraph DM .
We split the proof of Theorem 4.1 into two parts.
Proposition 4.2. MinimumUcoveringBranching is APX-hard, even for instances of height 2.
Consequently, MinimumConflict-FreeRowSplit is APX-hard, even for instances of height 2.
Proof. We will prove the proposition using the fact that the vertex cover problem is APX-hard on
cubic graphs [2]. Recall that a graph G is cubic if every vertex of G is incident with exactly three
edges and that a vertex cover of a graph G is a subset C ⊆ V (G) such that ∀ e = {v1 , v2 }, e ∈
E(G) ⇒ v1 ∈ C ∨ v2 ∈ C. For all v ∈ V (G), we define E(v) as a set of all edges in E(G) incident
with v. In symbols, E(v) = {e ∈ E(G) : v ∈ e}. We say that a graph G is cubic if for every
v ∈ V (G) it holds |E(v)| = 3.
We will construct an L-reduction from the vertex cover problem in cubic graphs to the MUB
problem on instances of height 2. Let G be a cubic graph. Let x and y be two new vertices not in
V (G) ∪ E(G). Let R = E(G) ∪ {x, y} and let H be the hypergraph with vertex set R and edge set
E

= {E(G) ∪ {x}} ∪ {E(v) ∪ {x} : v ∈ V (G)} ∪ {E(v) ∪ {y} : v ∈ V (G)}
∪ {E(v) ∪ {x, y} : v ∈ V (G)} .

Let M be a binary matrix without duplicated columns such that the column hypergraph of M is
isomorphic to H. Note that M is of height 2. See Fig. 5 for an example construction, representing
the containment digraph DM of the binary matrix derived from the complete graph K4 .
v1

G

DM

E ∪ {x}

E(v1 ) ∪ {x, y}

E(v2 ) ∪ {x, y}

E(v3 ) ∪ {x, y} E(v4 ) ∪ {x, y}

v4

v3

v2

E(v1 ) ∪ {x} E(v2 ) ∪ {x} E(v3 ) ∪ {x} E(v4 ) ∪ {x} E(v1 ) ∪ {y} E(v2 ) ∪ {y} E(v3 ) ∪ {y}

E(v4 ) ∪ {y}

Figure 5: An example construction of the L-reduction from the proof of Proposition 4.2.
We denote by τ (G) the vertex cover number of G, that is, the minimum size of a vertex cover in
G. The APX-hardness of MinimumUcoveringBranching will be a consequence of the following
claim and its proof.
Claim. τ (G) = β(M ) − 8|V (G)|.
Proof of the claim. We split the proof of the equality into two parts, proving each of the two
inequalities separately.
18

First, we prove the inequality β(M ) ≤ τ (G) + 8|V (G)|. Let C be a minimum vertex cover of
G. Define a branching B of DM as follows:
B = {(E(v) ∪ {y}, E(v) ∪ {x, y}) : v ∈ V (G)}
∪ {(E(v) ∪ {x}, E ∪ {x}) : v ∈ C}

∪ {(E(v) ∪ {x}, E(v) ∪ {x, y}) : v ∈ V (G) \ C}
See Fig. 6 for an example.

DM

E ∪ {x}

E(v1 ) ∪ {x, y}

E(v2 ) ∪ {x, y}

E(v3 ) ∪ {x, y} E(v4 ) ∪ {x, y}

E(v1 ) ∪ {x} E(v2 ) ∪ {x} E(v3 ) ∪ {x} E(v4 ) ∪ {x} E(v1 ) ∪ {y} E(v2 ) ∪ {y} E(v3 ) ∪ {y}

E(v4 ) ∪ {y}

Figure 6: The set of non-dashed arcs corresponds to the branching obtained from the vertex cover
{v1 , v2 , v3 }.
It is clear from the construction that B is indeed a branching. Since C is a vertex cover, every
e ∈ E(G) is covered in E(G) ∪ {x} with respect to B. It is now not difficult to see the set of
uncovered pairs with respect to B equals
U (B) = {(r, E(v) ∪ {z}) : v ∈ V (G), z ∈ {x, y}, r ∈ E(v) ∪ {z}}
∪ {(x, E(v) ∪ {x, y}) : v ∈ C} .

Since we have |E(v)| = 3 for all v ∈ V (G), this implies β(M ) ≤ |U (B)| = 8|V (G)| + |C| =
8|V (G)| + τ (G), as claimed.
Now we prove the inequality τ (G) ≤ β(M ) − 8|V (G)|. Let B be a branching of DM such
that |U (B)| = β(M ). For every source vertex u in DM and every element r ∈ u it holds that r
is uncovered in u. Since the source vertices are exactly the vertices of the form E(v) ∪ {x} and
E(v) ∪ {y}, we have exactly 8|V (G)| uncovered pairs corresponding to the source vertices. The
minimality of B implies that all arcs of the form (E(v) ∪ {y}, E(v) ∪ {x, y}) are in B. Therefore,
for every v ∈ V (G), element x is the only possibly uncovered element in vertex E(v) ∪ {x, y}.
We show that we may assume that vertex E(G) ∪ {x} is not irreducible, that is, that all its
elements are covered in E(G) ∪ {x}. Suppose first that x is not covered in E(G) ∪ {x}. Then
B does not contain any arc of the form (E(v) ∪ {x}, E(G) ∪ {x}), and therefore, by minimality,
contains all arcs of the form (E(v) ∪ {x}, E(v) ∪ {x, y}). Replacing one of these arcs with the
arc (E(v) ∪ {x}, E(G) ∪ {x}) results in a branching B 0 such that |U (B 0 )| ≤ |U (B)|, hence in an
optimal branching covering x. Now, suppose that there exists some e ∈ E(G) such that e 6∈
∪NB− (E(G) ∪ {x}). Let v be an endpoint of e in G and consider the vertex E(v) ∪ {x}. Since e
is not covered in E(G) ∪ {x}, the arc (E(v) ∪ {x}, E(G) ∪ {x}) is not in B. The optimality of B
implies that (E(v) ∪ {x}, E(v) ∪ {x, y}) ∈ B. Now, replace the arc (E(v) ∪ {x}, E(v) ∪ {x, y}) with
the arc (E(v) ∪ {x}, E(G) ∪ {x}). This results in a branching B 0 such that e ∈ ∪NB−0 (E(G) ∪ {x}).
Moreover, |U (B 0 )| ≤ |U (B)| since removing the arc (E(v)∪{x}, E(v)∪{x, y}) makes x uncovered in
19

E(v) ∪ {x, y}, but adding the arc (E(v) ∪ {x}, E(G) ∪ {x}) makes element e covered in E(G) ∪ {x}.
Therefore, repeating the above procedure will eventually result in an optimal branching with respect
to which E(G) ∪ {x} is not irreducible, as claimed.
Define C = {v ∈ V (G) : (E(v)∪{x}, E(G)∪{x}) ∈ B}. The fact that every e ∈ E(G) is covered
in E(G)∪{x} implies that C is a vertex cover of G. Moreover, for every v ∈ C, element x is the only
uncovered element in vertex E(v) ∪ {x, y}, and for every v ∈ V (G) \ C, all elements in E(v) ∪ {x, y}
are covered. This implies that the total number of uncovered pairs by B equals 8|V (G)| + |C|,
implying |C| = β(M ) − 8|V (G)|, which proves the claimed inequality τ (G) ≤ β(M ) − 8|V (G)|.
This completes the proof of the claim.
We now complete the proof by showing that the above reduction is an L-reduction. Since G
is cubic, every vertex in a vertex cover of G covers exactly 3 edges, hence τ (G) ≥ |E(G)|
= |V (G)|
3
2 .
This implies that β(M ) = τ (G) + 8|V (G)| ≤ 17τ (G), hence the first condition in the definition
of L-reducibility is satisfied with a = 17. The second condition in the definition of L-reducibility
states that for every branching B of DM we can can compute in polynomial time a vertex cover C
of G such that |C| − τ (G) ≤ b · (|U (B)| − β(M )) for some b > 0. We claim that this can be achieved
with b = 1. Indeed, the second part of the proof of above claim shows how one can transform in
polynomial time any branching of DM into a vertex cover C of G such that |C| ≤ |U (B)| − 8|V (G)|.
Therefore, |C|−τ (G) ≤ |U (B)|−8|V (G)|−τ (G) = |U (B)|−β(M ). This shows that the vertex cover
problem in cubic graphs is L-reducible to the MinimumUcoveringBranching and completes the
proof.
Proposition 4.3. The MIB problem is APX-hard, even for instances of height 2. Consequently,
the MDCRS problem is APX-hard, even for instances of height 2.
Proof. We construct an L-reduction from the vertex cover problem in cubic graphs to the MIB
problem. Let G be a cubic graph. Let M be a binary matrix without duplicated columns such
that its column hypergraph is isomorphic to H, where H = (E, E ∪ {E(x) : x ∈ V }). See Fig. 7 for
an example construction, representing the containment digraph DM of the binary matrix derived
from the complete graph K4 .

G

DM

e1

{e2 , e4 , e5 }

{e3 , e5 , e6 }

e3

e2

e4

{e1 , e2 , e3 } {e1 , e4 , e6 }

e5
e6

e1

e2

e3

e4

e5

e6

Figure 7: An example construction of the L-reduction from the proof of Proposition 4.3.
To prove APX-hardness, we will show that ζ(M ) = |E(G)| + τ (G). This will suffice: since every
vertex in a vertex cover covers at most three edges, we have τ (G) ≥ |E(G)|/3, which will imply
that ζ(M ) ≤ 4τ (G). Similar arguments as those used at the end of the proof of Proposition 4.2
can then be used to infer that the given reduction is an L-reduction, thus completing the proof of
the theorem.
20

We split the proof of ζ(M ) = |E(G)| + τ (G) into two parts. First we show that ζ(M ) ≤
|E(G)| + τ (G). Let C be any minimum vertex cover of G. Define a set of arcs B of DM as
B = {(e, E(x)) : x ∈ e ∧ x ∈ V (G) \ C}. We first claim that B is branching of DM . Indeed, if this
was not the case, then there would exist an edge e ∈ E(G) and two distinct vertices x, y ∈ V (G)
such that (e, E(x)), (e, E(y)) ∈ B. This would imply that e ∈ E(x) and e ∈ E(y) and consequently
e = xy. By definition of B, none of x and y is in C, contradicting the fact that C is vertex cover.
Let x ∈ V (G). We claim that E(x) ∈ I(B) implies that x ∈ C. Suppose for a contradiction
that E(x) ∈ I(B) with x 6∈ C. Since x ∈ V (G) \ C, the definition of B implies that (e, E(x)) ∈ B,
for every e ∈ E(x), in particular, every element of E(x) is B-covered in E(x). Hence E(x) 6∈ I(B),
a contradiction. This shows that |I(B) ∩ {E(x) : x ∈ V (G)}| ≤ |C|. Together with I(B) =
(I(B) ∩ E(G)) ∪ (I(B) ∩ {E(x) : x ∈ V (G)}) this implies that |I(B)| ≤ |E(G)| + |C|. It follows
that ζ(M ) ≤ |I(B)| ≤ |E(G)| + |C| = |E(G)| + τ (G), as claimed.
Next we show that ζ(M ) ≥ |E(G)| + τ (G) by showing that τ (G) ≤ ζ(M ) − |E(G)|. Let B be a
branching of DM such that |I(B)| = ζ(M ). Define a set C with C = {x ∈ V (G) : E(x) ∈ I(B)}.
We claim that C is a vertex cover of G. Suppose that this does not hold, that is, that there exists
e ∈ E(G), such that e = xy and x, y ∈ V (G) \ C. Since x, y 6∈ C, it follows that E(x), E(y) 6∈ I(B).
By construction, every element of DM of the form E(z) is B-irreducible, unless B contains all the
three arcs leading to E(z). Consequently, B contains all the three arcs leading to E(x), and similarly
for E(y). In particular, we infer that (e, E(x)), (e, E(y)) ∈ B, contradicting the fact that B is a
branching in DM . Since I(B) is the disjoint union of I(B) ∩ E(G) and I(B) ∩ {E(x) : x ∈ V (G)}
and E(G) ⊆ I(B) we have |I(B)| = |I(B) ∩ E(G)| + |I(B) ∩ {E(x) : x ∈ V (G)}| = |E(G)| + |C|,
implying that τ (G) ≤ |C| = |I(B)| − |E(G)| = ζ(M ) − |E(G)|.
Theorem 4.1 (restated). The MUB and the MIB problems (and consequently the MCRS and the
MDCRS problems) are APX-hard, even for instances of height 2.
Proof. The theorem combines the statements of Propositions 4.2 and 4.3.

4.2

2-Approximating η and ζ via Laminar Set Families

The result of Theorem 4.1 raises the question whether the four problems (MCRS, MDRCS, MUB,
and MIB) admit constant factor approximations. In this section, we show that this is the case for
the MDRCS and the MIB problems. This will be achieved by proving a lower and an upper bound
for η(M ), which will together imply a simple 2-approximation algorithm.
The lower bound is based on a connection between conflict-free matrices and laminar set families
and an upper bound on the size of a laminar family in terms of the size of the ground set. Recall
that a hypergraph H is said to be laminar if every two hyperedges e1 , e2 ∈ E(H) satisfy e1 ∩ e2 = ∅,
e1 ⊆ e2 , or e2 ⊆ e1 . Recall also that the column hypergraph HM of a binary matrix M is the
hypergraph with vertex set V (HM ) = RM and hyperedge set E(HM ) = {suppM (c) : c ∈ CM }.
The following observation follows immediately from definitions.
Observation 4.4. A binary matrix M is conflict-free if and only if its column hypergraph HM is
laminar.
The following upper bound on the size of a laminar hypergraph is well known, see, e.g., [28].
Theorem 4.5. Every laminar hypergraph H satisfies |E(H)| ≤ 2|V (H)|.
21

Observation 4.4 and Theorem 4.5 imply the following.
Corollary 4.6. Every conflict-free binary matrix M with m rows satisfies k ≤ 2m, where k is the
number of distinct columns of M .
The claimed 2-approximation will be based on three lemmas.
Lemma 4.7. If M 0 is a conflict-free row split of M , then the number of distinct columns of M 0 is
at least as large as the number of distinct columns of M .
Proof. It suffices to prove that each two distinct columns of M are still distinct after performing
the row split. Let ci , cj be two distinct columns of M and c0i , c0j the corresponding columns of M 0 .
Then, without loss of generality, there exists a row r of M such that, Mr,i = 0 and Mr,j = 1. Let
R(r) be the set of split rows of r with respect to M 0 . Then for every r0 ∈ R(r) it holds Mr0 0 ,i = 0.
Since the rows in R(r) split r, there exists some r00 ∈ R(r) with Mr0 00 ,j = 1. This gives us Mr0 00 ,i = 0
and Mr0 00 ,j = 1, showing that columns c0i and c0j are distinct.
The following lemma shows that the value of η is invariant under deleting one of a pair of
identical columns.
Lemma 4.8. For every binary matrix M it holds that
γ(M ) = γ(Red(M )) ,

η(M ) = η(Red(M )) ,

β(M ) = β(Red(M )) ,

ζ(M ) = ζ(Red(M )) .

Proof. Since Red(M ) is submatrix of M , it follows that γ(Red(M )) ≤ γ(M ) and, similarly, that
η(Red(M )) ≤ η(M ). Conversely, since any conflict-free row split of Red(M ) can be transformed to
a conflict-free row split of M with the same number of rows (by duplicating some columns) it follows
that γ(M ) ≤ γ(Red(M )) and η(M ) ≤ η(Red(M )). We have shown that γ(M ) = γ(Red(M )) and
η(M ) = η(Red(M )). Moreover, since the containment digraphs DM and DRed(M ) are the same, we
infer that β(M ) = β(Red(M )) and ζ(M ) = ζ(Red(M )).
Corollary 4.6 and Lemmas 4.7 and 4.8 together with a simple row splitting strategy imply the
following.
Lemma 4.9. For every binary matrix M , we have k/2 ≤ η(M ) ≤ k, where k is the number of
distinct columns of M .
Proof. Let M ∈ {0, 1}m×n . First, we prove that k/2 ≤ η(M ) or, equivalently, that k ≤ 2η(M ).
0
Let M 0 ∈ {0, 1}m ×n be a row split of M with exactly η(M ) distinct rows. Let k 0 be the number
of distinct columns of M 0 . Let N ∈ {0, 1}η(M )×n be a new matrix obtained from M 0 by taking one
row from each set of identical rows. It is not difficult to see that N is conflict-free, with exactly
k 0 distinct columns. Further on, by Corollary 4.6 it holds k 0 ≤ 2η(M ) and hence by Lemma 4.7 it
holds k ≤ k 0 ≤ 2η(M ), as claimed.
It remains to show η(M ) ≤ k. By Lemma 4.8 it suffices to show that η(Red(M )) ≤ k. Let M 0
be the row split of Red(M ) obtained by splitting each row r with t ones into t rows, each with
exactly one non-zero entry. By construction, M 0 has exactly k columns and therefore at most k
distinct rows. It follows that η(Red(M )) ≤ k, as desired.
22

Now we have everything ready to state and prove the announced approximation result.
Theorem 4.10. There is a 2-approximation algorithm for the MDCRS (and consequently for the
MIB) problem running in time O(mnk) on a given matrix M ∈ {0, 1}m×n where k is the number
of distinct columns of M .
Proof. Let M be a binary matrix with m rows and n columns, exactly k of which are distinct. The
proof of Lemma 4.9 is constructive and leads to the following algorithm to compute a row split of
M with at most k distinct rows:
1. Compute Red(M ). (This can be done in time O(mn) using radix sort.)
2. Compute a row split M 0 of Red(M ) obtained by splitting each row r with t ones into t rows,
each with exactly one non-zero entry. (This can be done in time O(mk 2 ).)
3. Transform M 0 into a row split of M by an appropriate duplication of some columns. (This
can be done in time O(kmn), since M 0 has at most km rows and the constructed matrix will
have exactly n columns.)
Clearly, the algorithm produces a row split of M with at most k distinct rows. Since η(M ) ≥ k/2,
it follows that this is a 2-approximation. Moreover, using the fact that k ≤ n, we infer that the
total time complexity of the algorithm is O(mn + mk 2 + mnk) = O(mnk), as stated.
Note that Theorems 4.1 and 4.10 imply that the MDCRS and the MIB problems are APXcomplete.

4.3

Two Approximation Algorithms for Computing γ and β

While the question of whether the MCRS (and consequently the MUB) problem admits a constant
factor approximation algorithm on general instances remains open, we give in this section two partial
results in this direction. We show that the two problems admit constant factor approximation
algorithms on instances of bounded height or width.
Roughly speaking, the following theorem shows that for instances of bounded height any algorithm for the MCRS problem based on branchings is a constant factor approximation algorithm.
Theorem 4.11. Let M be a binary matrix and let B be an arbitrary branching of DM . Then, the
number of rows in the B-split of M is at most h(M )γ(M ).
Proof. Let h = h(M ) and let Bopt be a branching of DM with |U (Bopt )| = β(M ). Recall that the
number of rows in the B-split of M is |U (B)|. Since by Theorem 2.1 β(M ) = γ(M ), it suffices to
prove that |U (B)| ≤ hβ(M ). For (r, v) ∈ U (Bopt ), define the set Ω(r, v) with
+
Ω(r, v) = {(r, v 0 ) | v ∈ V, v 0 ∈ Bopt
(v)}.

We claim that
U (B) ⊆ ∪(r,v)∈U (Bopt ) Ω(r, v).

(1)

(In fact, since U (B) = U (∅) = {(r, v) : r ∈ v ∈ V }, equality holds in (1), but we will not need it
in the proof.) Let (r, v 0 ) ∈ U (B). We will show that there exists some (r, v) ∈ U (Bopt ) such that
+
(r, v 0 ) ∈ Ω(r, v). If (r, v 0 ) ∈ U (Bopt ), then (r, v 0 ) ∈ Ω(r, v 0 ), since v 0 ∈ Bopt
(v 0 ). If (r, v 0 ) 6∈ U (Bopt ),
23

it follows that r is covered in v 0 with respect to Bopt , and therefore, there exists some v 00 such
that (v 00 , v 0 ) ∈ Bopt , and r ∈ v 00 . If (r, v 00 ) ∈ U (Bopt ), then it is clear that (r, v 0 ) ∈ Ω(r, v 00 ). If
(r, v 00 ) 6∈ U (Bopt ), then we repeat the described procedure, which has to terminate after finitely
many steps. Therefore, there exists some (r, v) ∈ U (Bopt ) such that (r, v 0 ) ∈ Ω(r, v), as claimed.
This establishes inclusion (1).
Since the height of DM is h, it follows that the height of Bopt is at most h. Moreover, since
Bopt is a branching, it follows that |Ω(r, v)| ≤ h, for every (r, v) ∈ U (Bopt ). Combining this with
(1), we have
X
|Ω(r, v)| ≤ h|U (Bopt )| = hβ(M ).
|U (B)| ≤
(r,v)∈U (Bopt )

Since β(M ) = γ(M ), it follows that |U (B)| ≤ hγ(M ). This completes the proof.
Remark 4.12. Since in Theorem 4.11, there is no restriction on the branching B, an h(M )approximation to γ(M ) can be obtained simply by taking B = ∅ and returning the resulting row
split.
Remark 4.13. The following example shows that for every h > 1 and every  > 0, the algorithm
for the MCRS problem given by Theorem 3.6 is not an (h − )-approximation when restricted to
instances of height h.
Example 4.14. Fix a positive integer h ≥ 2. For all d ≥ 2, let Md be a binary matrix with dh−1
rows (indexed by 1, . . . , dh−1 ) and 1 + d + d2 + . . . + dh−1 columns. Entries of Md are defined
so that the supports of columns of Md are given by Aij = {(j − 1)di−1 + k : 1 ≤ k ≤ di−1 } for
all i ∈ {1, . . . , h} and all j ∈ {1, . . . , dh−i−1 } (see Figs. 8 and 9 for an example). The height
of Md is h. Matrix Md is conflict-free, therefore γ(Md ) = β(Md ) = dh−1 . It can be seen that
β` (Md ) = h · dh−1 − (h − 1) · dh−2 . Therefore, β` (Md )/β(Md ) = h − h−1
d . It follows that for every
 > 0, we have β` (Md )/β(Md ) > h −  for all large enough d.
A31 = {1, 2, 3, 4, 5, 6, 7, 8, 9}

A21 = {1, 2, 3}

A16 = {6}

A14 = {4}
A11 = {1}
A12

A23 = {7, 8, 9}

A22 = {4, 5, 6}

A19 = {9}

A15 = {5}
= {2}

A17 = {7}

A13 = {3}

A18 = {8}

Figure 8: The underlying tree of a branching B of DMd where Md is defined as in Example 4.14
for d = 3 and h = 3.

24

A91 = {1, 2, 3, 4, 5, 6, 7, 8, 9}

A21 = {1, 2, 3}

A22 = {4, 5, 6}

A23 = {7, 8, 9}

A11 = {1} A12 = {2} A13 = {3} A14 = {4} A15 = {5}A16 = {6} A17 = {7} A18 = {8} A19 = {9}

Figure 9: The underlying forest of an optimal linear branching B 0 given by Theorem 3.6. Note
that, if B denotes the branching from Fig. 8, then |U (B)| = γ(Md ) = 9 and |U (B 0 )| = 21.
For instances of bounded width, a constant factor approximation can be obtained by considering
any B-split resulting from a linear branching B of DM consisting of wdt(M ) paths. Note that such
a branching can be computed in polynomial time using Dilworth’s theorem (Theorem 3.1).
Theorem 4.15. Any algorithm that, given a binary matrix M , computes a linear branching B
of DM consisting of wdt(M ) paths and returns the corresponding B-split of M is a wdt(M )approximation algorithm for the MCRS problem.
Proof. Let M be a binary matrix and let w = wdt(M ). Let P = {C1 , . . . , Cw } be a chain partition
of DM (the existence of such a partition is guaranteed by Dilworth’s theorem) and let B be the
linear branching of DM corresponding to P . We will prove that |U (B)| ≤ w|RM |, where RM
denotes the set of rows of M . We claim that the number of elements in U (B) with fixed first
coordinate is at most w. For a row r of M , let N (r) = {v ∈ V (DM ) : (r, v) ∈ U (B)}. We claim
that |N (r) ∩ Ci | ≤ 1, for every i ∈ {1, . . . , w}. Suppose that v1 6= v2 and v1 , v2 ∈ N (r) ∩ Ci for
some i ∈ {1, . . . , w}. Since Ci is a chain, we may assume without loss of generality that v1 ⊂ v2 .
Moreover, since v1 , v2 are both in Ci it follows that there exists a path in B from v1 to v2 . Since
v1 ∈ N (r), it follows that r ∈ v1 , and since there exists a path in B from v1 to v2 , it follows
that r is covered in v2 with respect to B. This contradicts the assumption that v2 ∈ N (r). The
obtained contradiction shows that |N (r) ∩ Ci | ≤P
1, as claimed. Since |N (r) ∩ Ci | ≤ 1, and P is a
chain partition
of DM , it follows that |N (r)| = w
i=1 |N (r) ∩ Ci | ≤ w. It is now easy to see that
P
|U (B)| = r∈RM |N (r)| ≤ w|RM |.
Since matrix M is assumed to have no row whose all entries are 0, every row split of M contains
at least |RM | rows, that is, |RM | ≤ γ(M ). It follows that |U (B)| ≤ wγ(M ) and since the B-split
of M has exactly |U (B)| rows (by Lemma 2.2), the claimed approximation ratio follows.

5

Conclusion

In this paper, we revisited the minimum conflict-free row split problem and a variant of it. We
formulated the two problems as optimization problems on branchings in a derived directed acyclic
graph and, building on these formulations, obtained several new algorithmic and complexity insights
about the two problems, including APX-hardness results and approximation algorithms. Moreover,
we proved a min-max result on digraphs strengthening the classical Dilworth’s theorem and leading
25

to a new heuristic for the MCRS problem. In Figure 10 we summarize the relations between several
problems discussed in this paper, along with known complexity results and some applications. The
relations are described informally; for instance, we say that problem P1 reduces to problem P2 if a
polynomial-time algorithm for problem P2 can be used to develop a polynomial-time algorithm for
problem P1 .
APX-hard [Alimonti and Kann, 2000]
Vertex Cover in cubic graphs
reduces to
APX-hard (Theorem 4.1)
MinimumConflict-FreeRowSplit

application: cancer genomics
[Hajirasouliha and Raphael 2014]

equivalent problems
MinimumUncoveringBranching∗

APX-hard (Theorem 4.1)

restrict the solution space
MinimumUncoveringLinearBranching∗

polynomial (Theorem 3.6)

reduces to
MinimumPriceChainPartition∗
restrict the solution space

polynomial (Corollary 3.5)

reduces to

Minimum Weight Partition into B-chains

Weighted Coloring on cocomparability graphs
NP-hard – follows from hardness
on interval graphs [Escoffier et al., 2006]

APX-hard [Moonen and Spieksma, 2008]
application:
manufacturing (optimal pallet loading)
[Moonen and Spieksma, 2008]

applications (on interval graphs):
distributed computing in transportation networks,
dynamic storage allocation in computer processes
[Guan and Zhu, 1997]

Figure 10: Summary of relations between some problems discussed in this paper, along with known
complexity results and some applications. Problems marked with an asterisk (∗ ) are introduced in
this paper.
The main problem left open by our work is the determination of the exact (in)approximability
status of the MCRS problem. In particular, does the problem admit a constant factor approximation? Other possibilities for related future research include: i) the study of the approximability
properties of the closely related Minimum-Split-Row problem [18] (our preliminary investigations
show that the problem, while being APX-hard, admits a (2h(M ) − 1)-approximation); ii) a parameterized complexity study of the considered problems (along with identification of meaningful
26

parameterizations), and iii) a study of extensions of the model that could be relevant for the biological application, such as the case when the input binary matrix may contain errors or has
partially missing data. Finally, it would be interesting to find further applications of the polynomially solvable MinimumPriceChainPartition problem, as well as of the two branching problems,
MinimumUncoveringBranching and MinimumIrreducingBranching, introduced in this paper.

Acknowledgments
The authors are grateful to the two anonymous reviewers for helpful remarks. This work is supported in part by the Slovenian Research Agency under research programs I0-0035, P1-0285, and
research projects N1-0032, N1-0038, N1-0062, J1-6720, J1-7051, and by the Academy of Finland
under Grant No. 274977.

References
[1] A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph.
SIAM J. Comput., 1(2):131–137, 1972.
[2] P. Alimonti and V. Kann. Some APX-completeness results for cubic graphs. Theoret. Comput.
Sci., 237(1-2):123–134, 2000.
[3] J. Araujo, N. Nisse, and S. Pérennes. Weighted coloring in trees. SIAM J. Discrete Math.,
28(4):2029–2041, 2014.
[4] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi.
Complexity and Approximation. Springer-Verlag, Berlin, 1999.
[5] J. Cheriyan, T. Jordán, and R. Ravi. On 2-coverings and 2-packings of laminar families. In
Algorithms—ESA ’99 (Prague), volume 1643 of Lecture Notes in Comput. Sci., pages 510–520.
Springer, Berlin, 1999.
[6] D. de Werra, M. Demange, B. Escoffier, J. Monnot, and V. T. Paschos. Weighted coloring
on planar, bipartite and split graphs: complexity and approximation. Discrete Appl. Math.,
157(4):819–832, 2009.
[7] R. P. Dilworth. A decomposition theorem for partially ordered sets. Ann. of Math. (2),
51:161–166, 1950.
[8] B. Escoffier, J. Monnot, and V. T. Paschos. Weighted coloring: further complexity and approximability results. Inform. Process. Lett., 97(3):98–103, 2006.
[9] G. F. Estabrook, C. S. Johnson, Jr., and F. R. McMorris. An idealized concept of the true
cladistic character. Math. Biosci., 23:263–272, 1975.
[10] T. Feder and R. Motwani. Clique partitions, graph compression and speeding-up algorithms.
J. Comput. System Sci., 51(2):261–272, 1995.

27

[11] A. Frank. Finding minimum weighted generators of a path system. In Contemporary trends
in discrete mathematics (Štiřı́n Castle, 1997), volume 49 of DIMACS Ser. Discrete Math.
Theoret. Comput. Sci., pages 129–138. Amer. Math. Soc., Providence, RI, 1999.
[12] D. R. Fulkerson. Note on Dilworth’s decomposition theorem for partially ordered sets. Proc.
Amer. Math. Soc., 7:701–702, 1956.
[13] H. N. Gabow and K. S. Manu. Packing algorithms for arborescences (and spanning trees) in
capacitated graphs. Math. Programming, 82(1-2, Ser. B):83–109, 1998.
[14] M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Elsevier Science B.V.,
Amsterdam, second edition, 2004.
[15] D. J. Guan and X. Zhu. A coloring problem for weighted graphs. Inform. Process. Lett.,
61(2):77–81, 1997.
[16] D. Gusfield. Efficient algorithms for inferring evolutionary trees. Networks, 21(1):19–28, 1991.
[17] D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.
[18] I. Hajirasouliha and B. J. Raphael. Reconstructing mutational history in multiply sampled
tumors using perfect phylogeny mixtures. In Algorithms in Bioinformatics, volume 8701 of
Lecture Notes in Comput. Sci., pages 354–367. Springer, Heidelberg, 2014.
[19] A. Hujdurović, E. Husić, M. Milanič, R. Rizzi, and A. I. Tomescu. The minimum conflictfree row split problem revisited. In Graph-Theoretic Concepts in Computer Science - 43rd
International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised
Selected Papers, pages 303–315, 2017.
[20] A. Hujdurović, U. Kačar, M. Milanič, B. Ries, and A. I. Tomescu. Complexity and algorithms
for finding a perfect phylogeny from mixed tumor samples. IEEE/ACM Trans. Comput. Biol.
Bioinform., 2017. To appear. For an extended abstract, see Proc. WABI 2015, Lecture Notes
in Computer Science 9289 (2015) 80–92.
[21] O. H. Ibarra and S. Moran. Deterministic and probabilistic algorithms for maximum bipartite
matching via fast matrix multiplication. Inform. Process. Lett., 13(1):12–15, 1981.
[22] K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem.
Combinatorica, 21(1):39–60, 2001.
[23] F. Le Gall. Powers of tensors and fast matrix multiplication. In ISSAC 2014—Proceedings
of the 39th International Symposium on Symbolic and Algebraic Computation, pages 296–303.
ACM, New York, 2014.
[24] V. Mäkinen, D. Belazzougui, F. Cunial, and A. I. Tomescu. Genome-Scale Algorithm Design.
Cambridge University Press, 2015.
[25] L. S. Moonen and F. C. R. Spieksma. Partitioning a weighted partial order. J. Comb. Optim.,
15(4):342–356, 2008.

28

[26] S. C. Ntafos and S. L. Hakimi. On path cover problems in digraphs and applications to program
testing. IEEE Trans. Software Engrg., 5(5):520–529, 1979.
[27] M. Sakashita, K. Makino, and S. Fujishige. Minimizing a monotone concave function with
laminar covering constraints. Discrete Appl. Math., 156(11):2004–2019, 2008.
[28] A. Schrijver. Combinatorial Optimization. Polyhedra and Efficiency., volume 24 of Algorithms
and Combinatorics. Springer-Verlag, Berlin, 2003.
[29] H. Shum and L. E. Trotter, Jr. Cardinality-restricted chains and antichains in partially ordered
sets. Discrete Appl. Math., 65(1-3):421–439, 1996.

29

