The Minimum Feasible Tileset problem∗
Yann Disser1 , Stefan Kratsch2 , and Manuel Sorge3

arXiv:1409.8524v2 [cs.CC] 25 Oct 2017

1

Institut für Mathematik, Graduate School CE, TU Darmstadt, Germany,
disser@mathematik.tu-darmstadt.de
2
Institut für Informatik, Humboldt-Universität zu Berlin, Berlin, Germany,
kratsch@informatik.hu-berlin.de
3
Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Germany and Department of
Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer Sheva, Israel,
sorge@post.bgu.ac.il

October 26, 2017

Abstract
We introduce and study the Minimum Feasible Tileset problem: Given a set of
symbols and subsets of these symbols (scenarios), ﬁnd a smallest possible number of pairs
of symbols (tiles) such that each scenario can be formed by selecting at most one symbol
from each tile. We show that this problem is APX-hard and that it is NP-hard even if each
scenario contains at most three symbols. Our main result is a 4/3-approximation algorithm
for the general case. In addition, we show that the Minimum Feasible Tileset problem is
ﬁxed-parameter tractable both when parameterized with the number of scenarios and with
the number of symbols.

1

Introduction

Consider the general assignment problem where several devices (e.g., workers, robots, microchips, . . . ) each can be used in one of k functions/modes at a time (e.g., employing diﬀerent
skills, tools, instruction sets, . . . ). Given a set of scenarios, the goal is to assign k diﬀerent
functions to each device, such that, for each scenario, all functions requested by the scenario
are available simultaneously. In this paper, we initiate the study of this problem for k = 2 and
the case that each function is requested at most once by each scenario. Formally, we study
the following problem (we use “tile” instead of “device” to intuitively capture the fact that a
device/tile has two modes/sides).
Minimum Feasible Tileset
Input: A universe of symbols F , scenarios S ⊆ 2F \ {F }.
Problem: Find a minimum-size tileset T that is feasible for all scenarios in S.
∗

An extended abstract of this article appeared at the 12th Workshop on Approximation and Online Algorithms,
Wroclaw, September 2014 [9]. In comparison, apart from full proof details, the present article additionally
contains examples and an APX-hardness proof. The authors gratefully acknowledge support by the Alexander von
Humboldt-Foundation (Yann Disser), the ‘Excellence Initiative’ of the German Federal and State Governments
and the Graduate School CE at TU Darmstadt (Yann Disser), the German Research Foundation (DFG), projects
KR 4286/1 (Stefan Kratsch) and NI 369/12 (Manuel Sorge), the Israel Science Foundation, grant no. 551145/14
(Manuel Sorge), and the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework
Programme (FP7/2007-2013) under REA grant agreement number 631163.11 (Manuel Sorge).

1

In the above, a tile is a two-element subset of F and we refer to (multi-)sets of tiles as tilesets.
A tileset T is feasible for scenario S if we can produce all symbols in S by taking at most one
symbol from each tile in T . Formally, a tileset T is feasible for a scenario S ⊂ F if there is a
mapping φ : T → F , such that φ(T ) ∈ T for all T ∈ T , and S ⊆ φ[T ] := {φ(T ) | T ∈ T }. By
deﬁnition, no scenario contains all symbols of F . Note that such a scenario would require |F |
tiles, making the problem trivial. Similarly, we may assume that all symbols in F appear in
at least one scenario, otherwise we can simply remove each symbol that does not occur in any
scenario. Finally, the requirement that tiles contain no less than two symbols can be met by
arbitrarily assigning a second symbol to all tiles of cardinality one.
Example 1. Let us illustrate the problem with two instances of Minimum Feasible Tileset:
If our set of symbols is F = {A, B, C, 1, 2, 3} and our set S of scenarios consists of {A, B, 1, 2},
{A, C, 1, 3}, and {B, C, 2, 3}, then it is not hard to check that a feasible tileset is
A B 1 2
B , C , 2, 3.
Herein, each tile is represented by two adjoined boxes which correspond to the two modes in
which we can use the tile. Clearly, the feasible tileset above is also of minimum size since each
scenario requires at least four tiles.
If we
have n ∈ N, F = {1, . . . , 3n}, and our scenarios are all size-2 subsets of F , that is,
F
S = 2 , then a feasible tileset with 2n tiles is

3i − 2 3i − 1
3n − 2 3n − 1
3i − 1 ,
3i , . . . , 3n − 1 ,
3n .

To see that the above tileset is feasible for F2 , pick any integer a ∈ {1, . . . , 3n}. If a 6= 3i − 1
for each i ∈ {1, . . . , n}, then, whichever tile we pick to produce a, each other integer from 1 to
3n is available on some other tile. If a = 3i − 1 for some i ∈ {1, . . . , n}, then, to produce a
and any other integer b ∈ {1, . . . , 3n} \ {a}, we can pick an arbitrary tile for b and a will be
available on another tile. Hence, we can produce any scenario containing two distinct integers
from 1 to 3n by
 two distinct tiles. It will become clear later, that each feasible tileset for the
instance (F, F2 ) of Minimum Feasible Tileset contains at least 2n tiles.
1 2
2, 3,

4 5
5 , 6 , ...,

Apart from practical motivations, Minimum Feasible Tileset is appealing from a structural point of view. In this work we exhibit equivalent deﬁnitions for the problem which are
interesting in their own right. At ﬁrst glance, Minimum Feasible Tileset is a covering problem since we must cover all scenarios using tiles that can each cover one of the tile’s two symbols
in each scenario. It turns out that the problem can also be phrased as a packing/partitioning
problem, but with an objective function diﬀerent from the classical one in terms of number
of packed objects or sets (see Section 3). In addition, having tiles be symbol sets of size two
suggests a graph interpretation where we are asked to ﬁnd a minimum set of edges such that
for each scenario there is an orientation where each vertex has indegree at least one. For our
presentation however, we favor the tileset formulation, since it most naturally generalizes to
the original assignment problem with tiles of larger sizes and scenarios which contain multiple
copies of the same symbols. Also, the Minimum Feasible Tileset interpretation appears
suitable for studying the eﬀect of parameters, such as the number of symbols/scenarios, on the
complexity.

2

Results and Outline. We analyze the structure of the graph that has the tiles of a minimum cardinality tileset as its edges, and show that this graph is always (wlog.) a forest. In
fact, only the component structure of this forest matters: We may replace trees by arbitrary
trees spanning the same components without aﬀecting the feasibility of the corresponding tileset (Section 2). This lets us view Minimum Feasible Tileset as a partitioning problem, which
in turn allows us to prove NP-completeness even when scenarios have size at most three and
lets us show APX-hardness for the general case (Section 3). As our main result, we complement
the hardness with a 4/3-approximation algorithm (for scenarios of arbitrary sizes) inspired by
the component structure of the optimum solution (Section 4). We show that the problem is
ﬁxed-parameter tractable with respect to the number of scenarios (Section 5) and the number of
symbols (Section 6), respectively. We also observe that, when each scenario has size at most d, a
polynomial-time compression of an arbitrary instance to O(|F |d ) bits is possible without loosing
the information about the size of the optimum solution and such a compression to O(|F |d−ǫ )
bits is unlikely (Section 6). Finally, we provide a preliminary result on the relevant variant of
Minimum Feasible Tileset where the scenarios are multisets rather than sets and show that
also this case is ﬁxed-parameter tractable with respect to the number of symbols (Section 6).
Related Work. The problem most closely related to Minimum Feasible Tileset is arguably Set Packing, as 3-Set Packing appears as a subproblem in our approximation algorithm and also as the source problem for our NP-hardness reduction (in the form of Maximum Three-Dimensional Matching). Set Packing has been extensively studied for both
approximability and parameterized complexity (see, e.g., [1, 6, 27] and [7, 21] for some recent
results). The main diﬀerence between the two problems is that Set Packing is a maximization
problem whereas Minimum Feasible Tileset seeks to minimize the size of a feasible tileset
— a measure that is only indirectly related to the number of sets (scenarios). In particular,
Set Packing becomes trivial for a bounded number of sets, whereas for Minimum Feasible
Tileset we get a nontrivial polynomial-time algorithm via integer linear programming (see
Section 5).
As alluded to above, the Minimum Feasible Tileset problem can equivalently be seen as
designing an edge-minimal graph on the set of symbols such that, for each scenario, the edges
(tiles) can be oriented in such a way that all symbols in the scenario have indegree at least one.
The question whether a given graph admits an orientation with certain properties has been
studied in various settings. For example, Biedl et al. [2] proposed an approximation algorithm
for ﬁnding a balanced acyclic orientation. Another natural constraint on an orientation that
has been studied is to prescribe degrees for each vertex [10, 13, 17].
More abstractly, we are looking for a graph on the set of symbols that fulﬁlls a certain
constraint for each scenario. The case where the subgraph induced by each scenario has to be
connected is well-studied [3, 4, 11, 16, 18, 28]. In particular, it is NP-hard to ﬁnd the minimum
number of edges needed [11] and to decide whether a planar solution [3, 18] or a solution of
treewidth at most three [16] exists.
Preliminaries. SFor some positive integer
S ℓ ∈ N, we denote [ℓ] := {1, 2, . . . , ℓ}. For a set
family S we use S as a shorthand for S∈S S. Apart from standard Landau notation for
running times, we also use the O∗ notation, which disregards factors that are polynomial in
the input size. We use standard graph notation, see the book by Diestel [24], for example. For
the relevant notions from parameterized complexity and approximation complexity we refer to
textbooks [12, 23, 25] and refs. [5, 26], respectively.

