# Can I reduce from the recognition version of one probem to another without knowing the exact parameter?

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?

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

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'$$.