1
$\begingroup$

Given an (undirected) graph G, let i(G) be the number of independent sets [1] in G. Given also a threshold th, the problem is to decide whether $i(G) > th$.

Are there known values of th for which the problem is known to be intractable?

[1] https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you mean independent sets here or maximal independent sets? $\endgroup$
    – JoshuaZ
    Jan 31, 2023 at 12:52
  • 1
    $\begingroup$ The problem "given $G$ and an integer $th$, are there at least $th$ independent sets in $G$" does not admit efficient randomized algorithms unless $\mathsf{NP}=\mathsf{RP}$ by a well-known result of Allan Sly [FOCS 2010]. Are you asking for a specific value of $th=th(n)$, which necessarily grows with the number of vertices? $\endgroup$
    – Jason Gaitonde
    Jan 31, 2023 at 16:24

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.