arXiv:1506.03282v4 [] 16 Dec 2017

Discrete Mathematics and Theoretical Computer Science

DMTCS vol. 19:4, 2017, #3

Multidimensional Binary Vector Assignment
problem: standard, structural and above
guarantee parameterizations
Marin Bougeret1 Guillerme Duvillié1 Rodolphe Giroudeau1 Rémi
Watrigant2
1
2

LIRMM, Université Montpellier 2, France
Hong Kong Polytechnic University. Computing department

received 12th Nov. 2015, revised 5th Dec. 2016, accepted 3rd Oct. 2017.
In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem
(called B MVA). An input of this problem is defined by m disjoint sets V 1 , V 2 , . . . , V m , each composed of n binary
vectors of size p. An output is a set of n disjoint m-tuples of vectors, where each m-tuple is obtained by picking
one vector from each set V i . To each m-tuple we associate a p dimensional vector by applying the bit-wise AND
operation on the m vectors of the tuple. The objective is to minimize the total number of zeros in these n vectors.
B MVA can be seen as a variant of multidimensional matching where hyperedges are implicitly locally encoded via
labels attached to vertices, but was originally introduced in the context of integrated circuit manufacturing.
We provide for this problem FPT algorithms and negative results (ET H-based results, W2-hardness and a kernel
lower bound) according to several parameters: the standard parameter k (i.e. the total number of zeros), as well as
two parameters above some guaranteed values.
Keywords: parameterized complexity, kernel, above guarantee parameterization, AND-cross composition, multidimensional binary vector assignment, wafer-to-wafer integration, locally encoded multidimensional matching

1 Introduction
1.1 Definition of the problem
In this paper, we consider the parameterized version of the M ULTIDIMENSIONAL B INARY V ECTOR A S SIGNMENT problem ( B MVA). An input of this problem is described by m sets V 1 , V 2 , . . . , V m , each of
these sets containing n p-dimensional binary vectors. We note V i = {v1i , . . . , vni } for all i ∈ [m](i) , and
for all j ∈ [n] and r ∈ [p], we denote by vji [r] ∈ {0, 1} the rth component of vji .
In order to define the output of the problem, we need to introduce the notion of stack. A stack s =
s
(v1s , v2s , . . . , vm
) is an m-tuple of vectors such that ∀i ∈ [m], vis ∈ V i . The output of B MVA is a set S of
(i)

[m] stands for {1, . . . , m}.

ISSN 1365–8050

c 2017 by the author(s)

Distributed under a Creative Commons Attribution 4.0 International License

2

M. Bougeret, G. Duvillié, R. Giroudeau, R. Watrigant
V1

V2

V3

001101

110010

110110

110111

010101

010110

011101

110011

010011

111101

010101

001111

S
110010 vs1
000000 vs2

c(vs1 ) = 3

s1

c(vs2 ) = 6

s2

010001 vs3
000101 vs4

c(vs3 ) = 4

s3

c(vs4 ) = 4

s4

Figure 1: Example of B MVA instance with m = 3, n = 4, p = 6 and of a feasible solution S of cost c(S) = 17.

n stacks such that for all i, j ∈ [m] × [n], vji belongs to only one stack (in that case, the stacks are said
disjoint). An example of an instance together with a solution is depicted in Figure 1.
We are now ready to define the objective function. We define the operator ∧ that, given two pdimensional vectors u and v, computes the vector
w = (u[1] ∧ v[1], u[2] ∧ v[2], . . . , u[p] ∧ v[p]). We
V
associate to any stack s a unique vector vs = i∈[m] vis .
We define the
Pcost of a binary vector v as the number of zeros in it. More formally, if v is p-dimensional,
c(v) = p − r∈[p] v[r]. We extend this definition to a set of stacks S = {s1 , . . . , sn } as follows:
P
c(S) = j∈[n] c(vsj ). Finally, the objective of B MVA is to obtain a set S of n disjoint stacks while
minimizing c(S). In the decision version of the problem, we are given an integer k, and we ask whether
there exists a solution S of cost at most k. The problem is thus defined formally as follows:
Problem 1 M ULTIDIMENSIONAL B INARY V ECTOR A SSIGNMENT (B MVA)
Input:
m sets of n binary p-dimensional vectors, an integer k
Question:
Is there a set S of n disjoint stacks such that c(S) ≤ k ?
In order to avoid heavy notations throughout the paper, we will denote an instance of B MVA only by
I[m, n, p, k], the notations of the sets and vectors being implicitly given as previously.

1.2 Application and related work
B MVA can be seen as a variant of multidimensional matching where hyperedges are implicitly locally
encoded via labels attached to vertices. However, this kind of problem was originally introduced by Reda
et al. (2009) in the context of semiconductor industry as the “yield maximization problem in wafer-towafer 3-D integration technology”. In this context, each vector vji represents a wafer, which is seen
as a string of bad dies (0) and good dies (1). Integrating two wafers corresponds to superimposing the
two corresponding strings. In this operation, a position in the merged string is “good” when the two
corresponding dies are good, and is “bad” otherwise. The objective of Wafer-to-Wafer Integration is to
form n stacks, while maximizing their overall quality, or equivalently, minimizingP
the number of errors
(depending on the objective function). In the following, we will denote by max 1-B MVA the dual
version of B MVA where given the same input and ouput, the objective is to maximize np − c(S), the total
number of ones.
The results obtained so far concerning these problems mainly concern their approximability. It is proved
in Dokka et al. (2012) that when m = 3, B MVA is NP-hard but admits a 34 -approximation. We can also
mention Dokka et al. (2014) which provides a f (m)-approximation for general m, and an APX-hardness

Multidimensional Binary Vector Assignment problem

3

P
for m = 3. The main related article is Bougeret et al. (2016) where it is proved that max 1-B MVA has
no O(p1−ǫ ) nor O(m1−ǫ )-approximation for any ǫ > 0 unless P = NP (even when n = 2), but admits
a pc -approximation algorithm for any constant c ∈ N, and is FPT when parameterized by p (which also
holds for B MVA). Notice that one of the reductions provided
by Bougeret et al. (2016) is a parameterP
preserving
reduction
from
the
C
LIQUE problem to max
1B MVA, immediately proving W1-hardness
P
for max 1-B MVA when parameterized by the objective function. This is why our motivation in this
paper is to consider the parameterized complexity of B MVA. As we will see in the next section, we provide an analysis for several parameters related to this problem.
For formal definitions and detailed concepts on Fixed-Parameter Tractability, we refer to the monograph of Downey and Fellows (2013). Moreover, in order to define lower bounds on the running time of
parameterized algorithms, we will rely on the Exponential Time Hypothesis (ET H) of Impagliazzo et al.
(2001), stating that 3-S AT cannot be solved in O∗ (2o(n) ) where n is the number of variables (O∗ (.) hides
polynomial terms). For more results about lower bounds obtained under ET H, we refer the reader to the
survey of Lokshtanov et al. (2013).

