Information Technology Reference
In-Depth Information
v
v
j
,b
in the constructed graph
G
. Every vertex in
L
2
is connected to exactly one
vertex in
L
3
.Vertex
v
v
i
,b
in
L
2
is connected to
v
v
i
,a
in
L
3
. All the vertices in
L
3
are connected to the sink vertex
t
in
L
4
. All the edges between
L
0
and
L
1
and
all the edges between
L
1
and
L
2
have a capacity of 1. All the other edges have
capacity of
|
E
|
.
As explained above, all inputs for FLOW-EDGE-SUBSET are given with
regard to
A
1
.Thesetof
A
1
's edges
E
1
is (
v
v
i
,b
,v
v
i
,a
), for all possible
i
.Allof
the other edges belong to
A
2
, and in the input given to FLOW-EDGE-SUBSET,
A
2
declares all its edges. The payment constant
c
is chosen such that
c<
1
|V |
+
|E|
.
We demonstrate building the layer graph in Figure 2. The graph on the left of
Figure 2 is the input for the VERTEX-COVER, while the graph on the right is
the generated FLOW-EDGE-SUBSET layer graph.
Fig. 2.
Reducing VERTEX-COVER to FLOW-EDGE-SUBSET
The intuition behind this construction is simple.
A
1
's edges in the constructed
graph represent vertices in the original graph
G
.
A
1
must choose a subset of edges
to report to the mechanism. Let
E
1
⊂
E
1
be the subset of edges that
A
1
chooses
to declare. Each such choice can also be seen as a choice of a subset of vertices
in
G
. These vertices cover certain edges in the original graph. We later refer to
these edges as
EC
G,E
1
.The
v
e
i
vertices in
L
1
represent the edges in
G
.
The construction makes sure that the mechanism can only send flow from
s
to
v
e
i
if
e
i
is an edge covered by
E
1
(
e
i
∈
EC
G,E
1
). In fact, a flow going through
one of
A
1
's edges (
v
v
i
,b
,v
v
i
,a
) can only originate from a
v
e
j
vertex that represents
an edge
e
j
that covers
v
i
.
Thus
A
1
's valuation is limited by the number of edges covered by his chosen
set of vertices, or in other words by
. Therefore,
A
1
would choose
E
1
|
EC
G,E
1
|
