Skip to main content

All Questions

Filter by
Sorted by
Tagged with
8 votes
1 answer
330 views

Can a natural graph problem be universally hard?

Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to any polynomial-time recognizable graph class? To avoid degenerated cases, ...
Andras Farago's user avatar