0
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – PMercier
    Jan 27 '20 at 9:33
  • $\begingroup$ You can take any graph you want and add self loops to make it regular. Doing so won't change (for instance) Hamiltonicity. $\endgroup$
    – Lorenzo Najt
    Jan 27 '20 at 14:51
  • $\begingroup$ @LorenzoNajt Oh, I meant only simple graphs. $\endgroup$
    – Cyriac Antony
    Jan 27 '20 at 16:11
  • $\begingroup$ 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. $\endgroup$
    – Lorenzo Najt
    Jan 28 '20 at 17:11
  • $\begingroup$ (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?) $\endgroup$
    – Lorenzo Najt
    Jan 28 '20 at 17:27
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.