9
$\begingroup$

I would like to have a bound on the cardinality of the set of unit disk graphs with $N$ vertices. It is known that checking whether a graph is a member of this set is NP-hard. Does this lead to any lower bound on the cardinality, assuming P $\neq$ NP?

For example, suppose there is an ordering on all graphs with $N$ vertices. Would NP-hardness then imply the cardinality exceeds $2^N$, in that otherwise you could test for membership in polynomial time by doing a binary search through the set? I think this would assume that you have somehow stored the set in memory... Is this allowed?

Defintion: A graph is a unit disk graph if each vertex can be associated with a unit disk in the plane, such that vertices are connected whenever their disks intersect.

Here is a reference on NP-hardness of membership testing for unit disk graphs: http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf

$\endgroup$
  • 1
    $\begingroup$ I am wondering, is there an example where this technique provides the best known lower bound on the size of some set? That would be a cool indirect combinatorial application of complexity theory. $\endgroup$ – Sasho Nikolov Jun 9 '11 at 16:04
  • $\begingroup$ Thank you for your kind assistance. Both answers were helpful and insightful; I would have accepted either one in the absence of the other. $\endgroup$ – David Choi Jun 9 '11 at 22:13
11
$\begingroup$

I'm not sure if you're asking this question for the technique or for the answer, but there is a recent paper by McDiarmid and Mueller where they show the number of (labeled) unit-disk graphs on $n$ vertices is $2^{(2 + o(1))n}$; see http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf .

$\endgroup$
13
$\begingroup$

Mahaney’s Theorem states that sparse NP-complete sets exist iff P=NP. Therefore, assuming $P \neq NP $ implies a super-polynomial lower bound on the number of instances of size $n$ in $NP$-complete sets, for infinitely many $n$. That is, if $P \neq NP$, then any $NP$-complete set must have some $\epsilon \gt 0$ such that for infinitely-many integers $n\ge 0$, the set contains at least $2^{n^{\epsilon}}$ strings of length $n$.

H. Buhrman and J. M. Hitchcock proved the lower bound ($2^{n^{\epsilon}}$) is tight, unless the polynomial hierarchy collapses.

[1] H. Buhrman and J. M. Hitchcock, NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly, In IEEE Conference on Computational Complexity, pages 1–7, 2008

[2] Eric Allender, A Status Report on the P Versus NP Question, Advances in Computers, Volume 77, 2009, Pages 117-147

$\endgroup$
  • 4
    $\begingroup$ [Mah82] S. R. Mahaney. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis, Journal of Computer and System Sciences 25:130-143, 1982. $\endgroup$ – Marzio De Biasi Jun 9 '11 at 7:06
  • 2
    $\begingroup$ Each NP-complete set has countably infinite cardinality. You probably meant that P≠NP implies a super-polynomial lower bound on the number of instances of size $n$, for infinitely many $n$. Note also that $2^{(\log n)^2}$ is super-polynomial without being of the form you give. $\endgroup$ – András Salamon Jun 9 '11 at 13:57
  • $\begingroup$ Thanks András, your comment is incorporated in the answer. $\endgroup$ – Mohammad Al-Turkistany Jun 9 '11 at 15:15
  • $\begingroup$ @Mohammad: make the lower bound $2^{\omega(\log n)}$, or $n^{\omega(1)}$: that's what superpolynomial means. $\endgroup$ – Sasho Nikolov Jun 9 '11 at 16:01
  • 1
    $\begingroup$ @Sasho, H. Buhrman and J. M. Hitchcock proved the lower bound ($2^{n^{\epsilon}}$) I mentioned in my answer, unless the polynomial hierarchy collapses. H. Buhrman and J. M. Hitchcock, NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly, In IEEE Conference on Computational Complexity, pages 1–7, 2008 $\endgroup$ – Mohammad Al-Turkistany Jun 9 '11 at 16:46

Your Answer

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

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