Questions tagged [bounded-degree]
The bounded-degree tag has no usage guidance.
2
questions
21
votes
2answers
1k views
Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?
Feedback Vertex Set (FVS) 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 ...
21
votes
1answer
422 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 ...
