other hand, asks us to assign exactly one label to each vertex so to maximize the
total number of covered edges.
The Min-Rep problem, ﬁrst introduced in [74], can be viewed as a variant of
LabelCover-Min that has shown itself to be a simpler starting point for many
hardness results, e.g. [24, 33, 37, 47]. One formalization of the problem is as follows.
The ﬁrst part of the input consists of a bipartite graph with vertex set V and edge
set E. Within each bipartition, vertices are further partitioned into equal-sized sub-
sets, which are called supervertices. The set of all supervertices is denoted
ˆ
V . We
then establish an equivalence relation between edges based on whether or not their
endpoints fall in exactly the same pair of supervertices. The non-empty equivalence
classes are called the graph’s superedges, the set whereof is denoted
ˆ
E. Thus, an
instance of Min-Rep can be deﬁned as a 4-tuple (V, E,
ˆ
V ,
ˆ
E), deﬁning the vertices,
edges, supervertices, and superedges of the instance.
2
For a subset V
0
⊆ V of vertices, we say that V
0
covers a superedge ˆe ∈
ˆ
E if there
exists an edge e ∈ ˆe such that both endpoints of e are in V
0
. Finally, the set of
feasible solutions for a given Min-Rep instance are exactly those vertex subsets that
cover every superedge in
ˆ
E. As the name Min-Rep suggests, the objective is to ﬁnd
a feasible solution V
0
⊆ V of minimal cardinality.
Problem 1.4 (Min-Rep): Given a 4-tuple (V, E,
ˆ
V ,
ˆ
E) representing a bipartite
graph G = (V, E) with supervertex set
ˆ
V and superedge set
ˆ
E, ﬁnd a minimal-
cardinality subset V
0
⊆ V such that for each superedge ˆe ∈
ˆ
E, both endpoints of
some e ∈
ˆ
E are included in V
0
.
As shown in [74], Min-Rep has no 2
log
1−
n
approximation algorithm unless NP ⊆
DTIME[n
polylogn
]. LabelCover-Max has since been shown to admit a (slightly
stronger) hardness of 2
log
1−1/ log log
1/2−
n
under similar complexity conjectures [49]. To
2
Although the set of superedges is already implied by V , E, and
ˆ
V , in this thesis we treat it as
part of the input for convenience.
8