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

Improve this question
$\endgroup$
2
  • 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, 2011 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, 2011 at 22:13

2 Answers 2

Reset to default
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 .

Improve this answer
$\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

Improve this answer
$\endgroup$
6
  • 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, 2011 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, 2011 at 13:57
  • $\begingroup$ Thanks András, your comment is incorporated in the answer. $\endgroup$
    – Mohammad Al-Turkistany
    Jun 9, 2011 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, 2011 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, 2011 at 16:46

Your Answer

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

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