- We can rewrite xy as ((x + y)2 – x2 – y2)/2, and hence compute xy using three calls to our square function, and 4 other operations.
- We construct a new graph G’ = (V, E’) where E’ contains every pair {x, y} of vertices of G that is NOT an edge of G (that is, every {x, y} such that {x, y} ∉ E), and find the largest clique in G’. Because every subset W of V that is a clique in G’ is an independent set in G, and every subset W of V that is an independent set in G is a clique in G’, the largest clique in G’ is the largest independent set in G.
- Given G, we contruct a graph G’ by adding one vertex ve for each edge e ∈ E, and connecting this vertex to the endpoints of e. That is, if e = {x, y} then we add the edges {ve, x} and {ve, y}. This construction is illustrated below: the graph on top is G, and the bottom graph is G’.
Suppose that G has a vertex cover W with K vertices. The same K vertices will be a dominating set in G’: a vertex of G’ that is not in W is either (1) a vertex from G that’s the endpoint of an edge of G, whose other endpoint must be in W, or (2) one of the new vertices ve, which is connected to both endpoints of the edge e of G, and hence to a member of W.
Finally suppose that G’ has a dominating set W’ with K vertices. We construct a vertex cover W of G by choosing
- every element of W’ that is a vertex of G.
- one of the endpoints of the edge e, for every element ve of W’.
Consider an edge e of G: the vertex ve of G’ was dominated, which means that either it was in W’ (and so W will contain one of the endpoints of e), or one of its two neighbours (an endpoint of e) is in W. This means W is a vertex cover of G.