1.3 Parameterizations
One of the main purposes of Fixed-Parameter Tractability is to obtain efficient algorithms when the considered parameter is small in practice. When dealing with the decision version of an optimization problem,
the most natural parameter is perhaps the value of the desired solution (e.g. k for B MVA). Such a parameter is often referred to in the literature as the “standard parameter” of the problem. In some cases, this
parameter might not be very interesting, either because it usually takes high values in practice, or because
FPT algorithms with respect to this parameterization are trivial to find. When this happens, it is possible
to obtain more interesting results by subtracting to the objective function a known lower bound of it. For
instance, if one can prove that any solution of a given minimization problem is of cost at least B, then one
can ask for a solution of cost B + c and parameterize by c. This idea, called “above guarantee parameterization” was introduced by Mahajan et al. (2009) and first applied to M AX S AT and M AX C UT problems.
It then became a fruitful line of research with similar results obtained for many other problems (among
others, see Cygan et al. (2013); Gutin et al. (2007); Gutin and Yeo (2012); Mahajan et al. (2009)).
In this paper, we analyze the parameterized complexity of B MVA using three types of parameters. The
first one is the standard parameter k: the number of zeros to minimize in the optimization version of the
problem. Then, three natural structural parameters: m, the number of sets of the input, n, the number of
vectors in each set, and p, the size of each vector. The last two parameters are above guarantee parameters.
As we said previously, we already proved in Bougeret et al. (2016) that B MVA is FPT parameterized
by p. As we will notice in Lemma 2 that we can obtain p ≤ k after a polynomial pre-processing step,
this implies that B MVA is also FPT with its standard parameter. Our idea here is to use this previous
inequality in order to obtain smaller parameters. Thus, we define our first above guarantee parameter
ζp = k − p.
Finally, in order to define our last parameter, we first need to describe the corresponding lower bound
B, that will represent the maximum, over all sets of vectors, of
Pthe total number of zeros for each set.
More formally, we define B = maxi∈[m] c(V i ) where c(V i ) = nj=1 c(vji ). Since we perform a bit-wise
AND over each m-tuple, it is easily seen that any solution will be of cost at least B. Thus, we define our
last parameter ζB = k − B.

4

M. Bougeret, G. Duvillié, R. Giroudeau, R. Watrigant

1.4 Our results
In the next section, we present some pre-processing rules leading to a kernel of size O(k 2 m), and prove
that even when m = 3 we cannot improve it to pO(1) unless NP ⊆ coNP/poly (remember that B MVA
is known to be FPT when parameterized by p). Section 3 is mainly focused on results associated with
parameter ζB : we prove that B MVA can be solved in O∗ (4ζB log(n) ), while it is W2-hard when parameterized by ζB only, and cannot be solved in O∗ (2o(ζB ) log(n) ) nor in O∗ (2ζB o(log(n)) ) assuming ET H. In
Section 4, we focus on the parameterization by ζp : we show that when n = 2, the problem can be solved
in single exponential time with this parameter, but is not in XP for any fixed n ≥ 3 (unless P = NP).
The reduction we use also shows that for fixed n ∈ N, the problem cannot be solved in 2o(k) (and thus
in 2o(ζB ) ) unless ET H fails, which matches the upper bound obtained in Section 3. A summary of our
results is depicted in the following table.
Positive results
O(k 2 m) kernel (Thm. 1)

Negative results
no pO(1) kernel for m = 3 unless NP ⊆ coNP/poly (Thm. 3)
W2-hard for ζB only (Thm. 5)
no 2o(ζB ) log(n) nor 2ζB o(log(n)) under ET H (Thm. 6)
no 2o(k) for fixed n under ET H (Thm. 8)

O∗ (4ζB log(n) ) algorithm
(Thm. 4)
O∗ (dζp ) algorithm
for n = 2 (Thm. 7)

NP-hard for ζp = 0 and fixed n ≥ 3 (Thm. 8)

This article is the complete version of Bougeret et al. (2015) where some proofs were omitted due to
space limitations.

2 First remarks and kernels
Let us start with two simple lemmas allowing us to bound the size of the input. Notice first that it is
not always safe to create a 1-stack (i.e. a stack with ones on every component) when possible. Indeed,
in instance V 1 = {h111i, h101i, h011i}, V 2 = {h111i, h101i, h110i}, V 3 = {h111i, h011i, h110i},
depicted in Figure 2, no optimal solution creates a 1-stack. However, as we will see in Lemma 1, creating
1-stacks becomes safe if n > k.
V1

V2

V3

Opt

111

111

111

101

vs1

c(vs1 ) = 1

011

vs2

c(vs2 ) = 1

110

vs3

c(vs3 ) = 1

101
011

101
110

011
110

Figure 2: Example of B MVA instance such that no optimal solution creates a 1-stack.

Lemma 1. There exists a polynomial algorithm which, given any instance
I[m, n, p, k] of B MVA, either detects that I is a negative instance, or outputs an equivalent instance
I ′ [m, n′ , p, k] such that n′ ≤ k.

Multidimensional Binary Vector Assignment problem

5

Proof: Let I[m, n, p, k] be an instance of B MVA, and suppose that n > k. Let us write a polynomial preprocessing rule that either detects that I is a no instance, or compute an equivalent instance I ′′ [m, n′′ , p, k]
with n′′ = n − 1.
Notice first that there exists at least a 1-vector in every set V i . If not, I is a no instance as any solution
would be of cost at least n > k. It is now safe to create a 1-stack, obtaining a remaining instance I ′′
with n′′ = n − 1. Indeed, if I is a yes instance, then there must exist at least one 1-stack in the solution
(otherwise the cost would be at least n > k), and thus the remaining instance is also a yes instance. As
the converse is trivially true, the rule is safe. Applying it at most n − k times finally leads to the desired
upper bound.
Lemma 2. There exists a polynomial algorithm which, given any instance
I[m, n, p, k] of B MVA, either detects that I is a negative instance, or outputs an equivalent instance
I ′ [m, n, p′ , k] such that p′ ≤ k.
Proof: Let I[m, n, p, k] be an instance of the problem, and suppose that there exists r ∈ [p] such that for
all (i, j) ∈ [m] × [n] we have vji [r] = 1. In other words, the rth component of all vectors of all sets is
a 1. In this case, it is clear that all vectors of any set of n stacks obtained from I will also contain a 1
at the rth component. Hence, we can modify I[m, n, p, k] into I ′ [m, n, p′ , k] with p′ < p by dropping
all such components for all vectors. It is clear that this rule is safe since the cost of any solution remains
unchanged, and it can be applied in polynomial time. After applying this rule, for all r ∈ [p′ ] there exists
(i, j) ∈ [m] × [n] such that vji [r] = 0. This immediately implies that the cost of any solution is at least p′ ,
and thus if p′ > k the algorithm detected a no instance.
Given the two previous lemmas, we can suppose from now on that for any instance of B MVA we have
n ≤ k and p ≤ k. This immediately implies a polynomial kernel parameterized by k and m.
Theorem 1.

