2
$\begingroup$

In the paper The diameter of random regular graphs, Bollobás and Fernandez De La Vega give asymptotic lower and upper bounds on the diameter $d$ of random $r$-regular graphs. Roughly, the lower bound is $\Theta(log_{r-1}n)$, while the upper bound is $\Theta(log_{r-1}(nlogn))$, where $n$ is the number of nodes of the graph.

I would like to know (even just empirical) lower and upper bounds on the diameter of non-random $3$-regular graphs. More precisely, such non-random $3$-regular graphs in which I'm interested are those arising after reducing practical real world problem instances (which are known to be structured instead of random) to the $\sharp P$-complete problem $\sharp3$-regular Vertex Cover. In other words, suppose you have a real-world instance of a $NP$-complete problem, and suppose you want to count its solutions: following a chain of reductions, you come out with a $3$-regular graph $G$, whose number of vertex covers encodes the number of solutions of your initial instance.

Questions

  1. How is $G$? Is it still structured, as the original instance? Or did it destroyed the initial structure?
  2. If $G$ is structured, which are the lower bound and the upper bound on its diameter? Do the bounds given by Bollobás and Fernandez De La Vega still hold? Or are such bounds completely different in the structured case?
  3. Does there exist any automated tool (along the lines of ToughSAT) that, given an instance of a $NP$-complete problem, produces the graph $G$?
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ (apologies for the off-topic comment): @Walter, I had a question related to counting solns to NP-hard problems, and was wondering if I could email you directly ? unfortunately, your registered email bounced, so maybe you could email me ? (my email is on my profile page) $\endgroup$
    – Suresh Venkat
    Commented Aug 23, 2011 at 5:10
  • $\begingroup$ @Suresh: It would be a real pleasure to engage a conversation with you on counting solutions of NP-hard problems. Surprisingly, I happen to have something to ask you as well. I've just sent you an e-mail from my real address. $\endgroup$
    – Giorgio Camerani
    Commented Aug 23, 2011 at 6:58

1 Answer 1

Reset to default
4
$\begingroup$

A lower bound of approximately $\log_2 n$ still follows for arbitrary 3-regular graphs, based simply on the fact that there are at most $3\times 2^i$ different paths of length $i$ from any given starting vertex and one needs the diameter to be large enough to give a different path to each of the $n$ vertices. The random graph example that you mention (or the example of a complete binary tree with some extra edges thrown in to make it 3-regular) shows that this is tight to within a constant factor, and I'm pretty sure the actual lower bound is really $(1+o(1))\log_2 n$.

As for an upper bound: there exist 3-regular graphs with diameter $\Omega(n)$, for instance the Möbius ladders.

If you want to know the diameters of graphs coming from specific hardness constructions, you'd have to look at the details of those constructions, but my guess is that in most such cases it would be straightforward to tack on either a large binary tree or a large ladder in order to make the diameter as small or as large as you want without much changing the hardness of the instance.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm focusing on the last part of your answer. Are you suggesting that, given whatever initial instance, it is possible to build the graph $G$ in such a way that the diameter is as large as we want? I need $G$ to have diameter $\Theta(n)$ (i.e. I need $G$ to be a large ladder): is it always possible? If yes, this would have extremely important consequences. $\endgroup$
    – Giorgio Camerani
    Commented Aug 23, 2011 at 8:07
  • $\begingroup$ Well, obviously it depends on the specific problem. But in many hardness constructions there's likely to be free adjacencies at which one could attach a ladder, which would have predictable consequences for the decision problem you're trying to solve. It's hard to be any less vague without knowing which NP-complete problem and which reduction you actually care about. $\endgroup$
    – David Eppstein
    Commented Aug 23, 2011 at 16:25
  • $\begingroup$ Let's say that the NP-complete problem is SAT, and that the reduction chain is SAT to 3SAT, then to #3SAT, then to Permanent, then to 01-Permanent, then to #Monotone-2SAT, then to #Vertex Cover, then to #3-regular Vertex Cover. However, I've realized that having diameter $d \in \Theta(n)$ is not sufficient for my purposes: it must also be the case that the edges are scattered almost uniformly among the $d$ levels. In other words, what I actually need is that the number of edges at each of the $d$ levels is constant, or at most upper bounded by $log(n)$... $\endgroup$
    – Giorgio Camerani
    Commented Aug 23, 2011 at 21:24
  • $\begingroup$ ... So I'm no longer sure that attaching a ladder would suffice. Do you have any clue on the possibility (or not) to build $G$ in such a way that the number of edges at each of the $d$ levels is upper bounded by $log(n)$? $\endgroup$
    – Giorgio Camerani
    Commented Aug 23, 2011 at 21:30
  • $\begingroup$ That seems much more unlikely. If you could reduce to a graph in which some BFS tree had $O(\log_n)$ vertices per level, then it would have treewidth $O(\log n)$ and many NP-complete problems could be solved in polynomial time on it. So to me this is a strong reason for believing that no such reduction exists. $\endgroup$
    – David Eppstein
    Commented Aug 24, 2011 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.