3
$\begingroup$

Assume the following Language:
UNARY-CLIQUE= $\{(G=(V,E),1^k) \mid G$ is an undirected graph and there is a clique of size $k$ in $G\}$
I'm trying to determine whether this language belongs to NP complete or not, my first assumption was that it is NP complete as its basically the definition of CLIQUE with the slight change that the integer $K$ is given as a string of 1's.


So, my first attempt was to do a reduction from CLIQUE to UNARY-CLIQUE.
This is the point I encountered an issue, the trivial approach would be defining a function that goes like this:
$F=$"on input $(G,K)$, do:
1. (assuming the input is always of a valid form of a graph and integer) output the pair $(G, 1111....1)$ so that $1$ appears $k$ times."

After further thinking I've came to the conclusion that this function is actually not a valid function as if $k$ is exponential writing $1 k$ times will be an exponential operation which will make the function not polynomial.

First, am I correct in my assumption?
And second, will this solution I thought about fix the problem:
$F="$on input $(G,k)$ do:
1. count the number of vertices in $G$.
2. if $k >$ number of vertices, output $(G,111...1)$ ,$1$ appears $|V|+1$ times.
3. if $k \leq$ number of vertices, output $(G,1111...1)$, $1$ appears $k$ times."

polynomial correctness:
1. is $o(n)$ polynomial to the input
2. is $o(n)$ comparing $2$ numbers represented binary(for example)
3. because we know $k \leq |v|$ writing $1$ $k$ times will be polynomial to the input because input size is bigger than $|v|$."

reduction correctness:
the reduction correctness itself is very trivial as CLIQUE and UNARY-CLIQUE work in the same way regarding the input.(at least its trivial for me so I pass on elaborating on it).

Does this seem right to you? are there any flaws in the way I think ?
*Keep in mind that this is very high level speaking and I dont want to get into the real low level machine implementations, just need to see that my main idea is correct.

$\endgroup$
  • $\begingroup$ You've shown that ${UNARY-CLIQUE}\le_P {CLIQUE}$ $\endgroup$ – AlexR May 26 '15 at 15:46
1
$\begingroup$

UNARY-CLIQUE∈NPC

V = "On input ((G, 0^k), c), where G= (V, E) is an undirected graph, 2≤k≤|V| and c is a set of nodes:
1. Test whether c is a set of k nodes in G.
2. Test whether G contains all edges connecting nodes in c.
3. If both pass, accept; otherwise, reject."
We showed a poly-time verifier, therefore UNARY-CLIQUE∈NP.

Reduction from CLIQUE: Given graph G=(V,E) and 2≤k≤|V|, output (G,0^k).
If G (input) has a clique of size k -> G (output) has a clique of size k.
If G (input) doesn't have a clique of size k -> G (output) doesn't have a cliques of size k.
This reduction is polynomial in respect to the input length. The input length is comprised of V=O(|V|), E=[O(|V|),O(|V|2)] and k=O(log|V|) (k is bounded by |V| and is binary-encoded). The output length is V=O(|V|), E=[O(|V|),O(|V|2)] and 0^k=O(|V|).

We showed CLIQUE ≤p UNARY-CLIQUE, therefore UNARY-CLIQUE∈NPC.

QED.

$\endgroup$
  • $\begingroup$ Welcome to math.SE! This page should give you a start at learning how to typeset mathematics here so that your posts say what you want them to, and also look good. Cheers! $\endgroup$ – man and laptop May 27 '15 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.