Usuario:Dr Doofenshmirtz/Topic-based authoring

To see that MAX-CLIQUE is in DP, observe that the problem CLIQUE+ :={<G,k> |G has a k+1 clique} is in NP. It is then the case that MAX-CLIQUE is equal to CLIQUE CLIQUE+.

To show that MAX-CLIQUE is DP-hard, we show that there is a polynomial time reduction from C(in the previous part) to MAX-CLIQUE.

Consider a tuple <G1,k1,G2,k2>. We define a pair <G,k> that can be computed from the tuple in polynomial time such that <G1,k1,G2,k2> ∈ C iff <G,k> ∈ MAX-CLIQUE.

Let N1, N2 be respectively the node sets of G1 and G2 and E1, E2 their respective edge relations. Let Kk′ be the clique of size k′.

Consider first the graph G′1:= (N′1,E′1), where N′1:= [1,k1]×N1 and E′1:={((i,u),(i+ 1,v)|i∈[1,k1) and (u,v) ∈ E1}. By construction, no clique of G′1 can be bigger than k1, and it will have a clique of size k1 iff G1 also has a clique of size k1.

For r ∈ N, we extend G′1 to a graph Gr1 by adding an instance of Kr and then an edge from each node in this instance of Kr to each node in the original G′1. The graph Gr1 will now have a clique of size k1+r iff G1 has a clique of size k1, and moreover no clique of Gr1 can be bigger than k1+r. That is,G1 has a clique of size k1, iff the maximum-sized clique in Gr1 has size k1+r.

We now define the graph Gr2(i) first in a similar way to Gr1, replacing k1 with k2, N1 with N2 and E1 with E2, and then in addition (ii) adding a fresh disjoint instance Kk2+r-1.

It will then be the case that G2r has a (k2+r)-clique iff G2 has a k2-clique. Moreover, it is certain that gr2 has a k2+r-1 sized clique and that it has no clique larger thank 2+r. Thus the maximal clique of G2r has size k2+r iff G2 has a k2-clique.

If k1>k2 we can thus take G′:=G01×Gk1-k22, and otherwise G′:=Gk2-k11×G02. [[Categoría:Comunicación técnica]]