How big is the result when reducing from Clique to an NP-Complete sparse language and back again?

Question

Let's assume for the sake of this question that there exists an NP-complete sparse language. Let's call it $L$. So formally, by the definition of a sparse language, if $L_m = \{x \mid x \in L \ \text{and } |x| = m\}$ then $|L_m| = O(m^c)$ for some $c$ as $m$ grows; that is, $L_m$ is polynomially bounded.

So since $L$ is NP-complete, there exists a polynomial-time reduction $f$ from Clique to $L$. So $f:\textit{Clique} \to L$. Of course, since Clique is also NP-complete, there exists a polynomial-time reduction from $L$ to Clique which we'll call $r(s)$. So $r:L \to \textit{Clique}$. We assume there is an encoding of Clique where we can measure the sizes of these encodings.

Let $G_n$ be all graphs of size $n$:

$$ G_n = \{ g \mid g \text{ is a graph and } |g| = n\} $$

Let $L_n$ be the set of all the elements of the sparse language under the reduction from these graphs:

$$ L_n = \{ f(g) \mid g \in G_n\}$$

And finally, let $G'_n$ be all the graphs from the reduction back from those sparse language elements back into Clique:

$$ G'_n = \{ r(s) \mid s \in L_n\}$$

Question: Is $G'_n$ polynomially bounded as $n$ grows? That is, is $G'_n = O(n^k)$ for some fixed constant $k$?

Answer 1

We can say something true that's similar to what you claim.

Formally, define $\text{Clique}$ as the set of all pairs $(G,k)$ where $G$ is a graph, $k$ is a positive integer, and $G$ contains a $k$-clique. Within this subset, we can define $\text{Clique}_n$ to be the subset of $\text{Clique}$ where $G$ has $n$ vertices.

The polynomial-time reduction from $\text{Clique}$ to $L$ converts inputs to the clique problem to inputs to $L$'s decision problem, preserving the answer. In particular, it converts every element of $\text{Clique}$ to an element of $L$, so we can define a function $f\colon \text{Clique} \to L$ that describes part of what the reduction does. (This $f$ does not describe all the reduction does, because the reduction also turns pairs $(G,k) \notin \text{Clique}$ into some kind of objects not in $L$.)

Similarly, the polynomial-time reduction from $L$ to $\text{Clique}$ can be partially described by a function $r\colon L \to \text{Clique}$.

We can use these to define sets $$ A_n = \{f(G,k) : (G,k) \in \text{Clique}_n\} \qquad B_n = \{r(s) : s \in A_n\}. $$ By definition of $f$, $A_n$ is a subset of $L$ and so by definition of $r$, $B_n$ is a subset of $\text{Clique}$.

Then it follows that:

1. Because $f$ is computed by a polynomial-time reduction, its output must be polynomial in size. There must be some polynomial $p_1$ such that for every $n$ and every $(G,k) \in \text{Clique}_n$, the output $f(G,k)$ has size at most $p_1(n)$. Therefore every element of $A_n$ has size at most $p_1(n)$.
2. By definition, there is some polynomial $p_2$ such that for every $n$, there are at most $p_2(n)$ elements of $L$ that have size at most $n$. Since $A_n$ is a set of elements of $L$ with size at most $p_1(n)$, we have $|A_n| \le p_2(p_1(n))$.
3. Since $r$ is a function, we have $|B_n| \le p_2(p_1(n))$.

So we can say that the composition $r \circ f$ maps $\text{Clique}_n$ to a set of polynomially many elements of $\text{Clique}$. (They are not necessarily in $\text{Clique}_n$, though they are all polynomial in size.)

---

Separately, we can use the polynomial-time reduction from $\text{Clique}$ to $L$ to define a cousin of the function $f$ (call it $f^*$) that takes in any pair $(G,k)$ as an input. Its output is not necessarily in $L$: it is in $L$ on elements of $\text{Clique}$, and not in $L$ on other pairs $(G,k)$. There is a similar function $r^*$ which is a cousin to $r$.

Define $G_n$ to be the set of all pairs $(G,k)$ where $G$ has $n$ vertices and $1 \le k \le n$. Then we can define, as before: $$ A_n^* = \{f^*(G,k) : (G,k) \in G_n\} \qquad B_n^* = \{r^*(s) : s \in A_n^*\}. $$ It is still true that $f^*(G,k)$ is polynomial in size, because it's computed by a polynomial-time reduction on an input of length about $n + \log_2 n$. However, the set of possible inputs to $L$'s decision problem has no reason to be polynomially bounded, so the sets $|A_n^*|$ and $|B_n^*|$ could still be exponentially large, just like the set $G_n$.