Let $G$ be a $3$-regular graph. Let $O$ be the number of vertex covers of $G$ having odd cardinality, and let $E$ be the number of vertex covers of $G$ having even cardinality. Let $\Delta = O - E$. Computing $\Delta$ is $\#P$-hard.
Let $A$ be an algorithm behaving as follows:
- The input of $A$ is $G$, together with a positive integer constant $C_1$ (as huge as you wish).
- $A$ runs in time polynomial in the size of $G$.
The output of $A$ is another graph $H$ having all these properties:
- The minimum degree of $H$ is equal to or greater than $C_1$.
- The $\Delta$ of $H$ is the same as the $\Delta$ of $G$.
- $H$ has a number of nodes equal to $C_2 \cdot n$, where $n$ is the number of nodes of $G$, and $C_2$ is another constant (much bigger than $C_1$, but still constant in the size of $G$).
The existence of $A$ allows us to densify $G$, by increasing its minimum degree to any constant we desire.
Questions:
- The question that interests me most is the following: what are the consequences of the existence of $A$? Does its existence implies some complexity class separation / collapse? My sensation is that it does not, but at the same time that maybe its existence could be nevertheless interesting under some point of view (I feel that just because I'm unaware of any known algorithm behaving like it).
- Another question is: does computing $\Delta$ (or also $O + E$) has been studied for such graphs? My sensation is of course that by increasing the minimum degree the instance gets easier and easier (maybe it is still exponential time, but with the degree of the exponent which gets lower and lower as the minimum degree gets higher and higher). I wonder if there is a point at which $C_1$ is so astronomic that the instance becomes solvable in sub-exponential time (has anyone studied that?). The limitation of $A$ is that the number of nodes of $H$ grows faster than the minimum degree, so you can never make the minimum degree be a non-constant function of the number of nodes.
Motivation:
My motivation is that a recently developed, very promising research avenue relates the existence / non-existence of algorithms to the existence / non-existence of lower bounds (and thus to complexity class separation / collapse). Of course the algorithm $A$ described here is not the same kind of algorithm usually described in those papers, as it does not solve the given instance: it just reduces it to another instance having a certain property. Nevertheless I wonder if it can fit into the global picture in some way.