Are there graph problems which are NP-hard to approximate even when the input graph is regular?
For instance, are there optimization problems that are NP-hard to approximate within $O(n^\epsilon)$ even when the input graph is regular?
PS: The input graph is a simple undirected graphs