<p>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.</p>

<p>Let $A$ be an algorithm behaving as follows:  </p>

<ul>
<li>The input of $A$ is $G$, together with a positive integer constant $C_1$ (as huge as you wish).</li>
<li>$A$ runs in time polynomial in the size of $G$.</li>
<li><p>The output of $A$ is another graph $H$ having all these properties:</p>

<ul>
<li>The minimum degree of $H$ is equal to or greater than $C_1$.</li>
<li>The $\Delta$ of $H$ is the same as the $\Delta$ of $G$.</li>
<li>$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$).</li>
</ul></li>
</ul>

<p>The existence of $A$ allows us to <em>densify</em> $G$, by increasing its minimum degree to any constant we desire.</p>

<blockquote>
  <p><strong>Questions</strong>:  </p>
  
  <ol>
  <li>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).</li>
  <li>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.  </li>
  </ol>
  
  <p><strong>Motivation</strong>:</p>
  
  <p>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.</p>
</blockquote>

CC BY-SA 3.0
2015-01-19T22:17:41.837Z
From your description it doesn't sound you make the graph denser at all: you seem to say that the ratio of the min degree of $H$ to its size is even less than the ratio of the min degree of $G$ to its size?
Sasho Nikolov
CC BY-SA 3.0
2015-01-20T07:56:36.760Z
Everything you mentioned also takes into account the number of nodes (notice how $n$ is in every expression?). While "dense" may be up for some interpretation, making something *denser* has a very clear meaning: the average degree must increase. I see that as uncontroversial. To be honest, I don't think this is a good question. You are just saying "here is an arbitrary guarantee, what do you think about it?".
Sasho Nikolov
CC BY-SA 3.0
2015-01-20T08:03:00.907Z
$\frac{C_1}{C_2}$ tends to $0$ as $C_1$ grows, so your observation is right. I guess it depends on the definition of _dense_: I'm not sure there is a uniquely accepted definition. Yesterday I was reading a paper where their definition of _dense_ was that the minimum degree is $( \frac{1}{2} + \epsilon) \cdot n$. In other cases a graph with minimum degree $log n$ or $\sqrt n$ is considered dense. While your definition takes into account also the number of nodes. Thus I'm not sure which is the most suitable definition...
Giorgio Camerani
CC BY-SA 3.0
2015-01-20T08:03:25.343Z
...My gut feeling is that a graph with minimum degree $d_{MIN}$ is obviously denser than a graph with maximum degree $d_{MAX} < d_{MIN}$, regardless of the number of nodes of the two graphs (but I could be flat wrong of course). If necessary I'll edit the question.
Giorgio Camerani
CC BY-SA 3.0
2015-01-20T08:10:21.473Z
You are saying: _"the average degree must increase"_, and I fully agree with that. It is precisely what is happening, no? How do you define the average degree? For me, it is defined as $d_{AVG} = \frac{1}{n} \cdot \sum_{i = 1}^{n} d_i$, do you agree? On the other hand, if you define the average degree as $d_{AVG} = \frac{d_{MIN}}{n}$ it is not the case that $d_{AVG}$ is increasing of course.
Giorgio Camerani
CC BY-SA 3.0
2015-01-20T19:45:32.463Z
You are right, if the minimum degree increases then the graph is getting denser. Why do you expect this to help in counting though? Do you have any examples of counting problems where this is the case?
Sasho Nikolov
CC BY-SA 3.0
2015-01-22T08:01:13.190Z
I only have empirical evidence, not theoretical proof. After several experiments, it is a matter of fact that, as the minimum degree increases, the number of all vertex covers is counted faster. This is something expected and not surprising: as almost every algorithm for counting all vertex covers is a variation of the DPLL procedure, when you set some variable to false there are at least $d_{MIN}$ further variables that immediately become true by unit propagation...
Giorgio Camerani
CC BY-SA 3.0
2015-01-22T08:10:42.220Z
...In general I would not expect that this speed-up allows us to escape from exponential time: as I've said in the question, I would only expect that it decreases the exponent a bit. What puzzles me in this case, however, is that $C_1$ is unbounded: it can be as huge as we want. I'm not certain that this fact is insignificant (maybe such unboundedness can be used to get sub-exponential time somehow, I'm not sure we can rule out this possibility).
Giorgio Camerani
<cc.complexity-theory><ds.algorithms><complexity-classes><lower-bounds>
Consequences of the existence of the following algorithm: does it imply any complexity class separation / collapse?
Giorgio Camerani
# Consequences of the existence of the following algorithm: does it imply any complexity class separation / collapse?

(Asked by: username_0 on 2015-01-19)

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**:
>
> 1. 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).
> 2. 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.

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, lower-bounds

> **Comments:**
> **username_1**: From your description it doesn't sound you make the graph denser at all: you seem to say that the ratio of the min degree of $H$ to its size is even less than the ratio of the min degree of $G$ to its size?  
> **username_1**: Everything you mentioned also takes into account the number of nodes (notice how $n$ is in every expression?). While "dense" may be up for some interpretation, making something *denser* has a very clear meaning: the average degree must increase. I see that as uncontroversial. To be honest, I don't think this is a good question. You are just saying "here is an arbitrary guarantee, what do you think about it?".  
> **username_0**: $\frac{C_1}{C_2}$ tends to $0$ as $C_1$ grows, so your observation is right. I guess it depends on the definition of _dense_: I'm not sure there is a uniquely accepted definition. Yesterday I was reading a paper where their definition of _dense_ was that the minimum degree is $( \frac{1}{2} + \epsilon) \cdot n$. In other cases a graph with minimum degree $log n$ or $\sqrt n$ is considered dense. While your definition takes into account also the number of nodes. Thus I'm not sure which is the most suitable definition...  
> **username_0**: ...My gut feeling is that a graph with minimum degree $d_{MIN}$ is obviously denser than a graph with maximum degree $d_{MAX} < d_{MIN}$, regardless of the number of nodes of the two graphs (but I could be flat wrong of course). If necessary I'll edit the question.  
> **username_0**: You are saying: _"the average degree must increase"_, and I fully agree with that. It is precisely what is happening, no? How do you define the average degree? For me, it is defined as $d_{AVG} = \frac{1}{n} \cdot \sum_{i = 1}^{n} d_i$, do you agree? On the other hand, if you define the average degree as $d_{AVG} = \frac{d_{MIN}}{n}$ it is not the case that $d_{AVG}$ is increasing of course.  
> **username_1**: You are right, if the minimum degree increases then the graph is getting denser. Why do you expect this to help in counting though? Do you have any examples of counting problems where this is the case?  
> **username_0**: I only have empirical evidence, not theoretical proof. After several experiments, it is a matter of fact that, as the minimum degree increases, the number of all vertex covers is counted faster. This is something expected and not surprising: as almost every algorithm for counting all vertex covers is a variation of the DPLL procedure, when you set some variable to false there are at least $d_{MIN}$ further variables that immediately become true by unit propagation...  
> **username_0**: ...In general I would not expect that this speed-up allows us to escape from exponential time: as I've said in the question, I would only expect that it decreases the exponent a bit. What puzzles me in this case, however, is that $C_1$ is unbounded: it can be as huge as we want. I'm not certain that this fact is insignificant (maybe such unboundedness can be used to get sub-exponential time somehow, I'm not sure we can rule out this possibility).  

---

## 0 answers