3

2

Graph structure of tilesets

The tiles in a tileset T over a universe of symbols F can be viewed as the edges of the undirected
(multi-) graph G(T ) := (F, T ). In this section, we establish that there always exist optimal
tilesets with a simple graph structure. This is made formal in the following lemma which will
be useful in later sections.
Lemma 1. Let F be a universe of symbols,
F , and T a tileset
 S a family of scenarios over
F
′
′
feasible for S. There is a tileset T ⊆ 2 feasible for S such that |T | ≤ |T | and G(T ′ ) is a
forest.
Note that each connected component of G(T ′ ) has size at least two because each symbol
occurs in at least one scenario and hence is incident with at least one edge.
In the proof of Lemma 1 it is convenient to think of feasibility of T via orientations of the
graph G(T ). Let us say that an orientation of G(T ) is feasible for the scenario S if each vertex
in S has indegree at least one. It is easy to see that deciding whether T is feasible for some
scenario S ⊂ F is equivalent to deciding whether there is a feasible orientation of the edges of
G(T ) for S. We obtain the following lemma.
Lemma 2. For every tileset T and scenario S over a universe of symbols F the following are
equivalent.
(i) T is feasible for S,
(ii) there is a feasible orientation of G(T ) for S,
(iii) for every connected component C of G(T ), there is a feasible orientation of G(T ) for S ∩C,
(iv) for every connected component C of G(T ), tileset T is feasible for S ∩ C.
Proof. Note that it suﬃces to prove the equivalence of the ﬁrst three statements, since equivalence of (i) and (ii) implies equivalence of (iii) and (iv).
(i) ⇒ (ii): Assume that T is feasible for S and let φ : T → F be the corresponding mapping
with φ(T ) ∈ T for all T ∈ T , and S ⊆ φ[T ]. We obtain an orientation of G(T ) by orienting
each edge T ∈ T towards φ(T ). Since S ⊆ φ[T ], each symbol in S has indegree at least one and
we have a feasible orientation of G(T ) for S.
(ii) ⇒ (iii): Clearly, a feasible orientation of G(T ) for S is, in particular, a feasible orientation
for S ∩ C for every connected component C of G(T ).
(iii) ⇒ (i): Let C1 , . . . , Ck denote the connected components of G(T ) and assume that
S there
~
~
are feasible orientations G1 , . . . , Gk for S ∩ C1 , . . . , S ∩ Ck , respectively. Since S ⊆ i Ci , we
~ of G(T ) for S as G
~ 1 [C1 ] ⊎ · · · ⊎ G
~ k [Ck ]. We deﬁne the mapping
obtain a feasible orientation G
φ : T → F by setting φ(T ) = s for each T ∈ T , where s is the symbol towards which the edge
~ By deﬁnition, φ(T ) ∈ T for all T ∈ T , and, since G
~ is feasible for S, we
T is oriented in G.
have S ⊆ φ[T ]. The existence of the mapping φ hence proves that T is feasible for S.
Using the notion of feasible orientations we now observe that connected components in G(T )
yield feasibility for each of their strict subsets.
Lemma 3. Let T be a tileset, C a connected component of G(T ) and C ′ ( C. Then, T is
feasible for C ′ .
Proof. The proof is by induction over the size of C ′ . If C ′ contains a single symbol, that
is, C ′ = {s}, then we obtain a feasible orientation by orienting an arbitrary edge towards s;
such an edge exists because C ′ is part of the (larger) connected component C. Consider the
case |C ′ | > 1. First assume that G(T )[C ′ ] contains no edges, i.e., C ′ is an independent set.
Then, there is an edge in G(T )[C] for each symbol s ∈ C ′ , connecting s to C \ C ′ . A feasible
4

orientation for C ′ can simply be obtained by orienting these edges towards C ′ . Now, assume
there is an edge {s, s′ } in G(T )[C ′ ] and consider the graph G′ obtained by contracting {s, s′ }.
By induction, there is a feasible orientation of G′ for C ′′ , where C ′′ is obtained from C ′ by
identifying s and s′ . Hence, there is an orientation of G(T ) such that all vertices in C ′ except
one of {s, s′ } have indegree at least one. We orient the edge {s, s′ } towards the vertex of smaller
indegree to obtain the desired feasible orientation of G(T ).
We are ready for a proof of Lemma 1. Intuitively, we observe that cycle components in G(T )
yield feasibility for any of their subsets and hence are a safe replacement for every component
with a large number of edges. Then we show how to break cycle components into trees.
Proof of Lemma 1. We replace connected components in G(T ), maintaining feasibility of T and
without increasing the cardinality of T .
Sk Let C1 , . . . , Ck be the connected′ components of G(T ) that contain a cycle, and let C =
i=1 Ci . We obtain a new tileset T by replacing the edges in G(T )[C] with a cycle on C. (If
|C| = 1, we introduce a self-loop and if |C| = 2, we introduce two parallel edges.) Since each
component Ci , i ∈ [k], originally contained at least |Ci | edges, and we only introduced |C| new
edges, the cardinality of T ′ is not larger than the cardinality of T . We observe that T ′ is still
feasible. Consider an arbitrary scenario S ∈ S. Clearly, if S ∩ C = ∅, then T ′ is feasible for S.
Hence, assume S ∩ C 6= ∅. By Lemma 2 there is a feasible orientation of G(T ) for S \ C. This
implies that there is still a feasible orientation of G(T ′ ) for S \ C. By Lemma 2 it suﬃces to
prove that there is a feasible orientation of G(T ′ ) for S ∩ C. Indeed, since G(T ′ )[C] is a cycle,
orienting the edges in one direction along the cycle yields a feasible orientation for any subset
of C, and, in particular, for S ∩ C. Hence, T ′ is still feasible for every S ∈ S.
By deﬁnition, every connected component C ′ of G(T ) outside of C is a tree. Hence, the
connected components of G(T ′ ) are trees, with the exception of at most one component C that
is a cycle. We now modify C in order to obtain our ﬁnal feasible tileset T ′′ with the desired
structure.
First, consider the case that C is the only connected component of G(T ′ ). Then, we can
remove an arbitrary tile from T ′ to obtain T ′′ : Since, by deﬁnition, S does not contain F as
a scenario, by Lemma 3, T ′′ is feasible for all scenarios S ∈ S. Clearly, G(T ′′ ) is a tree, as
required.
Now assume that there is at least one tree component C ′ in G(T ′ ) along with C. Consider
an arbitrary edge {s, s′ } in C and an arbitrary vertex s′′ ∈ C ′ . We remove {s, s′ } from T ′ and
instead add the edge {s, s′′ } to obtain the tileset T ′′ . Clearly, G(T ′′ ) is a forest. It remains to
prove that T ′′ is feasible for every scenario S ∈ S. By Lemma 2, T ′ is feasible for S \ C and,
hence, so is T ′′ . Because C ∪ C ′ is a connected component in G(T ′′ ), Lemma 3 guarantees that
T ′′ is feasible for every S ′ ( (C ∪ C ′ ) and, in particular, T ′′ is feasible for S ∩ C. Hence, as T ′′
is feasible for S ∩ C and S \ C, applying Lemma 2 we obtain that T ′′ is feasible for S. Clearly,
G[T ′′ ] is a forest, as required.
Intuitively, Lemmas 2 and 3 imply that only the partition of the symbols induced by the
component structure of the graph of a tileset matters, but not the exact topology of each of the
trees. This leads to the following.
Theorem 1. Let S be a family of scenarios and T be a tileset over symbols F . If G(T ) is a
forest, then T is feasible for S if and only if no connected component C of G(T ) is fully contained
in any scenario S ∈ S, i.e., C * S for all scenarios S ∈ S and all connected components C
of G(T ).

5

Proof. “⇒”: Assume towards a contradiction that T is feasible, G(T ) is a forest, and there is a
scenario S ∈ S and a component C of G(T ) such that C ⊆ S. By Lemma 2 there is a feasible
orientation of G(T ) for S ∩ C = C. But this is absurd, because G(T ) is a forest and hence
G(T )[C] contains only |C| − 1 edges.
“⇐”: For each component C of G(T ) and every scenario S ∈ S, we have that C ∩ S ( C,
since C * S. By Lemma 3, we get that T is feasible for C ∩ S. Since this is true for all choices
of C and S, Lemma 2 implies that T is feasible for S.

Example 2. We can now observe that for the instance (F = {1, . . . , 3n}, S = F2 ) from
Example 1 each feasible tileset contains at least 2n tiles: Let T be a feasible tileset for S.
No connected component of G(T ) can be contained in any set in S. Thus, each connected
component has size at least three, meaning that there are at least n connected components.
Since each such connected component induces at least two tiles, T contains at least 2n tiles.

3

NP-hardness and APX-Hardness of Minimum Feasible Tileset

In this section we establish the following result.
Theorem 2. Minimum Feasible Tileset is APX-hard. Minimum Feasible Tileset is
NP-hard even if each scenario has size at most three.
Before proving Theorem 2, let us check that the decision variant of Minimum Feasible
Tileset, in which we want to check for feasible tilesets of size at most a given integer, is
contained in NP: A feasible tileset can be encoded using polynomially many bits with respect
to |F |. Verifying feasibility comes down to solving one bipartite matching problem for each
scenario on an auxiliary graph that has an edge between each symbol in the scenario and every tile containing that symbol, which is possible in polynomial time. Thus we can infer from
Theorem 2 that the decision variant of Minimum Feasible Tileset is NP-complete.
We now prove NP- and APX-hardness of Minimum Feasible Tileset. For this, we ﬁrst
give a relation of Minimum Feasible Tileset to a partitioning problem. Let us say that, for
a ﬁnite set of symbols F and a family of scenarios S ⊆ 2F , a partition P of F is admissible, if
for every P ∈ P and every S ∈ S we have P 6⊆ S. We obtain the following.
Lemma 4. Let F be a set of symbols and S ⊆ 2F \ {F } a family of scenarios. There is a
feasible tileset of size ℓ for S if and only if there is a partition of F which is admissible for S
and comprises |F | − ℓ parts.
Proof. “⇒”: By Lemma 1 there is a feasible tileset T ′ for S of cardinality ℓ such that G(T ′ ) is a
forest. The connected components C1 , . . . , Ck of G(T ′ ) induce a partition P ′ which we claim to
be admissible: Indeed, by Theorem 1 we have Ci * S for all connected components Ci , i ∈ [k],
and scenarios S ∈ S. Furthermore,Psince there are exactly ℓ edges in G(T ′ ) and each connected
component is a tree, we have ℓ = ki=1 |Ci | − 1 = |F | − k. Hence, our partition has k = |F | − ℓ
parts, as required.
“⇐”: Let P = {P1 , . . . , Pp } be an admissible partition with |F | − ℓ parts. We construct a
tileset T by setting G(T )[Pi ] to an arbitrary spanning tree for each i ∈ [p]. Since Pi * S for
each S ∈ S and each i ∈ [p], by Theorem 1, T is feasible for S. The number of tiles in T is
P
p
i=1 |Pi | − 1 = |F | − p = |F | − (|F | − ℓ) = ℓ, as required.
Thus, Minimum Feasible Tileset is equivalent to ﬁnding a ﬁnest-possible partition, i.e. with
maximum number of parts, of the symbols such that no part in the partition is contained in
any scenario.
6

We now give a reduction from Maximum Bounded 3-Dimensional Matching which is
both NP-hard and APX-hard [19]:
Maximum Bounded 3-Dimensional Matching
Input: Three pairwise disjoint sets X, Y, Z, and a set D ⊆ X × Y × Z of triples
such that each element in X ∪ Y ∪ Z occurs in at most three triples in D.
Problem: Find a maximum-size three-dimensional matching for D, i.e., a maximumsize subset D ′ ⊆ D such that no element of X ∪ Y ∪ Z occurs in two triples in D ′ .
Proof of Theorem 2. We give a PTAS-reduction from Maximum Bounded 3-Dimensional
Matching [5]. More precisely, given an instance (X, Y, Z, D) and a desired approximation
ratio r, we construct an instance (F, S) of Minimum Feasible Tileset in time polynomial in the instance size for every ﬁxed r, subject to the following condition. There is a
function f : (0, 1) → Q such that for every r ∈ (0, 1) we have f (r) > 1 and for a arbitrary
given f (r)-approximate feasible tileset T for (F, S) we can construct an r-approximate threedimensional matching M for (X, Y, Z, D) in polynomial time. We specify the function f below
(while ensuring that f (r) > 1).
We ﬁrst describe how to construct the Minimum Feasible Tileset instance (F, S) from
a Maximum Bounded 3-Dimensional Matching instance (X, Y, Z, D). Set the universe
F := X ∪ Y ∪ Z. We choose a function g : (0, 1) → N with g(r) ≥ 3 for all r ∈ (0, 1). The precise
function is given below. The scenarios S consist of all subsets of F that have size at most g(r)
and do not contain any triple in D as a subset (we interpret D as a family of three-element sets).
Formally, S := {S ⊆ F | |S| ≤ g(r) ∧ ∀E ∈ D : E \ S 6= ∅}. This concludes the construction.
Let n := |X ∪ Y ∪ Z| = |F |. Clearly, for any ﬁxed r, we can carry out the construction in time
O(ng(r)+1 ), that is, in polynomial time in the instance size.
Before we show how to compute an approximate three-dimensional matching from an approximate feasible tileset, we ﬁnd a relation between the optimal solution sizes of the two
instances. Note that, from each three-dimensional matching N we can construct an admissible
partition R of F for S satisfying |R| = |N | as follows. Initially, take R = N (where N is
interpreted as a family
S of three-element sets). Then, replace an arbitrary part P ∈ R with
P ∪ ((X ∪ Y ∪ Z) \ R). That is, add to P all elements not covered by N . By deﬁnition of
S, there is no set S ∈ S that contains any P ∈ R, and hence R is admissible. Letting opt3DM
denote the size of an optimal solution to the Maximum Bounded 3-Dimensional Matching
instance, we thus have |P ∗ | ≥ opt3DM for an admissible partition P ∗ containing the maximum
number of parts. Lemma 4 implies that |P ∗ | = n − optFT , where optFT denotes the size of
an optimal solution for the Minimum Feasible Tileset instance. Rearranging terms hence
yields optFT = n − |P ∗ |. Because of |P ∗ | ≥ opt3DM , we have
optFT ≤ n − opt3DM .

(1)

Now let T be an arbitrary f (r)-approximate feasible tileset T for (F, S). We construct an
r-approximate three-dimensional matching M for (X, Y, Z, D) in polynomial time as follows.
Along the way, we gather observations that allow us to prove that M is r-approximate in the
end.
First, by Lemma 4 there is a partition P of F which is admissible for S and has n − |T |
parts. In other words, T has n − |P| tiles. (As the proof of Lemma 4 is constructive, it is
not hard to check that P can be computed in polynomial time.) As T is f (r)-approximate,
|T | ≤ f (r) optFT and hence, n − |P| ≤ f (r) optFT . Applying Inequality (1) we thus obtain
n − |P| ≤ f (r)(n − opt3DM ).
7

(2)

1
We create a partition P 1 = P31 ∪ Pg(r)+1
from P as follows. Obtain P31 by picking, for each
part P ∈ P which contains a triple S
of D, one triple E ∈ D with E ⊆ P S
and putting E (as a set)
1
1
as
, if |F \ P ∈P 1 P | < g(r) + 1, then put F \ P ∈P 1 P into Pg(r)+1
into P31 . To create Pg(r)+1
3
3
1
1
a single set of size at most g(r). In this case we call Pg(r)+1 degenerate. Otherwise, put Pg(r)+1
S
to be an arbitrary partition of F \ P ∈P 1 P into parts of size g(r) + 1 and, perhaps, one part of
3
size at least g(r) + 2 and at most 2g(r) + 1. Note that P31 is admissible for S because each triple
in P31 is not contained in any set in S by deﬁnition of S. We claim that |P 1 | ≥ |P|. Clearly, for
each part in P that contains a triple of D there is at least one part also in P 1 . Furthermore,
since S contains all g(r)-element sets which do not contain any triple of D, each set P ∈ P that
does not contain a triple from D must contain at least g(r) + 1 elements because P is admissible
for S. Hence, |P 1 | ≥ |P|. From Inequality (2) it follows that

n − |P 1 | ≤ f (r)(n − opt3DM ).

(3)

Note that the three-element sets in P 1 , i.e., P31 , form a three-dimensional matching for the
instance (X, Y, Z, D). The sets in P31 will form our r-approximate three-dimensional matching M
after one further augmentation step. The aim of this augmentation is to bound |P31 | by a function
1
of |Pg(r)+1
|. This enables us to give a lower bound on |M | via the size of P 1 .
of P 1 . If there is S
a triple in D that is disjoint from
S Consider the following modiﬁcation
1
P ∈P31 P , then add this triple to P3 . If we now have |F \ P ∈P31 P | < g(r) + 1, then replace
S
1
1
by an arbitrary
the sets in Pg(r)+1
by the single set F \ P ∈P 1 P . Otherwise, replace Pg(r)+1
3
S
partition of F \ P ∈P 1 P into parts of size g(r)+ 1 and, perhaps, one part of size at least g(r)+ 2
3
and at most 2g(r) + 1.
We claim that the above two modiﬁcation steps do not decrease the number ofSsets in P 1 .
1
This is clear if Pg(r)+1
was degenerate before applying them. Otherwise, we have |F \ P ∈P 1 P | >
3
1
g(r) + 3 before applying the modiﬁcation. Hence, each set in Pg(r)+1
had size at least g(r) + 1 ≥
4. Since we moved only three elements from these sets to P31 and afterwards repartition the
remaining elements with sets of size at least 4, the total number of sets cannot decrease.
As before, P31 remains admissible for S. Let P 2 be the partition obtained by exhaustively
2
applying the above modiﬁcation, let P32 equal the resulting set P31 and let Pg(r)+1
be the resulting
1
set Pg(r)+1 . We deﬁne the three-dimensional matching M as the family of three-element parts
in P 2 ∩ D, that is M = P32 . As mentioned, we have |P 2 | ≥ |P 1 |. From Inequality (3) it thus
follows that
n − |P 2 | ≤ f (r)(n − opt3DM ).
(4)
It remains to show that M is r-approximate (for appropriate functions f (r) and g(r)).
2
1
|. If Pg(r)+1
is degenerate and if this relation
We now claim that 12|P32 |/(g(r) + 1) ≥ |Pg(r)+1
2
does not hold, then |F | is upper bounded by 3|P3 | + g(r) − 1 < 3(g(r) + 1)/12 + g(r) − 1, that is,
|F | is upper bounded by a constant. Hence, we may compute the optimal solution in constant
time in this case. Thus, we may, without loss of generality, assume that the relation holds if
1
Pg(r)+1
is degenerate.
1
If Pg(r)+1 is not degenerate, we claim that the above modiﬁcation of P 1 is applicable as long
1
|, where the right hand side bounds the number of unmatched
as 12|P31 | < (g(r) + 1)|Pg(r)+1
elements. Indeed, since each element in F = X ∪ Y ∪ Z is contained in at most three triples
in D, for each triple E in P31 , there are at most twelve elements of F whose incident triples in
1
|,
D cannot be added to P31 , because they overlap with E. Hence, if 12|P31 | < (g(r) + 1)|Pg(r)+1
then there exists at least one element of F whose incident triples do not overlap with any triple
in P31 . This means that at least one triple will be added to P31 in the above modiﬁcation step,
8

because, without loss of generality, each element is in at least one triple. This indeed implies for
2
partition P 2 (after exhaustive modiﬁcation) that 12|P32 |/(g(r) + 1) ≥ |Pg(r)+1
|. We thus have
2
n − |P 2 | = n − (|P32 | + |Pg(r)+1
|)


12
|P32 |,
≥ n− 1+
g(r) + 1

and since P32 = M , in combination with Inequality (4) we have


12
n− 1+
|M | ≤ f (r)(n − opt3DM ).
g(r) + 1
Thus,
g(r) + 1
· ((1 − f (r))n + f (r) opt3DM ) ≤ |M |.
g(r) + 13

(5)

The same modiﬁcation that we applied above to (the three-element sets of) P 1 works for each
three-dimensional matching. As we cannot improve a maximum three-dimensional matching,
each element of F is either matched — of this type there are 3 opt3DM elements — or it is in
a triple together with a matched element — of this type there are at most 12 opt3DM elements
because each element is in at most three triples in D. Hence, n ≤ 3 opt3DM +12 opt3DM =
15 opt3DM . Note that 1 − f (r) < 0. Inequality (5) thus implies
g(r) + 1
· (15 − 14f (r)) · opt3DM ≤ |M |.
g(r) + 13

(6)

We now deﬁne f and g by setting g(r) := max{3, ⌈13r/(1 − r)⌉} and
f (r) :=

−rg(r) − 13r + 15g(r) + 15
.
14g(r) + 14

Clearly, g(r) ≥ 3 as required. We claim also that f (r) > 1. To see this, consider subtracting
the denominator from the numerator in f (r) to obtain x, that is,
x := −rg(r)−13r +15g(r)+15−14g(r)−14 = −rg(r)−13r +g(r)+1 = (1−r)g(r)−13r +1.
13r
If 3 ≤ 13r/(1 − r), then x ≥ (1 − r) · 1−r
− 13r + 1 > 0, that is f (r) > 1. If 3 > 13r/(1 − r) then
r < 3/16. Thus, x ≥ (1 − 3/16) · 3 − 13 · 3/16 + 1 = 1 > 0 and again f (r) > 1. Thus, these are
suitable deﬁnitions. All that remains is to show that the approximation factor in Inequality (6)
is at least r, that is,
g(r) + 1
· (15 − 14f (r)) ≥ r.
(7)
g(r) + 13

Observe that
15 − 14f (r) =

15g(r) + 15 15g(r) + 15 − rg(r) − 13r
rg(r) + 13r
−
=
.
g(r) + 1
g(r) + 1
g(r) + 1

Hence,
rg(r) + 13r
g(r) + 1
· (15 − 14f (r)) =
= r.
g(r) + 13
g(r) + 13
This implies that Inequality (7) holds. Hence, there is a PTAS-reduction from Maximum
Bounded 3-Dimensional Matching to Minimum Feasible Tileset.
9

NP-hardness of the decision version of Minimum Feasible Tileset follows from the following modiﬁcation to the reduction above. Instead of Maximum Bounded 3-Dimensional
Matching we reduce from the NP-hard decision problem which asks whether there is a threedimensional matching with n/3 triples [15]. We use the reduction above and set g(r) = 3 and the
desired feasible tileset size to 2n/3. As mentioned, this can be done in polynomial time. For the
correctness, each three-dimensional matching of size n/3 is also an admissible partition for S.
Hence, it implies a feasible tileset of size n − n/3 = 2n/3 by Lemma 4. In the reverse direction,
each feasible tileset of size 2n/3 implies an admissible partition with n/3 parts by Lemma 4.
Each of these parts is of size three because S contains all size-two subsets of F . Among sets of
size three, the only sets not contained in S are precisely the sets in D; hence, each part of an
admissible partition is in D. That is, any admissible partition is a three-dimensional matching
as well.

4

A 4/3-approximation for Minimum Feasible Tileset

In this section, we propose an approximation algorithm for Minimum Feasible Tileset with
unbounded scenario size. Motivated by the structural insights of Section 2, we construct a
tileset that induces a forest in the corresponding graph, with the property that none of its
components are contained in a single scenario. Since a component of size k requires k − 1 tiles,
we additionally aim for small components in order to keep the resulting tileset small.
We ﬁrst take as many components of size two as possible among all disjoint sets of two
symbols that are not both contained in the same scenario. This can easily be achieved by
computing a maximum matching in the graph that has an edge for each candidate component.
Similarly, among all remaining symbols, we try to form many (disjoint) components of size
three, without creating components that are contained in a single scenario. For this, we employ
a simple greedy strategy, that repeatedly takes any possible component until no possible candidates remain. (While there are better packing strategies available for sets of size three, we
will see that improving the packing strategy alone does not improve our approximation ratio.)
Finally, for each leftover symbol we add an individual tile (pairing that symbol in such a way
as to prevent cycles).
′
We give a more formal listing in Algorithm A. We use F̄i (F ′ ) = {C ∈ Fi | ∀S ∈ S : C * S}
to denote the family of all sets of symbols in F ′ that are of size i and not fully contained in a
single scenario. In the following, we identify connected components with their sets of vertices.
Algorithm A: 4/3-approximation for minimum feasible tilesets
Input: A set F of symbols and a set S of scenarios, where S ⊆ 2F \ {F }.
Output: A set of tiles T .
T2 ← maximum matching in graph G(F̄2 (F )).
S
P ← greedy set packing of F̄3 (F \ t∈T2 t).
S
T3 ← {f1 ,f2 ,f3 }∈P {{f1 , f2 }, {f2 , f3 }}.
S
if T2 ∪ T3 6= ∅ then take froot ∈ t∈T2 ∪T3 t
else take froot ∈ F .
T1 ← {{f, froot } | f ∈ F \
return T = T1 ∪ T2 ∪ T3 .

S

t∈T2 ∪T3

t , f 6= froot }.

Theorem 3. Algorithm A computes a 4/3-approximation for Minimum Feasible Tileset.
10

Proof. We ﬁrst argue that the set of tiles T = T1 ∪ T2 ∪ T3 computed by Algorithm A is feasible
for S. First observe that G(T ) is a forest. This is true, because G(T2 ∪ T3 ) consists of trees
of sizes 2 and 3, G(T1 ) is a star, and T1 ∩ (T2 ∪ T3 ) contains at most one node (froot ). Using
Theorem 1 it only remains to show that no connected component C of G(T ) is contained in
any scenario S ∈ S, i.e. C ∩ S ( C. By deﬁnition of Algorithm A this is true for all connected
components of the graph G(T2 ∪ T3 ). If T2 ∪ T3 6= ∅, then each component of G(T ) is a superset
of a component of G(T2 ∪ T3 ), and is thus not contained in any scenario. If T2 ∪ T3 is empty,
then G(T ) = G(T1 ) consists of a single component that is not contained in any scenario, since,
by deﬁnition, F ∈
/ S. Thus T is feasible for S.
We now bound the size of T with respect to a minimum cardinality tileset T ⋆ . To do this
we distribute virtual currency (gold) to the symbols in F , such that the total gold distributed
is 4/3 times the size of T ⋆ . We later use this gold to pay one unit of gold to certain symbols
that these can in turn use to provide for (at most) one tile of T that involves this symbol. To
complete the proof, we establish that each tile of T is provided for by one of its two symbols.
Let G⋆ := G(T ⋆ ) be the graph induced by T ⋆ and F̄i⋆ be the set of connected components
of size i ∈ {2, . . . , |F |} in G⋆ . By Lemma 1, we may assume that G⋆ is a forest. Furthermore,
because each symbol appears in at least one scenario, graph G⋆ does not contain components
of size 1. Since the symbols in a component of size i > 1 are part of exactly i − 1 tiles in T ⋆ ,
we may distribute all available gold by giving 4/3 · i−1
i gold to each symbol in a component of
⋆
F̄i , for all i ∈ {2, . . . , |F |}. This gold is used to pay symbols in what follows. We call a symbol
s ∈ F sufficiently paid if one of the following holds: (i) s is paid, (ii) s appears in a tile T ∈ T2
and the other symbol of T is paid, or (iii) s appears in a tile T ∈ T3 and the other two symbols
in the same component of G(T3 ) are paid. Below, we show how to suﬃciently pay all symbols.
This completes the proof, since then all tiles in T1 ∪ T2 ∪ T3 can be provided for (note that then
⋆
each tile in T1 contains its own paid symbol). We call
S a component of G sufficiently paid, if
⋆
all its symbols are suﬃciently paid. Let F≥4 := F \ C∈F̄ ⋆ ∪F̄ ⋆ C be the set of all symbols not
2
3
in components of size two or three in G⋆ . In paying the symbols we will maintain the invariant
⋆ is either suﬃciently paid, or it still holds its gold (all its
that each element of F̄2⋆ ∪ F̄3⋆ ∪ F≥4
symbols still hold their gold, respectively).
We deﬁne a graph H = (V, E) that has the components in F̄2⋆ ∪ F̄3⋆ as its vertices, as well
⋆ (cf. Figure 1).
as the symbols that are not part of these components, i.e., V = F̄2⋆ ∪ F̄3⋆ ∪ F≥4
In this way, each vertex of H represents up to three symbols. For each tile T ∈ T2 we introduce
an edge connecting the vertices of H representing the two symbols of T , possibly introducing
self-loops. Since T2 is a matching, and since the vertices in H represent at most three symbols
each, all vertices in H have degree at most 3. We partition the edges of H into paths, cycles,
and self-loops, and show for each how to use the gold remaining at its vertices to pay all symbols
in the components of G⋆ that are intersected by the path/cycle/self-loop. We will ensure that
every symbol (except possibly froot ) on a tile in T1 is paid. Since each symbol on a tile of T2
appears only exactly on this and no other tile of T2 ∪ T3 , it is thus suﬃcient to pay only one of
the two symbols on each tile of T2 .
Let P be the set of all paths in H connecting (diﬀerent) vertices of degree 1 or 3 with internal
nodes of degree 2. Consider the paths in P one by one. We use the gold available along path P ∈
P of length k as follows (cf. Figure 2). Let N2 , N3 be the number of internal nodes of P that
represent 2 and 3 symbols, respectively. Note that P has no inner nodes that represent a single
symbol, since T2 is a matching, and hence k = 1+N2 +N3 . Also, P is the only path visiting these
inner nodes and hence they all still hold their gold. Let N1end , N2end , N3end ≤ 2 be the number of
endpoints of P that still hold gold and represent 1, 2, and 3 symbols, respectively. Similarly, let
N0end be the number of endpoints without gold. By our invariant, the symbols or components
represented by the endpoints without gold left have already been suﬃciently paid before. We
11

Figure 1: Illustration of the graph H that has as its nodes the components of sizes 2 and 3
in G⋆ and all symbols that appear in components of other sizes. An edge between symbols
corresponds to a tile in T2 .

Figure 2: Illustration of our procedure for paying all symbols represented by the nodes along
a path in graph H. Shaded components have been suﬃciently paid for previously. For the top
path we have N1end = N3end = 1, N2 = 3, N0end = N2end = N3 = 0. For the bottom path we have
N0end = N2end = 1, N2 = 2, N3 = 1, N1end = N3end = 0.
make sure that all other nodes along P are suﬃciently paid. We do this by, for all tiles that form
the path P , paying one of the two corresponding symbols, and, in addition, paying every further
symbol represented by nodes along P . Note that this preserves the invariant. The total cost is
C − = k + N2end + 2N3end + N3 − N0end = 1 + N2end + 2N3end + N2 + 2N3 − N0end .

(8)

Using that each endpoint of P that contributes to N1end represents a symbol that is part
of a component in G⋆ of size i ≥ 4, we get that the gold available at this symbol is at least
4 i−1
3 · i ≥ 1. Hence, the gold available to us is at least
C+ =

3
4 end
(N2 + 2N3end + N2 + 2N3 + N1end ).
3
4

(9)

Since N0end + N1end + N2end + N3end = 2, we get
2
1
1
2
C + − C − = 1 − N2end − N3end + N2 + N3 .
3
3
3
3
Hence, we have C + ≥ C − , unless N2end = 2 and N0end = N1end = N3end = N2 = N3 = 0,
i.e. P is of length one, connecting two tiles p1 , p2 ∈ F̄2⋆ by an edge which corresponds to a
12

16
3 ,5

8, 8

8
3

1, 0

0, 0

8
3

8
3, 2

2, 1

+ 2, 4

+ 1, 3

1, 0

16
3

0, 0

16
3 ,5

3, 2

16
3 ,5

8
3, 2

8
3

+ 1, 6

8
3, 2

8
3, 2

+ 1, 3

8
3, 2

0, 0

8
3, 2

Figure 3: Possible intersections of components of G(T3 ) (arcs) and G⋆ (ellipses). Shaded components have been suﬃciently paid previously. Conﬁgurations are labeled by the available gold
C + and the required gold C − . Symmetrical conﬁgurations are omitted.
tile t ∈ T2 . To see that this case cannot occur, observe that, ﬁrst, p1 and p2 are of degree 1 in H.
Second, since T ⋆ is feasible, no component of G⋆ is contained in a single scenario (Theorem 1),
and thus p1 , p2 ∈ F̄2⋆ ⊆ F̄2 (F ). This is a contradiction to T2 being a maximum matching in
graph G(F̄2 (F )), as the matching can be augmented by removing t and adding p1 and p2 .
Similarly to the above, we can consider all cycles in H with at most one node of degree 3
one by one. (Note that cycles with at least two nodes of degree 3 contain a path as before.)
If a cycle of length k does not contain a node of degree 3, or the node of degree 3 is not yet
suﬃciently paid (and thus still holds its gold), the cost for the cycle and its available gold are
3
C − = k + N3 = N2 + 2N3 = C + < C + ,
4
where N2 , N3 are the numbers of nodes of P that represent 2 and 3 symbols, respectively. If
the node of degree 3 has no gold left, then it has already been suﬃciently paid and C − =
N2 + 2N3 − 3 < 34 C + . In either case, the available gold allows to suﬃciently pay all nodes along
the cycle. Finally, each self-loop in H connects two symbols in the same component C of size 2
or 3 in G⋆ . If |C| = 2, the gold available among the two symbols is C + = 34 , while we require
only C − = 1 unit of gold. If |C| = 3, we have C + = 83 and C − = 2.
After processing all paths, cycles, and self-loops all nodes of H intersecting a tile of T2 are
suﬃciently paid. In particular, since T2 is a maximum matching, all components in F̄2⋆ are
suﬃciently paid. In the next step we ensure that all components of F̄3⋆ are suﬃciently paid. By
construction, every element of F̄3⋆ , that is not suﬃciently paid yet, intersects at least one tile
of T3 . We can thus consider the components of G(T3 ) one by one and make sure to suﬃciently
pay each element of F̄3⋆ that intersects the considered component of G(T3 ).
Consider a component of G(T3 ) involving the three symbols f1 , f2 , f3 (cf. Figure 3 in the
following). Let C3 ⊆ F̄3⋆ be the set of components of size 3 in G⋆ that involve at least one of these
symbols and have not yet been suﬃciently paid (i.e., still hold their gold). Further, let Nn be
⋆ that are not yet suﬃciently paid. Since all comthe number of symbols among {f1 , f2 , f3 } ∩ F≥4
ponents in F̄2⋆ are suﬃciently paid, the gold we have available is at least C + ≥ 43 (2|C3 | + 34 Nn ).
We ensure that (at least) two symbols among f1 , f2 , f3 are paid, as well as all other symbols appearing in C3 . In this way, each component in C3 is suﬃciently paid. Note that this preserves our
13

⋆ is either suﬃciently paid, or still holds its gold. The
invariant that each element of F̄2⋆ ∪ F̄3⋆ ∪F≥4
cost for paying the symbols f1 , fS
2 , f3 is at most 2. Since in addition to f1 , f2 , f3 there are 3|C3 | +
Nn − 3 symbols needing pay in C∈C3 C ∪ {f1 , f2 , f3 }, and because |C3 | ≤ 3, the total cost is

8
C − ≤ 3|C3 | + Nn − 1 ≤ |C3 | + Nn ≤ C + .
3

At this point, we have suﬃciently paid all components in F̄2⋆ ∪ F̄3⋆ using gold only from these
components. This means that all remaining symbols that are not suﬃciently paid yet have at
least 34 · 4−1
4 = 1 gold available, which we can use to pay these symbols themselves. Now all
⋆ have been suﬃciently paid and the proof is complete.
elements of F̄2⋆ ∪ F̄3⋆ ∪ F≥4
Our analysis of Algorithm A is tight in three diﬀerent spots: (i) A path of length 1 in the
graph H deﬁned above that visits a component of size 2 and a component of size 3 of the
optimum solution T may lead to 4 tiles in our solution compared to the 3 tiles required in the
optimum solution, i.e., Equations (8) and (9) coincide if N2end = N3end = 1 and all other terms
vanish. (ii) The ﬁrst intersection of a component of G(T3 ) with components of G⋆ illustrated
in Figure 3 may lead to 8 tiles in our solution compared to the 6 tiles required in the optimum
solution. (iii) Each symbol of a component of size 4 in G⋆ might result in a single tile for
this symbol only, in which case the optimum solution requires 3 tiles for the symbols of the
component, while our solution requires 4 tiles. To improve Algorithm A we have to address
each of these three bottlenecks. For (i), we either would have to alter the matching T2 to
prevent the described situation, or combine the analysis to account for the loss in other places.
The aspect (ii) can easily be prevented by employing a more sophisticated set packing algorithm
(e.g., the (4/3 + ε)-approximation of Cygan [6]). Finally, to avoid (iii), we would need to pack
sets of size 4 similarly to our packing of sets of size 3. In addition to requiring one more level
of analysis, this would also complicate the other levels, as we would have to include sets of size
4 in our reasoning there.

5

Bounded number of scenarios

In this section, we prove that Minimum Feasible Tileset can be solved in polynomial time
when the number |S| of scenarios is some constant. For convenience, for the course of this
section, we switch to the decision variant of Minimum Feasible Tileset. That is, we equip
each instance (F, S) of Minimum Feasible Tileset with an additional integer ℓ, and we ask,
whether there is a feasible tileset for S with at most ℓ tiles. Clearly, solving the decision variant
in polynomial time implies that also the optimization variant is solvable in polynomial time.
We provide an algorithm that solves any instance (F, S, ℓ) in time f (|S|)|(F, S, ℓ)|c , i.e., in
time O(|(F, S, k)|c ) for bounded values of |S|. In other words, Minimum Feasible Tileset is
ﬁxed-parameter tractable with respect to the number of scenarios.
Our algorithm works by ﬁrst translating the input instance (F, S, ℓ) into an integer linear
program (ILP) in such a way that the ILP is feasible (i.e., contains at least one integer point)
if and only if (F, S, ℓ) admits a feasible tileset with at most ℓ tiles. The ILP uses O(|S||S| )
variables. Lenstra [22] proved that deciding feasibility of any ILP is ﬁxed-parameter tractable
with respect to the number of variables; the currently fastest algorithm was obtained by Frank
and Tardos [14], modifying an algorithm by Kannan [20].
Theorem 4 (Frank and Tardos [14]). In O∗ (pO(p) ) time we can decide whether a given ILP
with p variables is feasible.
Using this, we can prove the following result.
14

Theorem 5. Minimum Feasible Tileset on instances with at most k scenarios can be solved
k+1
in time O∗ (kO(k ) ).
Intuitively, a bounded number of scenarios also implies a bound on the number of diﬀerent
subsets of scenarios in which a tile can appear. Thus, one would like to forget the actual identities
of the symbols and only remember how many symbols appear, say, exactly in scenarios S1 , S5 ,
and S6 . It appears, however, that grouping symbols in this way is insuﬃcient since symbols
from the same group can nevertheless have diﬀerent patterns for how they are provided by tiles:
E.g., one tile could provide such a symbol in all three scenarios S1 , S5 , and S6 , whereas other
symbols of the same group might need three separate tiles for S1 , S5 , and S6 . To cope with
this, the constructed ILP has separate variables for all partitions of scenario subsets as well as
variables for all ways of using a tile (recall that a tile has two symbols, meaning that it has two
disjoint subsets of the scenario that express when either symbol is provided by the tile).
Proof of Theorem 5. We formulate Minimum Feasible Tileset as an ILP and employ Kannan’s algorithm. Intuitively, each tile contributes both of its symbols to diﬀerent (disjoint)
subsets of the scenarios. For example, if we have 5 scenarios, a tile might contribute one of its
symbols to scenarios 1 and 4, the other to scenarios 3 and 5, and neither to scenario 2. Each
tile is associated with such a pattern of how it contributes to scenarios, and one part of the
variables of our ILP track the number of tiles having each of the possible patterns. On the
other hand, each symbol has a pattern associated with it, depending on which occurrences of
the symbol are provided by the same tile. In our example, a symbol appearing in scenarios
1, 2, and 4 might be provided by the same tile in scenarios 1 and 4, and by a diﬀerent tile in
scenario 2. The remaining variables of the ILP track the number of symbols having each of
the possible patterns. We provide exchange arguments to show that enforcing correct totals for
these variables by linear constraints is suﬃcient to ensure that a feasible assignment of tiles to
symbols exists for each scenario.
ILP formulation. To make our description precise, let an instance (F, S, ℓ) with k scenarios
S = {S1 , . . . , Sk } be given. For brevity, we refer to a subset of S by the corresponding index
set. For every subset I ⊆ [k] of scenarios we countTthe number
S of symbols that occur exactly in
these scenarios and denote this number by cI = | i∈I Si \ i∈I
/ Si |. The family of all partitions
of I is denoted by Π(I). The ILP is constructed as follows.
1. For each set I ⊆ [k] and each partition I = {I1 , . . . , Is } ∈ Π(I) we introduce a variable yI .
The intention is that variable yI counts the number of symbols that occur (exactly) in
scenarios I := I1 ∪ . . . ∪ Is and have pattern I associated with them, in the following way:
Exactly s tiles, say, T1 , . . . , Ts , are used for such a symbol and the symbol is provided by
tile Ti in the scenarios Ii .
For each I we add a constraint that enforces the total number of patterns to equal the
number cI of symbols that occur in the scenarios I:
X
cI =
yI
∀I ⊆ [k].
I∈Π(I)

For example, if I = {1, 2, 3}, the following variables are created:
y{{1,2,3}} , y{{1,2},{3}} , y{{1,3},{2}} , y{{2,3},{1}} , y{{1},{2},{3}} .
The number of y-variables equals the number of subpartitions of the set [k]. This is
upper bounded by kk + 1: We can k-color all subpartitions other than the partition into
15

singletons by using color k for all unused elements and colors 1, . . . , k − 1 for the elements
of each set in the partition (only the partition into singletons has k sets). Thus, we get
an injective mapping of all but one subpartition into the k colorings of [k]; this gives a
total of kk + 1.
2. For the tiles, we introduce variables xI,J for all I, J ⊆ [k] with I ∩ J = ∅ and I ∪ J 6= ∅; for
convenience we identify xI,J = xJ,I . Intuitively, the variable xI,J stands for the number of
tiles that provide one of their symbols for scenarios I and the other symbol for scenarios J.
For example, for k = 3 we create the following variables:
x∅,{1} , x∅,{2} , x∅,{3} , x∅,{1,2} , x∅,{1,3} , x∅,{2,3} , x∅,{1,2,3} ,
x{1},{2} , x{1},{3} , x{1},{2,3} , x{2},{3} , x{2},{1,3} , x{3},{1,2} .
k

The number of x-variables is 3 2−1 corresponding to all partitions of [k] into three sets
(i.e., I, J, and [k] \ (I ∪ J)), without I = J = ∅, and identifying xI,J with xJ,I .
We add constraints that enforce that the number of tiles of each pattern match the sum
of the corresponding y-variables. Concretely, we add
X
X
yJ =
xI,J
∀I ⊆ [k], I 6= ∅.
(10)
I⊆J⊆[k]
J ∈Π(J)
I∈J

J⊆[k]\I

We compare the number of tiles that provide one of their symbols for scenarios in I with
the number of symbols that have I in their pattern. For the set of scenarios J such symbols
appear in we must have I ⊆ J ⊆ [k], and we need partitions J ∈ Π(J) that contain I.
3. As a ﬁnal constraint we enforce that the total number of used tiles is no more than ℓ. To
this end, we simply sum over all x-variables and add
1 X
xI,J ≤ ℓ.
2
I,J⊆[k]
I∩J=∅
I∪J6=∅

k

This completes our construction. We use p ≤ kk + 1 + 3 2−1 = O(kk ) variables and, thus, Kank
k+1
nan’s algorithm decides feasibility of our ILP in time O∗ (pO(p) ) = O∗ ((kk )O(k ) ) = O∗ (kO(k ) ).
Correctness. First assume that the given instance (F, S, ℓ) of Minimum Feasible Tileset
admits a feasible tileset T of minimum cardinality |T | ≤ ℓ. Since T is feasible for each scenario Si ∈ S, we may let ϕi : Si → T be an injective function that assigns each symbol in Si a
unique tile in T that can provide it. We specify feasible values for the x- and y-variables.
1. x-variables. Each tile T ∈ T has two symbols, say, T = {s, s′ }, and, hence, for each i ∈ [k]
it is the image of at most one of s and s′ . Formally, let
I := {i ∈ [k] | ϕi (s) = T },
J := {j ∈ [k] | ϕj (s′ ) = T }.
That is, the set I contains all scenarios for which tile T provides symbol s, and J is the
analogue for symbol s′ . Since the functions ϕi are injective, we must have that I ∩ J = ∅.
16

We have I ∪ J 6= ∅ as otherwise T would not be used for any scenario, contradicting the
minimality of T . We say that tile T has pattern {I, J}.
For each I, J ⊆ [k] with I ∩ J = ∅ and I ∪ J 6= ∅, we set xI,J to the number of tiles with
pattern {I, J}. Clearly, the constraint forcing the total value of the x-variables to be at
most ℓ is fulﬁlled since |T | ≤ ℓ.
2. y-variables. Similarly to the tiles in T we determine a pattern for each symbol s ∈ F .
We let T (s) := {T ∈ T | ∃i ∈ [k] : ϕi (s) = T } = {T1 , . . . , Tr }, i.e., the set of tiles that
provide s in at least one scenario. Let I ⊆ [k] be the set of scenarios containing s. We
deﬁne a partition {I1 , . . . , Ir } of I by
Ip := {i ∈ [k] | ϕi (s) = Tp },
for all p ∈ [r]. We say that symbol s has pattern {I1 , . . . , Ir } ∈ Π(I).
For each I ∈ [k] and each partition I ∈ Π(I) we set yI to the number of symbols in F
with pattern I. Clearly, this fulﬁlls the constraint that all y-variables whose pattern is
a partition of some set I ⊆ [k] equals the total number cI of symbols that occur exactly
among the scenarios in I.
It remains to verify that the constraint relating x- and y-variables is satisﬁed. To this end, let
us ﬁx some I ⊆ [k], I 6= ∅, and consider the constraint
X
X
yJ =
xI,J .
I⊆J⊆[k]
J ∈Π(J)
I∈J

J⊆[k]\I

For each tile T ∈ T that contributes to the right-hand-side, there must be a unique symbol s
in F , such that ϕi (s) = T if and only if i ∈ I. For this symbol, we have T ∈ T (s), the set
of scenarios J containing s satisﬁes I ⊆ J ⊆ [k], and I is part of the pattern of s. Hence, s
contributes to the left-hand-side. Conversely, if s is a symbol contributing to the left-hand-side,
then I must be part of the pattern of s. This means that there is a unique tile T ∈ T , such
that ϕi (s) = T if and only if i ∈ I. This tile has I in its pattern and thus contributes to
the right-hand-side. Overall, the contribution to both sides is equal, and our assignment to xand y-variables is feasible, as claimed.
Now, assume that the ILP constructed from (F, S, ℓ) is feasible and ﬁx a feasible assignment
to the x- and y-variables. We derive a feasible tileset for all scenarios in S. The set of all
symbols can be partitioned according to the scenarios I ⊆ [k] that each symbol appears in. The
total count cI of symbols in I is matched by the sum of y-variables that are indexed by the
partitions I ∈ Π(I). We arbitrarily assign to each symbol with scenario set I a pattern I ∈
Π(I) under the sole constraint that the total number of symbols with pattern I matches the
corresponding variable yI . For a symbol with assigned pattern I = {I1 , . . . , Ir } the intention is
to use r tiles T1 , . . . , Tr that are each responsible for one set Ip ∈ I.
We will use a number of tiles that exactly matches the sum of x-variables, and thereby
ensure that the ﬁnal tileset has cardinality at most ℓ. We do not pick symbols for each tile
but, according to the x-variables, we pick for each tile two disjoint sets of scenarios in which
its two symbols will be used. Concretely, exactly xI,J tiles will be used in I-scenarios for one
symbol and in J scenarios for their other symbol, i.e., we use xI,J tiles of pattern {I, J}. Recall
that I ∩ J = ∅ and that the sum of these variables does not exceed the maximum number of
allowed tiles ℓ.

17

Finally, we assign symbols to tiles according to symbol and tile patterns in a canonical
way. Speciﬁcally, symbols whose pattern contains some ﬁxed I ⊆ [k] are assigned to tiles that
contain I in their pattern. By constraint (10) the number of symbols and the number of tiles
are equal. Note that each tile is used for two disjoint sets I, J ⊆ [k] and each variable xI,J
appears in two (10)-constraints (for I and for J). Thus, each tile with pattern {I, J} is assigned
two symbols, one requiring the tile for the scenarios in I and the other requiring it the ones
in J. Similarly, a symbol with pattern I = {I1 , . . . , Ir } contributes to r constraints (10), one
for each I1 , . . . , Ir . Accordingly, these constraints enforce the correct sum of the corresponding
variables xI1 ,· , . . . , xIr ,· . (Recall that we identiﬁed xI,J with xJ,I .)
We argue that the constructed tileset is indeed feasible for all scenarios Si ∈ S. Consider
any symbol s ∈ Si with pattern J . Since s appears in Si , we have i ∈ I ∈ J for some
set I. By the above, we know that there is a tile T containing s that has I as a part of its
pattern {I, J}. Since, by deﬁnition, I ∩ J = ∅, we have i ∈
/ J and may safely use T for symbol s
in scenario Si .

6

Bounded number of symbols

We now analyze the inﬂuence of the number of symbols |F | on the complexity of solving an
instance (F, S, ℓ) of the decision variant of Minimum Feasible Tileset. (That is, as in section
Section 5, we want to decide whether there is a feasible tileset for S with at most ℓ tiles.) It
is easy to see that the problem becomes solvable in polynomial time when F is bounded: The
instance is trivial if ℓ ≥ |F | since, in that case, we can aﬀord to dedicate a separate tile for
each symbol. Otherwise, there are only O(|F |2ℓ ) ⊆ O(|F |2|F | ) ways to ﬁx ℓ tiles. As mentioned
in Section 3, each candidate tileset can be veriﬁed by solving a bipartite matching problem for
each scenario, on a graph that has an edge between each symbol in the scenario and every
tile containing that symbol. This yields an overall runtime of O∗ (|F |2|F | ), and, hence, ﬁxedparameter tractability in |F |. Using structural insights of Section 2 we are able to improve on
this naive running time.
Theorem 6. Instances (F, S, ℓ) of the decision variant of Minimum Feasible Tileset can
be solved in time O∗ (3|F | ).
Note that, as every symbol occurs in a scenario, ℓ ≥ |F |/2. Hence, Theorem 6 gives a
ﬁxed-parameter algorithm also for parameter ℓ.
Proof of Theorem 6. We describe a dynamic programing algorithm for solving an instance
(F, S, ℓ). Recall that we may assume ℓ < |F |; otherwise the instance is trivial. Our algorithm uses a table M of size 2|F | that is indexed by subsets D ⊆ F , with each entry taking
integer values from [|F |] ∪ {−∞}. At the end of the computation, each entry M (D) will be set
to −∞ if D ⊆ S for some scenario S ∈ S, and otherwise to the maximum integer i ∈ [|F |] for
which there is a partition of D into i sets D1 , . . . , Di such that no scenario contains any set in
{D1 , . . . , Di } as a subset.
In the end, by Theorem 1, the entry M (F ) contains the maximum number of components
in the graph corresponding to a feasible tileset. Accordingly, every corresponding tileset T has
minimum cardinality. Hence, and since each connected component C in the graph (F, T ) is
composed of |C| − 1 tiles, the instance (F, S, ℓ) admits a tileset of size ℓ if and only if M (F ) ≥
|F | − ℓ.
We ﬁll out the entries of the table in order of increasing subset sizes. Each entry is computed
via the following recurrence. (Note that the 1 in the maximum taken over subsets D ′ of D stands

18

for the trivial partition of D into just one set. This is the best value in case that no split into
at least two sets can be found such that both sets are not subsets of scenarios.)

−∞,
if D ⊆ S for some S ∈ S,
M (D) = max
′
′
{1, M (D ) + M (D \ D )}, otherwise.

D ′ ⊂D
2≤|D ′ |≤|D|/2

Thus, for each D ⊆ F that is not a subset of a scenario we need to compute the maximum
of M (D ′ ) + M (D \ D ′ ) over less than 2|D| subsets D ′ of D. By the well-known binomial theorem
the total number of evaluations taken over all D ⊆ F can be upper bounded by 3|F | giving us
the claimed runtime.
After this ﬁxed-parameter tractability result, and taking into account the trivial bound
of 2|F | for the number of scenarios (giving a worst-case size of instances of O(2|F | |F |)), it
is natural to ask whether polynomial-time preprocessing can simplify input instances to size
polynomial in |F |. We show that this is impossible unless NP ⊆ coNP/poly (and the polynomial
hierarchy collapses). More generally, we prove that for the restricted case d-Minimum Feasible
Tileset, where scenarios have size at most d, no polynomial-time algorithm can achieve a size
of O(kd−ε ). Note that this restricted case has an essentially matching upper bound of |S| <
(|F | + 1)d = O(|F |d ).1 As a consequence there is no reduction to size polynomial in |F | for
the general Minimum Feasible Tileset problem: Any size O(kc ) preprocessing for Minimum
Feasible Tileset could be used for d-Minimum Feasible Tileset, for any d > c, and violate
the lower bound.
Theorem 7. Let d ≥ 3 and ε be a positive real. There is no polynomial-time algorithm that
reduces every instance of d-Minimum Feasible Tileset to an equivalent instance (possibly of
a different problem) of size O(|F |d−ε ), unless NP ⊆ coNP/poly.
To prove Theorem 7 we employ a similar result by Dell and Marx [7] for Exact Cover by
d-Sets, which is deﬁned as follows.2
Exact Cover by d-Sets

Input: A universe X and a family C of d-element sets C ∈ Xd .
Problem: Is there an exact d-set cover for X, i.e., a partition of X into a family
C ′ ⊆ C of disjoint sets?
Note that the original result by Dell and Marx [7] is given in terms of the size k of an
exact d-set cover. Clearly, k = |Ud | and, thus, we have O(kd−ε ) = O(|U |d−ε ) and may instead
phrase the result in terms of |U |. Furthermore, their result builds on work by Dell and van
Melkebeek [8] and, thus, extends to any polynomial time algorithms (rather than just problem
kernels as mentioned there) whose output instances can be with respect to a diﬀerent problem.
We give the following paraphrased version of the result.
Theorem 8 (Dell and Marx [7]). Let d ≥ 3 and ε be a positive real. There is no polynomialtime algorithm that reduces every instance (U, H) of Exact Cover by d-Sets to an equivalent
instance of size O(|U |d−ε ) (possibly with respect to a different problem), unless NP ⊆ coNP/poly.
The following lemma, together with Theorem 8, directly implies Theorem 7.
1
A compression to O(|F |d ) size can be achieved by specifying one bit for each possible scenario in S and
setting it to one if the scenario is present and zero otherwise.
2
Dell and Marx called this problem Perfect d-Set Matching.

19

Lemma 5. There is a polynomial-time reduction from Exact Cover by d-Sets to Minimum
Feasible Tileset such that instances (X, C) are mapped to instances (F, S, ℓ) with F = X
and scenario size at most d.
Proof sketch of Lemma 5. The proof is similar to the proof of NP-hardness in Theorem 2. Given
an instance of Exact Cover by d-Sets with universe X and a family C we construct an
instance (F, S, (d−1)n/d) of Minimum Feasible Tileset with F = X and n = |X|. Applying
the equivalence of ﬁnding a feasible tileset of size (d − 1)n/d and ﬁnding an admissible partition
for S of size n/d then gives Lemma 5.
X 
To construct the instance of Minimum Feasible Tileset, we simply set S = d−1
∪
X
X 
( d \ C). Similarly to the reduction used for Theorem 2, the scenarios d−1 enforce that every

admissible partition contains only parts of size exactly d. The constraints Xd \ C enforce that
only sets of C occur in an admissible partition. Hence, each admissible partition is also an exact
d-set cover and vice-versa.
We now consider a more general setting: In the Generalized Minimum Feasible Tileset
problem we are also given a set of symbols and a set of scenarios, but here each scenario may
be a multi-set of symbols (or, equivalently, each scenario is a function S : F → N indicating
the number of copies of each symbol f needed for S). We prove that Generalized Minimum
2
Feasible Tileset can be solved in time O∗ (|F |O(|F | ) ). Note that for this problem the solution
size ℓ may be much larger than |F | and similarly the number of scenarios cannot in general be
bounded in |F |.
2

Theorem 9. Generalized Minimum Feasible Tileset can be solved in time O∗ (|F |O(|F | ) ),
i.e., it is fixed-parameter tractable with respect to |F |.
Proof. Let (F, S, ℓ) be an instance of Generalized Minimum Feasible
Tileset and let k :=

|F |. We will construct an integer linear program (ILP) with k2 = O(k2 ) variables and O∗ (2k )
constraints that is feasible if and only if (F, S, ℓ) admits a feasible tileset with at most ℓ tiles.
Using Kannan’s algorithm (Theorem 4) then completes the proof.
We introduce one variable xs,s′ ≥ 0 for each possible tile type, i.e., for each pair of sym
bols s, s′ ∈ F2 . We interpret xs,s′ as the number of tiles of type s, s′ that the solution will
contain. We begin with the constraint ensuring that we do not use more than ℓ tiles overall:
X

xs,s′ ≤ ℓ

{s,s′ }∈ F2

( )

We need to add constraints to the ILP to ensure that the resulting assignment to the xs,s′ variables corresponds to a feasible tileset, i.e., that each scenario S can be implemented using
the corresponding numbers of tiles of each type. This is the case if and only if there is a
matching from the symbols in S to the tiles that cover all symbols in S. Clearly, in order not
to use too many variables, we do not want to compute a (one-sided perfect) matching for each
scenario S. By Hall’s Theorem, it is instead suﬃcient to ensure that for each subset I ⊂ F of
symbols appearing at least once in scenario S there are at least that many tiles involving these
symbols. If cs,S denotes the number of occurrences of symbol s in scenario S, we obtain the
following constraints:
X
X
cs,S
∀S ∈ S, ∀I ⊆ F
xs,s′ ≥
{s,s′ }∩I6=∅

s∈I

20



In total we use k2 = O(k2 ) variables and 1+ m ·2k + k2 constraints. Using Kannan’s algorithm
for testing feasibility of an ILP with p variables in time O∗ (pO(p) ) (Theorem 4) we get a total
2
running time of O∗ (kO(k ) ).

7

Conclusion

We initiated the study of the Minimum Feasible Tileset problem and exposed an interesting
combinatorial structure. We proved the problem to be NP-complete even in the restricted case
with scenarios of size at most three and APX-hard in general. On the positive side, we showed
that the Minimum Feasible Tileset problem admits a 4/3-approximation algorithm and that
it is ﬁxed-parameter tractable with respect to the number of scenarios and number of symbols.
The latter algorithm works also for the Generalized Minimum Feasible Tileset problem
where each scenario can contain multiple copies of a symbol and we believe that it can be
further generalized to work also for the original assignment problem where also tiles of larger
(but constant) size are allowed. It would be interesting to see whether our other positive results
transfer to this more general setting. We note that our approximation algorithm relies heavily
on the structural observations from Section 2 which do not seem to generalize well. Our integer
linear program for a ﬁxed number of scenarios does not seem easily adaptable either.

References
[1] N. Bansal, A. Caprara, and M. Sviridenko. A new approximation method for set covering
problems, with applications to multidimensional bin packing. SIAM Journal on Computing,
39(4):1256–1278, 2009.
[2] T. Biedl, T. Chan, Y. Ganjali, M. Hajiaghayi, and D. Wood. Balanced vertex-orderings of
graphs. Discrete Applied Mathematics, 148(1):27–48, 2005.
[3] K. Buchin, M. J. van Kreveld, H. Meijer, B. Speckmann, and K. Verbeek. On planar
supports for hypergraphs. Journal of Graph Algorithms and Applications, 15(4):533–549,
2011.
[4] J. Chen, C. Komusiewicz, R. Niedermeier, M. Sorge, O. Suchý, and M. Weller. Polynomialtime data reduction for the subset interconnection design problem. SIAM Journal on
Discrete Mathematics, 29(1):1–25, 2015.
[5] P. Crescenzi. A short guide to approximation preserving reductions. In Proceedings of the
Twelfth Annual IEEE Conference on Computational Complexity (CCC), pages 262–273.
IEEE Computer Society, 1997.
[6] M. Cygan. Improved approximation for 3-dimensional matching via bounded pathwidth
local search. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 509–518, 2013.
[7] H. Dell and D. Marx. Kernelization of packing problems. In Proceedings of the 23rd Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 68–81, 2012.
[8] H. Dell and D. van Melkebeek. Satisﬁability allows no nontrivial sparsiﬁcation unless the
polynomial-time hierarchy collapses. Journal of the ACM, 61(4):23:1–23:27, 2014.

21

[9] Y. Disser, S. Kratsch, and M. Sorge. The minimum feasible tileset problem. In Proceedings
of the 12th Workshop on Approximation and Online Algorithms (WAOA ’14), volume 8952
of LNCS, pages 144–155. Springer, 2014.
[10] Y. Disser and J. Matuschke. Degree-constrained orientations of embedded graphs. Journal
of Combinatorial Optimization, 31(2):758–773, 2016.
[11] D.-Z. Du and Z. Miller. Matroids and subset interconnection design. SIAM Journal on
Discrete Mathematics, 1(4):416–424, 1988.
[12] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006.
[13] A. Frank and A. Gyárfás. How to orient the edges of a graph. Colloquia mathematica
societatis Janos Bolyai, 18:353–364, 1976.
[14] A. Frank and É. Tardos. An application of simultaneous diophantine approximation in
combinatorial optimization. Combinatorica, 7(1):49–65, 1987.
[15] M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of
NP-Completeness. W.H. Freeman and Company, 1979.
[16] G. Gottlob and G. Greco. Decomposing combinatorial auctions and set packing problems.
Journal of the ACM, 60(4):24, 2013.
[17] S. Hakimi. On the degrees of the vertices of a directed graph. Journal of the Franklin
Institute, 279(4):290–308, 1965.
[18] D. S. Johnson and H. O. Pollak. Hypergraph planarity and the complexity of drawing
Venn diagrams. Journal of Graph Theory, 11(3):309–325, 1987.
[19] V. Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete. Information
Processing Letters, 37(1):27–35, 1991.
[20] R. Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of
Operations Research, 12:415–440, 1987.
[21] I. Koutis. Faster algebraic algorithms for path and packing problems. In Proceedings of
the 35th International Colloquium on Automata (ICALP), pages 575–586, 2008.
[22] H. W. Lenstra. Integer programming with a ﬁxed number of variables. Mathematics of
Operations Research, 8:538–548, 1983.
[23] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin
Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer,
2015.
[24] Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer,
5th edition, 2016.
[25] Rodney G. Downey and Micheal R. Fellows. Fundamentals of Parameterized Complexity.
Texts in Computer Science. Springer, 2013.
[26] P. Schuurman and G. J. Woeginger. Approximation schemes–a tutorial.

22

[27] M. Sviridenko and J. Ward. Large neighborhood local search for the maximum set packing
problem. In 40th International Colloquium on Automata, Languages, and Programming
(ICALP), pages 792–803, 2013.
[28] R. van Bevern, I. Kanj, C. Komusiewicz, R. Niedermeier, and M. Sorge. Twins in subdivision drawings of hypergraphs. In Proceedings of the 24th International Symposium on
Graph Drawing & Network Visualization, volume 9801 of LNCS, pages 67–80. Springer,
2016.

23