B MVA

admits a kernel with O(k 2 m) bits.

Let us now turn to the main result of this section. To complement Theorem 1, we show that even
when m = 3, we cannot obtain a polynomial kernel with the smaller parameter p under some classical
complexity assumptions (notice however that the existence of a polynomial kernel in k only is still open
when m is not fixed). Notice also that as B MVA was known to be FPT when parameterized by p, proved
in Bougeret et al. (2016), it was a natural question to ask for a polynomial kernel.
In order to establish kernel lower bounds, we use the concept of AND-cross-composition of Bodlaender
et al. (2014), together with the recently proved AND-conjecture of Drucker (2015). In the following, a
parameterized problem is a subset of Σ∗ × N, where Σ∗ is the set of words over some finite alphabet Σ.
Definition 1 (Polynomial equivalence relation according to Bodlaender et al. (2014)). An equivalence
relation R on Σ∗ is called a polynomial equivalence relation if the two following conditions hold:
• There is an algorithm that given two strings x, y ∈ Σ∗ , decides whether x and y belong to the same
equivalence class in (|x| + |y|)O(1) time.
• For any finite set S ⊆ Σ∗ , the equivalence relation R partitions the elements of S into at most
(maxx∈S |x|)O(1) classes.
Definition 2 (AND-cross-composition according to Bodlaender et al. (2014)). Let L ⊆ Σ∗ be a set and
let Q ⊆ Σ∗ × N be a parameterized problem. We say that L AND-cross-composes into Q if there

6

M. Bougeret, G. Duvillié, R. Giroudeau, R. Watrigant

is a polynomial equivalence relation R and an algorithm which, given t strings belonging
Pt to the same
equivalence class of R, computes an instance (x∗ , k ∗ ) ∈ Σ∗ × N in time polynomial in i=1 |xi | such
that:
• (x∗ , k ∗ ) ∈ Q ⇔ xi ∈ L for all i ∈ {1, . . . , t}
• k ∗ is bounded by a polynomial in maxti=1 |xi | + log t
Theorem 2 (Drucker (2015)). If some set L ⊆ Σ∗ is NP-hard and L AND-cross-composes into a parameterized problem Q, then there is no polynomial kernel for Q unless NP ⊆ coNP/poly.
Theorem 3. Even for m = 3, B MVA parameterized by p does not admit a polynomial kernel unless
NP ⊆ coNP/poly.
Proof: The proof is an AND-cross-composition inspired by the NP-hardness reduction for B MVA provided by Dokka et al. (2012). More precisely, we cross-compose from a sequence of instances of 3DIMENSIONAL PERFECT MATCHING . According to Definition 2 and Theorem 2, this will imply the
desired result. 3- DIMENSIONAL PERFECT MATCHING is formally defined as follows:
Problem 2 3-Dimensional Perfect Matching
Three sets X, Y and Z of size n, a set of hyperedges S ⊆ X × Y × Z
Input:
Question:

Does there exist a subset S ′ ⊆ S such that:
• for all e, e′ ∈ S ′ with e = (x, y, z) and e′ = (x′ , y ′ , z ′ ), we have x 6= x′ ,
y 6= y ′ and z 6= z ′ (that is, S ′ is a matching)
• |S ′ | = n (that is, S ′ is perfect)

Let (X1 , Y1 , Z1 , S1 ), . . . , (Xt , Yt , Zt , St ) be a sequence of t equivalent instances of 3-DPM, with respect to the following polynomial equivalence relation: (X, Y, Z, S) and (X ′ , Y ′ , Z ′ , S ′ ) are equivalent
if |X| = |X ′ | (and thus |Y | = |Y ′ | = |Z| = |Z ′ | = |X|), and |S| = |S ′ |. In the following we denote
by n the cardinality of the sets Xi (and equivalently the sets Yi and Zi ), and by m the cardinality of the
sets Si . Moreover, for all i ∈ {1, . . . , t} we define Xi = {xi,1 , . . . , xi,n }, Yi = {yi,1 , . . . , yi,n }, Zi =
{zi,1 , . . . , zi,n }, and Si = {si,1 , . . . , si,m }. We also assume that t = 2q for some q ∈ N (if it is not the
case, we add a sufficiently number of dummy yes-instances).
∗
In the following we construct three sets (X ∗ , Y ∗ , Z ∗ ) of nt vectors each: X ∗ = {x∗i,j }j=1,...,n
i=1,...,t , Y =
j=1,...,n
j=1,...,n
∗
∗
{yi,j
}i=1,...,t and Z ∗ = {zi,j
}i=1,...,t , where each vector is composed of p∗ = m + 2mq components.
Let us first describe the first m components of each vector. For all i ∈ {1, . . . , t}, j ∈ {1, . . . , n} and
k ∈ {1, . . . , m} we set:

1 if the hyperedge si,k contains xi,j
x∗i,j [k] =
0 otherwise

1 if the hyperedge si,k contains yi,j
∗
yi,j
[k] =
0 otherwise

Multidimensional Binary Vector Assignment problem

1 if the hyperedge si,k contains zi,j
∗
zi,j
[k] =
0 otherwise

7

