Questions tagged [bounded-degree]
The bounded-degree tag has no usage guidance.
2
questions
20
votes
2answers
1k views
Is feedback vertex set problem is solvable in polynomial time for 3-degree bounded graphs?
Feedback Vertex Set is NP-complete for general graphs. It is known to be NP-complete for degree-8 bounded graphs due to a reduction from vertex cover.
The Wikipedia article says that it is poly-time ...
21
votes
1answer
396 views
Random functions of low degree as a real polynomial
Is there a (reasonable) way to sample a uniformly random boolean function $f:\{0,1\}^n \to \{0,1\}$ whose degree as a real polynomial is at most $d$?
EDIT: Nisan and Szegedy have shown that a ...
