1
$\begingroup$

I was reading the paper "Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(2), 135-139" and from what I understand, they prove that SET-ECC is NP-complete by constructing a graph G' and showing that (G, k)$\in$ SET-NCC iff (G', k') $\in$ SET-ECC, with $k'= k(e + 1) + e$. However, the size of the ECC of G' could be smaller than k', and in fact, we don't know exactly what it is. I just want to confirm that I understood the paper correctly, so my question is, for a reduction of this type, is it enough to have an upper bound of k', as long as k' depends on k?

$\endgroup$
1
  • $\begingroup$ You do know the exact parameter: $k' = k(e+1)+e$. $\endgroup$ Dec 26 '21 at 9:54
0
$\begingroup$

A mapping $f$ from instances of a decision problem $A$ to instances of a decision problem $B$ is a reduction if $x \in A$ iff $f(x) \in B$.

In your case, instances of both problems are of the form $(G,k)$. Such instances are Yes instances if there is a clique-cover of $G$ of size at most $k$.

Thus a function mapping $(G,k)$ to $(G',k')$ is a reduction between SET-NCC and SET-ECC if the following holds: $G$ has a node-clique-cover of size at most $k$ iff $G'$ has an edge-clique-cover of size at most $k'$.

$\endgroup$

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.