Problems that are NP-hard to approximate even when the input graph is regular

Question

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

If you want a combinatorial problem, i'm pretty sure there exist one though I couldn't say which in particular. If you accept cheating answer then you can interpret your planar graph as encoding a Turing machine. — PMercier, Jan 27 at 9:33
You can take any graph you want and add self loops to make it regular. Doing so won't change (for instance) Hamiltonicity. — Lorenzo Najt, Jan 27 at 14:51
Hamiltonian cycle is hard on 3 regular graphs ( even if you insist on three connected and planar). Counting simple cycled will be hard to approximate on such graphs, because you can replace vertices with gadgets that cause an exponential blow up in the proportion of simple cycles that are longest. The gadget used in the triangulation case here arxiv.org/abs/1908.08881 should work. — Lorenzo Najt, Jan 28 at 17:11
(There are certainly simpler examples -- the gadget in that paper was cooked up to control a lot of parameters at once. If you just want to control 3-regularity, maybe iteratively replacing vertices by triangles would work?) — Lorenzo Najt, Jan 28 at 17:27

Cyriac Antony · Accepted Answer · 2020-01-29 07:19:13Z

1

For all $k\geq 3$, the problem maximum induced matching is APX-hard for $k$-regular bipartite graphs. See this paper.

A matching $M$ of a graph $G$ is induced if for every pair of edges $e,e'$ in M, there is no edge between them in $G$.

answered Jan 29 at 7:02

Cyriac Antony

5664 silver badges17 bronze badges

$\begingroup$ Also, maximum induced matching is APX-complete for cubic planar graphs (see sciencedirect.com/science/article/pii/S1570866704000371) $\endgroup$ – Cyriac Antony Jan 29 at 8:47

add a comment |

1 Answer 1