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.


  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.


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.

  • $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Jan 19 '15 at 22:17
  • $\begingroup$ 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?". $\endgroup$ – Sasho Nikolov Jan 20 '15 at 7:56
  • $\begingroup$ $\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... $\endgroup$ – Giorgio Camerani Jan 20 '15 at 8:03
  • $\begingroup$ ...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. $\endgroup$ – Giorgio Camerani Jan 20 '15 at 8:03
  • $\begingroup$ 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. $\endgroup$ – Giorgio Camerani Jan 20 '15 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.