∗
}j=1,...,n
Then, for all i ∈ {1, . . . , t}, we append two vectors bi and b¯i to all vectors {x∗i,j }j=1,...,n , {yi,j
∗
and {zi,j }j=1,...,n . The vector bi is composed of mq coordinates, and is defined as the binary representation of the integer i, where each bit is duplicated m times. Finally, b¯i is obtained by taking the complement
of bi (i.e. replacing all zeros by ones, and conversely) as depicted in Figure 3. It is now clear that each
∗
∗
vector x∗i,j (resp. yi,j
, zi,j
) is composed of p∗ = m + 2mq coordinates. Thus, the parameter of the input
instance is a polynomial in n, m and log t whereas the total size of the instance is a polynomial in the size
of the sequence of inputs, as required in cross-compositions. It now remains to prove that (X ∗ , Y ∗ , Z ∗ )
contains an assignment of cost k ∗ = nt(mq + m − 1) if and only if for all i ∈ {1, . . . , t}, Si contains a
perfect matching Si′ .

• Suppose that for all i ∈ {1, . . . , t} we have a perfect matching Si′ ⊆ Si . W.l.o.g. suppose that
Si′ = {si,1 , . . . , si,n }. Then, for each j ∈ {1, . . . , n}, we have si,j = (xi,j1 , yi,j2 , zi,j3 ) for some
∗
∗
. It is easy to see that the cost of this
and zi,j
j1 , j2 , j3 ∈ {1, . . . , n}. We assign x∗i,j1 with yi,j
3
2
triple is m − 1 + mq. Indeed, they all have a one at the j th coordinate, corresponding to the j th
hyperedge of Si (and this is the only shared one, since we can suppose that all hyperedges are
pairwise distinct), and they all contain the same vectors bi and b¯i . Summing up for all instances, we
get the desired solution value.
• Conversely, first remark that in any assignment, the cost of every triple (x∗i1 ,j1 , yi∗2 ,j2 , zi∗3 ,j3 ) is
at least m − 1 + mq, and let us prove that this bound is tight when (1) all elements are chosen
within the same instance, i.e. i1 = i2 = i3 = i, and (2) this triple corresponds to an element
of Si , i.e. (xi,j1 , yi,j2 , zi,j3 ) ∈ Si . Indeed, suppose first that i1 6= i2 . Then, since the binary
representation of i1 and i2 differs on at least one bit, it is clear that the resulting vector is of cost at
least m(q + 1) > mq + m − 1. Now if i1 = i2 = i3 = i, then the result is straightforward, since at
most one hyperedge of Si can contain x∗i1 ,j1 , yi∗2 ,j2 and zi∗3 ,j3 . Finally, using the same arguments as
previously, we can easily deduce a perfect matching Si′ ⊆ Si for each i ∈ {1, . . . , t}, and the result
follows.

3 Parameterizing according to ζB
In this section, we present an FPT algorithm when parameterized by ζB and n (recall that both ζB and
n are smaller parameters than the standard one k, since k = B + ζB and n ≤ k in any reduced instance).
Notice first that it is easy to get an O∗ (2ζB (log(n)+log(p)) ) algorithm. Indeed, by considering a set i ∈ [m]
where c(V i ) = B, and guessing the positions of the ζB new zeros (among np possible positions) that
will appear in an optimal solution, we can actually guess in O∗ ((np)ζB ) the vectors {vs∗j } of an optimal
solution, and it remains to check in polynomial time that every V j can be “matched” to {vs∗j }. Now we
show how to get rid of the log(p) term in the exponent.
Theorem 4.

B MVA

can be solved in O∗ (4ζB log(n) ).

8

M. Bougeret, G. Duvillié, R. Giroudeau, R. Watrigant

X1
x1,1

Y1
y1,1

Z1
z1,1

X∗

Y∗

Z∗

1100 00000000 11111111

1000 00000000 11111111

0010 00000000 11111111

x1,2

y1,2

z1,2

0010 00000000 11111111

0100 00000000 11111111

0100 00000000 11111111

x1,3

y1,3

z1,3

0001 00000000 11111111

0011 00000000 11111111

1001 00000000 11111111

X2
x2,1

Y2
y2,1

Z2
z2,1

1000 01010101 10101010

1000 01010101 10101010

1001 01010101 10101010

x2,2

y2,2

z2,2

0100 01010101 10101010

0101 01010101 10101010

0100 01010101 10101010

x2,3

y2,3

z2,3

0011 01010101 10101010

0010 01010101 10101010

0010 01010101 10101010

X3
x3,1

Y3
y3,1

Z3
z3,1

1000 10101010 01010101

1100 10101010 01010101

1100 10101010 01010101

x3,2

y3,2

z3,2

0100 10101010 01010101

0010 10101010 01010101

0010 10101010 01010101

x3,3

y3,3

z3,3

0011 10101010 01010101

0001 10101010 01010101

0001 10101010 01010101

X4
x4,1

Y4
y4,1

Z4
z4,1

1000 11111111 00000000

0100 11111111 00000000

0100 11111111 00000000

x4,2

y4,2

z4,2

0110 11111111 00000000

1010 11111111 00000000

1010 11111111 00000000

x4,3

y4,3

z4,3

0001 11111111 00000000

0001 11111111 00000000

0001 11111111 00000000

bi

bi

bi

bi

bi

bi

Figure 3: Example of Cross Composition construction from four equivalent instances of 3-Dimensional
Perfect
Matching
(X1 , Y1 , Z1 , {(x1,1 , y1,1 , z1,3 ), (x1,1 , y1,2 , z1,2 ), (x1,2 , y1,3 , z1,3 ), (x1,3 , y1,3 , z1,3 )}),
(X2 , Y2 , Z2 , {(x2,1 , y2,1 , z2,1 ), (x2,2 , y2,2 , z2,2 ), (x2,3 , y2,3 , z2,3 ), (x2,3 , y2,2 , z2,1 )}),
(X3 , Y3 , Z3 , {(x3,1 , y3,1 , z3,1 ), (x3,2 , y3,1 , z3,1 ), (x3,3 , y3,2 , z3,2 ), (x3,3 , y3,3 , z3,3 )}),
(X4 , Y4 , Z4 , {(x4,1 , y4,2 , z4,2 ), (x4,2 , y4,1 , z4,1 ), (x4,2 , y4,2 , z4,2 ), (x4,3 , y4,3 , z4,3 )}) into an instance of bMVA
with m = 3, n = 12 and p = 20.

Multidimensional Binary Vector Assignment problem

9

Proof: Let I[m, n, p, k] be an instance of our problem and, w.l.o.g., suppose that V 1 is a set whose
number of zeros reaches the upper bound B, i.e. c(V 1 ) = B. The algorithm consists in constructing a
solution by finding an optimal assignment between V 1 and V 2 , . . . , V m , successively.
We first claim that we can decide in polynomial time whether there is an assignment between V 1 and
2
V which does not create any additional zero.
To that end, we create a bipartite graph G with bipartization (A, B), A = {a1 , . . . , an }, B = {b1 , . . . ,
bn }, and link aj1 and bj2 for all (j1 , j2 ) ∈ [n] × [n] iff assigning vector vj11 from V 1 and vector vj22 from
V 2 does not create any additional zero in V 1 (vj11 ∧ vj22 = vj11 ).
If a perfect maching can be found in G, then we can safely delete the set V 2 and continue. In order to
avoid heavy notations, we consider this first step as a polynomial pre-processing, and we re-label V i into
V i−1 for all i ∈ {3, . . . , m} (and m is implicitly decreased by one).
In the following, we suppose that the previous pre-processing step cannot apply (i.e. there is no perfect
matching in G). Intuitively, in this case any assignment (including an optimal one) between V 1 and V 2
must lead to at least one additional zero in V 1 . In this case, we perform a branching to guess one couple
of vectors from V 1 × V 2 which will induce such an additional zero. More formally, we branch on every
couple (j1 , j2 ) ∈ [n] × [n], and create a new instance as a copy of I in which vj11 is replaced by vj11 ∧ vj22 .
This operation increases c(V 1 ) by at least one, and thus B by at least one as well. If we denote by I ′ this
new instance, we can check that a solution of cost at most k for I ′ will immediately imply a solution of
cost at most k for I, as I ′ is constructed from I by adding some zeros. The converse is also true as one
assignment we enumerate corresponds to one from an optimal solution.
As the value of B in this branching increases by at least one while we still look for a solution of cost k,
this implies that this branching will be applied at most ζB times. Summing up, we have one polynomial
pre-processing and one branching of size n2 which will be applied at most ζB times. The total running
time of this algorithm is thus bounded by O∗ (4ζB log(n) ).
Despite its simplicity, we now show that, when considering each parameter (n and ζB ) separately, this
algorithm is the best we can hope for (whereas the existence of an O∗ (2k ) algorithm is still open). Indeed,
we first show in Theorem 6 that the linear dependence in ζB and log(n) in the exponent is necessary
(unless ETH fails), and also that we cannot hope for an FPT algorithm parameterized by ζB only unless
FPT = W2 (Theorem 5). Finally, as we will see in the next section (Theorem 8), this result is matched
by a 2o(ζB ) lower bound when n ∈ N is fixed. We now present a reduction from the H ITTING S ET
problem which produces an instance of B MVA.
Problem 3 Hitting Set
m subsets R1 , ..., Rm of [n], and an integer k
Input:
Question:

Is there a set R of k elements of [n] such that R ∩ Ri 6= ∅ for any i ∈ [m]?

Lemma 3. There is a polynomial reduction from H ITTING S ET to B MVA that given an instance composed of m subsets of [n] and an integer k, constructs an instance of B MVA I[m′ , n′ , p′ , k ′ ] such that
n′ = n and ζB = k.
Proof: Let R1 , ..., Rm be subsets of [n], and k ∈ N. We construct m sets V 1 , ..., V m of n vectors each,
where, for all i ∈ [m] we have V i = {v1i , ..., vni }, each vector being composed of n components. For all

10

M. Bougeret, G. Duvillié, R. Giroudeau, R. Watrigant

R1
2

7

3

R2

1

4

6

5
R3

R4

V1

V2

V3

V4

V5

0111111

0111111

0000000

0000000

0000000

1011111

0000000

1011111

0000000

0000000

0000000

1101111

0000000

0000000

0000000

0000000

1110111

1110111

0000000

0000000

0000000

1111011

1111011

1111011

0000000

0000000

0000000

0000000

1111101

0000000

1111110

0000000

0000000

1111110

1111111

0111011

Figure 4: Example of reduction from an instance of Hitting Set consisting of four subsets of [n = 7] : R1 =
{1, 2, 7} , R2 = {1, 3, 4, 5} , R3 = {2, 4, 5} , R4 = {5, 6, 7}, and an integer k = 2, to an instance of B MVA with
m′ = 5, n′ = n, p = n.

i ∈ [m] and all j ∈ [n], if j ∈ Ri , then the vector vji is composed of ones everywhere except at the j th
component. If j ∈
/ Ri , then vji is a 0-vector (i.e. a vector with zero in every component). We also add a
∗
set V composed of (n − 1) 0-vectors and one 1-vector as depicted in Figure 4.
For this constructed instance, it is clear that B = n(n − 1) because of the set V ∗ . In other words, any
assignment will lead to a solution with (n − 1) 0-vectors, and thus with at least n(n − 1) zeros. We will
actually show that this instance has a solution with n(n − 1) + k zeros if and only if R1 , ..., Rm has a
hitting set of size k. By the foregoing, we only need to focus on the only vector of each set which is
assigned to the 1-vector of V ∗ .
⇒ Let J ⊆ [n] be a hitting set of size k. By the definition of a hitting set, for all i ∈ [m], there exists
ji ∈ J ∩ Ri . Thus, for all i ∈ [m], we select the vector vjii from the set V i to be assigned to the 1vector of V ∗ . By construction, this vector has only one zero at the jith component, which implies that the
Vm
conjunction of all such vectors i=1 vjji will have a 1 everywhere except at the components corresponding
to J. We thus have the desired number of zeros in our solution.
⇐ Conversely, for each i ∈ [m], let ji ∈ [n] be the vector from V i which is assigned to the 1-vector of
V ∗ . Since the resulting conjunction of all these vectors has only k zeros, vjii cannot be a 0-vector, and
we thus have ji ∈ Ri . Using the same arguments as previously, {uji }i∈[m] corresponds to a hitting set of
R1 , ..., Rm of size k.
As we seen previously, B = n(n − 1) for the obtained instance, k ′ = n(n − 1) + k, (which implies
ζB = k), and the size of all sets is n, as desired.
As we can see, the reduction is parameter-preserving for ζB . From the W2-hardness of H ITTING S ET
provided by Downey and Fellows (2013), we have the following:
Theorem 5.

B MVA

is W2-hard when parameterized by ζB .

As said previously, we also use this reduction to show the following result:
Theorem 6.

B MVA

cannot be solved in O∗ (2o(ζB ) log(n) ) nor O∗ (2ζB o(log(n)) ), unless ETH fails.

Proof: To show this, we use a the previous hardness result, but using a constrained version of the H ITTING
S ET problem obtained by Lokshtanov et al. (2011), where the element set is [k] × [k] and can thus be seen
as a table with k rows and k columns:

Multidimensional Binary Vector Assignment problem

11

Problem 4 k × k Hitting Set
An integer k, and R1 , ..., Rt ⊆ [k] × [k]
Input:
Question:

Is there a set R containing exactly one element from each row such that R ∩ Ri 6= ∅
for any i ∈ [t]?

Lokshtanov et al. (2011) show that assuming ET H this problem cannot be solved in 2o(k log(k)) nO(1)
(whereas a simple brute force solves it in O∗ (2k log(k) )). Notice that we can modify the question of this
problem by dropping the constraint that S contains at least one element from each row. Indeed, let us add
to the instance a set of k sets {R1′ , . . . , Rk′ }, where Ri′ contains all elements of row i for i ∈ [k]. Now,
finding a (classical) hitting set of size k on this modified instance is equivalent to finding a solution of size
k for the original instance of k × k-H ITTING S ET. Moreover, it is easy to check that a 2o(k log(k)) nO(1)
algorithm for this relaxed problem would also contradict ET H. To summarize, we know that unless
ET H fails, there is no 2o(k log(k)) nO(1) algorithm for the classical H ITTING S ET problem, even when the
ground set has size k 2 . This allows us to perform the reduction of Lemma 3 on these special instances,
leading to an instance I[m′ , n′ , p′ , k ′ ] with associated parameter ζB such that ζB = k and n′ = k 2 .
Suppose now that there exists an algorithm for B MVA running in 2o(ζB ) log(n) (k + m + n + p)O(1) . Using
2
the reduction above, we would be able to solve the instance of k × k-H ITTING S ET in 2o(k) log(k ) nO(1) ,
and thus in 2o(k log(k)) nO(1) , which would violate ET H. A similar idea also rules out any algorithm
running in 2ζB o(log(n)) under ET H.

4 Parameterizing according to ζp
We now consider the problem parameterized by ζp = k − p (recall that p ≤ k). Notice that one motivation
of this parameterization is the previous reduction of Lemma 3 from H ITTING S ET. Indeed, when applied
for n = 2, it reduces an instance of V ERTEX C OVER to an instance of B MVA with k = p + ζp where
ζp is equal to the size of the vertex cover. Our intuition is confirmed by the following result: we show
that when parameterized by ζp , the problem is indeed FPT when n = 2 (Theorem 7). We complement
this by showing that for any n ≥ 3, it becomes NP-hard when ζp = 0 (Theorem 8), and is thus even
not in XP. The reduction we use even proves that for any fixed n ≥ 3, the problem cannot be solved in
2o(k) (and thus in 2o(ζB ) ) unless ET H fails, while the algorithm of Theorem 4 runs in O∗ (2O(ζB ) ). In
the following, n-B MVA denotes the problem B MVA where the size of all sets is fixed to some constant
n ∈ N.

4.1 Positive result for n = 2
In this subsection, we prove that 2-B MVA is FPT parameterized by ζp . To do so, we reduce to the O DD
C YCLE T RANSVERSAL problem (OCT for short). In this problem, given a graph G = (V, E) and an
integer c ∈ N, the objective is to decide whether there exists a partition (X, S1 , S2 ) of V with |X| ≤ c
such that S1 and S2 are independent sets.
We first introduce a generalized version of OCT, called BIP -OCT. In this problem, we are given a set of
vertices V , an integer c, and a set of m pairs (A1 , B1 ), ..., (Am , Bm ) with Ai , Bi ⊆ V for all i ∈ [m] and
Ai ∩ Bi = ∅. Informally, each pair (Ai , Bi ) can be seen as a complete bipartite subgraph. The output of
BIP -OCT is described by a partition (X, S1 , S2 ) of V such that for any i ∈ [m], either (Ai \ X ⊆ S1 and

12

M. Bougeret, G. Duvillié, R. Giroudeau, R. Watrigant

Bi \ X ⊆ S2 ) or (Ai \ X ⊆ S2 and Bi \ X ⊆ S1 ). The question is whether there exists such a partition
with |X| ≤ c. As we can see, if all Ai and Bi are singletons (and thus form edges), then BIP -OCT
corresponds to OCT. Notice that in the following, the considered parameter of OCT and BIP -OCT will
always be the standard parameter, i.e. c. We first show that there is a linear parameter-preserving reduction
from 2-B MVA parameterized by ζp to BIP -OCT, and then that there is also a linear parameter-preserving
transformation from BIP -OCT to OCT.
Lemma 4. There is a linear parameter-preserving reduction from 2-B MVA parameterized by ζp to BIP OCT.
Proof: Let I[m, 2, p, p + ζp ] be an instance of 2-B MVA (i.e. in which every set contains only two
vectors), and let us construct an instance I ′ of BIP -OCT, such that I has a solution of cost p + ζp iff I ′
has a solution of size ζp . Notice first that we can suppose that for any i ∈ [m] and any r ∈ [p], we cannot
have both v1i [r] = 0 and v2i [r] = 0 as otherwise any stack s from any solution would have vs [r] = 0, and
thus we could safely remove such a component r from the instance (and decrease k and p by one).
Let the vertex set of I ′ be [p]. Then, for all i ∈ [m], let us define Ai = {r|v1i [r] = 0}, and Bi =
{r|v2i [r] = 0} as depicted in Figure 5. By the foregoing, and as required in an instance of bip-OCT, we
have Ai ∩ Bi = ∅. Let us prove that I has a solution of cost p + ζp iff I ′ has a solution (X, S1 , S2 ) with
|X| ≤ ζp .
⇒ Let S = {s1 , s2 } be a solution of I of cost p + ζp . Let X = {r|vs1 [r] = vs2 [r] = 0}, S1 =
{r|vs1 [r] = 0 and vs2 [r] = 1}, and S2 = {r|vs1 [r] = 1 and vs2 [r] = 0}. Notice that (X, S1 , S2 ) forms
a partition of [p] (as we cannot have a r0 with vs1 [r0 ] = vs2 [r0 ] = 1, as this would imply that all the nm
vectors have v[r0 ] = 1, and such cooordinates have been removed from the instance in Lemma 2), and
|X| = ζp . It remains to prove that (X, S1 , S2 ) is a feasible solution of I ′ . Let i ∈ [m]. Without loss of
generality, let us suppose that v1i has been added to s1 and v2i has been added to s2 . Let r ∈ Ai \ X. Since
/ X, we have vs2 [r] = 1. Thus, r ∈ S1 , which
r ∈ Ai , we have v1i [r] = 0, and thus vs1 [r] = 0. Since r ∈
proves Ai \ X ⊆ S1 . Similarly, we can prove that Bi \ X ⊆ S2 .
⇐ Let (X, S1 , S2 ) be a solution of I ′ with |X| ≤ ζp . Let s1 be such that vs1 [r] = 0 iff r ∈ X or
r ∈ S1 , and let s2 be such that vs2 [r] = 0 iff r ∈ X or r ∈ S2 . It remains to prove that the solution
S = {s1 , s2 } is feasible, which immediately implies that its cost is p + ζp . Let i ∈ [m]. Without loss of
generality, let us suppose that Ai \ X ⊆ S1 and Bi \ X ⊆ S2 . We now claim that v1i can be assigned to
s1 and v2i can be assigned to s2 without creating any new zero. To do so, let us show that for all r ∈ [p],
we have v1i [r] = 0 =⇒ vs1 [p] = 0 (resp. v2i [r] = 0 =⇒ vs2 [p] = 0). Indeed, let r ∈ [p] such that
v1i [r] = 0. Then by construction, it means that r ∈ Ai . Thus, by definition of the solution (X, S1 , S2 ),
it means that either r ∈ X or r ∈ S1 , which implies vs1 [r] = 0 as desired. Similar arguments show that
v2i [r] = 0 =⇒ vs2 [p] = 0 for all r ∈ [p].
Lemma 5. There is a linear parameterized reduction from BIP -OCT to OCT.
Proof: Let I = (V, {Ai , Bi }i∈[m] , c) be an instance of BIP -OCT. Let us construct a graph G′ = (V ′ , E ′ )
which contains an odd cycle transversal of size c if and only
S if I has a solution of size c for BIP -OCT.
Observe first that we cannot simply set V ′ = V and E ′ = i∈[m],a∈Ai ,b∈Bi {a, b}. Indeed, if for example
A1 = {2, . . . , n}, B1 = {1}, A2 = {2, . . . , n2 } and B2 = { n2 + 1, . . . , n}, defining G′ as above would
lead to an odd cycle transversal of size one, as removing only vertex {1} makes the graph bipartite with
bipartization (A2 , B2 ). However, this solution is not feasible for BIP -OCT as A1 \X = A1 , and A1 6⊆ A2

13

Multidimensional Binary Vector Assignment problem
A1
V1

V2

V3

S

110110111

001111011

111010111

110100110

3

A2

5
011101111

110101110

111111000

6

A3
4

9

8

001001000
B1

1

7

B3

2
B2

Figure 5: Example of reduction from an instance of 2-B MVA, with n = 2, m = 3, p = 9, admitting a solution
of cost p + 2, to an instance of BIP -OCT, with |V | = p, A1 = {3, 6} , B1 = {1, 5} , A2 = {2, 3, 7} , B2 =
{3, 5, 9} , A3 = {4, 6} , B3 = {7, 8, 9}, admitting the partition ({5, 9} , {3, 4, 6} , {1, 2, 7, 8}) as solution of cost 2.

and A1 6⊆ B2 . Intuitively, we have to prevent solutions of G′ from splitting sets Ai \ X (and Bi \ X)
between the two parts of the bipartization. To do so, we will construct G′ as described above, and then
we "augment" each bipartite graph by adding c + 1 new vertices on each side. More formally, we start by
setting V ′ = VSas said before, and for all i ∈ [m], we create two sets of c + 1 new vertices A′i , Bi′ . We
then set E ′ = i∈[m],a∈Ai ∪A′ ,b∈Bi ∪B ′ {a, b}.
i

i

Let us now prove that I contains a solution of size c for BIP -OCT if and only if G′ contains an odd
cycle transversal of size c.
⇒ Let (X, S1 , S2 ) be an optimal solution of I. We define a partial solution X ′ , S1′ , S2′ of G′ by setting
′
X = X and Sl′ = Sl for l ∈ {1, 2} (the solution is partial in the sense that it remains to assign vertices
of A′i ∪ Bi′ , for all i ∈ [m]). Let i ∈ [m]. If Ai \ X = ∅ and Bi \ X = ∅, then we add (arbitrarily)
A′i to S1′ and Bi′ to S2′ . Otherwise, if Ai \ X 6= ∅ and is added to Sl , we add A′i to Sl′ and Bi′ to Sl′′
with l, l′ ∈ {1, 2}, l′ 6= l, and if Bi \ X 6= ∅ and is added to Sl , we add Bi′ to Sl′ and A′i to Sl′′ with
l, l′ ∈ {1, 2}, l′ 6= l.
This new solution has the same size (|X ′ | = |X|) and we claim that it is an odd cycle transversal of G′ .
Indeed, let us check that any edge {u, v} ∈ E ′ such that {u, v} ∩ X ′ = ∅ is not entirely contained in a
Sl′ . If {u, v} is an edge of a complete bipartite of I, i.e. if there exists i such that u ∈ Ai and v ∈ Bi ,
then by definition of the solution (X, S1 , S2 ) it is straightforward that u and v are not both in S1′ nor in
S2′ . Otherwise, if {u, v} is adjacent to one or two of the new vertices, let i be such that u ∈ A′i . If v ∈ Bi′ ,
then the solution is valid as A′i and Bi′ are never added to the same set Sl′ , l ∈ {1, 2}. Otherwise, we
necessarily have v ∈ Bi . Let l ∈ {1, 2} be such that Bi \ X (which is not empty) has been added to Sl′ .
In this case Ai (and thus u) has been added to Sl′′ , with l′ 6= l.
⇐ Let (X ′ , S1′ , S2′ ) be an optimal solution of G′ . For any i ∈ [m], let Ãi = (Ai ∪ A′i ) \ X ′ and
B̃i = (Bi ∪ Bi′ ) \ X ′ . A first observation is that Ãi 6= ∅ and B̃i 6= ∅ as |Ai ∪ A′i | = |Bi ∪ Bi′ | > c and
|X ′ | ≤ c. A second observation is that for any u and v ∈ Ãi , u and v are in the same set Sl′ for some
l ∈ {1, 2}. Indeed, suppose by contradiction that u ∈ S1′ and v ∈ S2′ . As B̃i 6= ∅, there exists b ∈ B̃i and

14

M. Bougeret, G. Duvillié, R. Giroudeau, R. Watrigant

l ∈ {1, 2} such that b ∈ Sl′ . As all the edges of the complete bipartite subgraph on (Ai ∪ A′i , Bi ∪ Bi′ )
belong to E ′ , we have {u, b} ∈ E ′ and {v, b} ∈ E ′ , and thus Sl′ contains both endpoints of an edge of
E ′ , which is a contradiction. In the same way, we can prove that for any i ∈ [m], and any u and v ∈ B̃i ,
u and v are in the same set Sl′ for some l ∈ {1, 2}.
Thus, according to the two previous observations, for any i ∈ [m] we can define λÃi ∈ {1, 2} and
λB̃i ∈ {1, 2} such that Ãi ⊆ Sλ′ ˜ and B̃i ⊆ Sλ′ , with λÃi 6= λB̃i .
Ai

B̃i

Let us now define X = X ′ ∩ V , S1 = S1′ ∩ V , and S2 = S2′ ∩ V , and check that this is a valid solution
of I. Let i ∈ [m]. Observe first that Ai \ X ⊆ Ãi , and thus either Ai \ X = ∅, or Ai \ X ⊆ SλA˜ . As the
i
same fact also holds for Bi \ X, and as λÃi 6= λB̃i , the constraint (Ai \ X ⊆ S1 and Bi \ X ⊆ S2 ) or
(Ai \ X ⊆ S2 and Bi \ X ⊆ S1 ) is respected, and the solution is feasible, which concludes the proof.
As O DD C YCLE T RANSVERSAL can be solved in O∗ (2.3146c), proved by Lokshtanov et al. (2014),
and since our parameters are exactly preserved in our two reductions, we obtain the following result:
Theorem 7. 2-B MVA can be solved in O∗ (dζp ) where d ≤ 2.3146 is such that OCT can be solved in
O∗ (dc ).

4.2 Negative results for n ≥ 3
We now complement the previous result by proving that the problem is intractable with respect to the
parameter ζp for larger values of n.
Theorem 8. For any fixed n ≥ 3, n-B MVA is not in XP when parameterized by ζp (unless P = NP),
and cannot be solved in 2o(k) (unless ET H fails).
Proof: Let χ ≥ 3. We present a reduction from χ-C OLORING. Given a graph G = (V, E), this problem
consists to ask for a mapping f : V −→ [χ] such that for all {u, v} ∈ E we have f (u) 6= f (v). Let
E = {e1 , ..., emG } and V = [nG ]. Let us construct an instance I of n-B MVA with n = χ, p = nG ,
m = mG and such that G admits a χ-coloring iff I has a solution of cost p (i.e. ζp = 0). To each edge
ei = {u, v} ∈ E, i ∈ [mG ], we associate a set V i with |V i | = χ, where:
• v1i represents the vertex u, that is v1i [u] = 0 and v1i [r] = 1 for any r ∈ [nG ], r 6= u,
• v2i represents the vertex v, that is v2i [v] = 0 and v2i [r] = 1 for any r ∈ [nG ], r 6= v,
• for all j ∈ {3, . . . , χ}, vji is a 1-vector, i.e. it has a 1 at every component.
An example of this construcion is depicted in Figure 6. Let us now prove that G admits a χ-coloring iff I
has a solution of cost p = nG .
⇒ Let Sj ⊆ V , jS∈ [χ] be the χ color classes (notice that the Sj are pairwise disjoint, some of them
may be empty, and j∈[χ] Sj = V ). To each Sj we associate a stack sj such that vsj [r] = 0 iff r ∈ Sj .
It remains to prove that the solution S = {s1 , . . . , sχ } is feasible, as its cost is exactly p by construction.
Let us consider a set V i where v1i (resp. v2i ) represents a vertex u (resp. v). As {u, v} is an edge of G,
we know that u and v have two different colors, i.e. that u ∈ Sj and v ∈ Sj ′ , for some j, j ′ ∈ [χ] with
j 6= j ′ . Thus, we can add v1i to stack sj , v2i to stack sj ′ , and the χ − 2 other vji (j ≥ 3) in an arbitrary
way. Since the only 0 in v1i (resp. v2i ) is at the uth (resp. v th ) component, we have v1i ∧ vsj = vsj (resp.
v2i ∧ vsj′ = vsj′ ), which proves that S is feasible.

15

Multidimensional Binary Vector Assignment problem

4
1

3

5

2

V 1,2

V 1,3

V 1,4

V 2,3

V 3,4

V 2,5

V 4,5

S

01111

01111

01111

10111

11011

10111

11101

10101

10111

11011

11101

11011

11101

11110

11110

01110

11111

11111

11111

11111

11111

11111

11111

11011

Figure 6: Example of reduction from a positive instance of χ-C OLORING, with χ = 3, V = [5], E =
{{1, 2} , {1, 3} , {1, 4} , {2, 3} , {3, 4} , {2, 5} , {4, 5}}, to an instance of B MVA with m = |E| = 6, n = χ =
3, p = |V | = 5 admitting a solution of cost p.

⇐ Let S = {s
S1χ, . . . , sχ } be the stacks of an optimal solution. For j ∈ [χ], let Sj = {r ∈ [p]|vsj [r] =
0}. Notice that j=1 Sj = V , and as I is of cost p, all the Sj are pairwise disjoints and form a partition
of V . Moreover, as for any i ∈ [m], v1i and v2i have been assigned to different stacks, the corresponding vertices have been assigned to different colors, and thus each Sj induces an independent set, which
completes the reduction.
It is known, thanks to Impagliazzo et al. (2001) that there is no 2o(|V |) algorithm for deciding whether
a graph G = (V, E) admits a χ-C OLORING, for any χ ≥ 3 (under ET H). As we can see, the value of
the optimal solution for n-B MVA in the previous reduction equals the number of vertices in the instance
of χ-C OLORING, which proves that n-B MVA cannot be solved in 2o(k) for any n ≥ 3.
Finally, remark that as for the parameterization by p, one could ask if B MVA is FPT when parameterized by the first lower bound B. However, we can see in the previous reduction that we obtain a graph
with B = 2, and thus the problem is even not in XP unless P = NP.

5 Conclusion
In this article, we presented some negative and positive results for a multidimensional binary vector assignment problem in the framework of parameterized complexity. Notice that neither lower bounds of
Theorem 6 nor Theorem 8 are able to rule out an algorithm running in O∗ (2k ) (when n is part of the
input), hence the existence of such an algorithm seems a challenging open problem. Another interesting
question concerns the improvement of the O(k 2 m) kernel of Theorem 1 by getting rid of the parameter
m: does B MVA admit a polynomial kernel when parameterized by k only?

References
Bodlaender, H. L., Jansen, B. M., and Kratsch, S. (2014).
composition. SIAM J. Discrete Math., 28(1):277–305.

Kernelization lower bounds by cross-

Bougeret, M., Boudet, V., Dokka, T., Duvillié, G., and Giroudeau, R. (2016). On the complexity of
wafer-to-wafer integration. Discrete Optimization, 22:255–269.
Bougeret, M., Duvillié, G., Giroudeau, R., and Watrigant, R. (2015). Multidimensional binary vector
assignment problem: Standard, structural and above guarantee parameterizations. In Fundamentals of

16

M. Bougeret, G. Duvillié, R. Giroudeau, R. Watrigant

Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015,
Proceedings, pages 189–201.
Cygan, M., Pilipczuk, M., Pilipczuk, M., and Wojtaszczyk, J. O. (2013). On multiway cut parameterized
above lower bounds. ACM Transactions on Computation Theory (TOCT), 5(1):3:1–3:11.
Dokka, T., Bougeret, M., Boudet, V., Giroudeau, R., and Spieksma, F. C. (2012). Approximation algorithms for the wafer to wafer integration problem. In Approximation and Online Algorithms - 10th
International Workshop, WAOA 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected
Papers, pages 286–297.
Dokka, T., Crama, Y., and Spieksma, F. C. (2014). Multi-dimensional vector assignment problems. Discrete Optimization, 14:111–125.
Downey, R. G. and Fellows, M. R. (2013). Fundamentals of Parameterized Complexity. Texts in Computer
Science. Springer.
Drucker, A. (2015). New limits to classical and quantum instance compression. SIAM J. Comput.,
44(5):1443–1479.
Gutin, G., Rafiey, A., Szeider, S., and Yeo, A. (2007). The linear arrangement problem parameterized
above guaranteed value. Theory of Computing Systems, 41(3):521–538.
Gutin, G. and Yeo, A. (2012). The multivariate algorithmic revolution and beyond. chapter Constraint Satisfaction Problems Parameterized Above or Below Tight Bounds: A Survey, pages 257–286. SpringerVerlag, Berlin, Heidelberg.
Impagliazzo, R., Paturi, R., and Zane, F. (2001). Which problems have strongly exponential complexity?
Journal of Computer and System Sciences, 63:512–530.
Lokshtanov, D., Marx, D., and Saurabh, S. (2011). Slightly superexponential parameterized problems.
In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA
2011, San Francisco, California, USA, January 23-25, 2011, pages 760–776.
Lokshtanov, D., Marx, D., and Saurabh, S. (2013). Lower bounds based on the exponential time hypothesis. Bulletin of EATCS, 3(105).
Lokshtanov, D., N.S., N., and Ramanujan, M. (2014). Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms (TALG), 11(2):15.
Mahajan, M., Raman, V., and Sikdar, S. (2009). Parameterizing above or below guaranteed values. Journal of Computer and System Sciences, 75(2):137–153.
Reda, S., Smith, G., and Smith, L. (2009). Maximizing the functional yield of wafer-to-wafer 3-d integration. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 17(9):1357–1362.

