<p>For all <span class="math-container">$k\geq 3$</span>, the problem maximum induced matching is APX-hard for <span class="math-container">$k$</span>-regular bipartite graphs. See <a href="https://www.sciencedirect.com/science/article/pii/S0304397513000893" rel="nofollow noreferrer">this</a> paper. </p>

<p>A matching <span class="math-container">$M$</span> of a graph <span class="math-container">$G$</span> is induced if for every pair of edges <span class="math-container">$e,e'$</span> in M, there is no edge between them in <span class="math-container">$G$</span>.</p>

CC BY-SA 4.0
2020-01-29T08:47:02.623Z
Also, maximum induced matching is APX-complete for cubic planar graphs (see https://www.sciencedirect.com/science/article/pii/S1570866704000371)
Cyriac Antony
CC BY-SA 4.0
2020-01-29T07:02:35.437Z
2020-01-29T07:19:13.990Z
2020-01-29T07:19:13.990Z
Cyriac Antony
<p>Are there graph problems which are NP-hard to approximate even when the input graph is regular?</p>

<p>For instance, are there optimization problems that are NP-hard to approximate within <span class="math-container">$O(n^\epsilon)$</span> even when the input graph is regular?</p>

<p>PS: The input graph is a simple undirected graphs</p>

CC BY-SA 4.0
2020-01-27T09:33:58.633Z
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.
ULechine
CC BY-SA 4.0
2020-01-27T14:51:27.333Z
You can take any graph you want and add self loops to make it regular. Doing so won't change (for instance) Hamiltonicity.
Elle Najt
CC BY-SA 4.0
2020-01-27T16:11:49.627Z
@LorenzoNajt  Oh, I meant only simple graphs.
Cyriac Antony
CC BY-SA 4.0
2020-01-28T17:11:01.447Z
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 https://arxiv.org/abs/1908.08881 should work.
Elle Najt
CC BY-SA 4.0
2020-01-28T17:27:42.780Z
(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?)
Elle Najt
CC BY-SA 4.0
2020-01-29T04:29:51.430Z
@LorenzoNajt Please post your comment as an answer.
Cyriac Antony
CC BY-SA 4.0
2020-06-11T06:04:52.573Z
Acyclic Matching Problem is APX-complete also for regular graphs. 
See [this paper](https://link.springer.com/chapter/10.1007/978-3-030-48966-3_31).
Amir Nikabadi
CC BY-SA 4.0
2020-06-11T07:29:06.317Z
@AmirNikabadi Please post it as an answer (preferably with a brief description of the problem to keep it self contained)
Cyriac Antony
<graph-theory><approximation-hardness>
Problems that are NP-hard to approximate even when the input graph is regular
Cyriac Antony
# Problems that are NP-hard to approximate even when the input graph is regular

(Asked by: username_0 on 2020-01-27)

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

**Tags:** graph-theory, approximation-hardness
> **Comments:**
> **username_1**: 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.  
> **username_2**: You can take any graph you want and add self loops to make it regular. Doing so won't change (for instance) Hamiltonicity.  
> **username_0**: @LorenzoNajt  Oh, I meant only simple graphs.  
> **username_2**: 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 https://arxiv.org/abs/1908.08881 should work.  
> **username_2**: (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?)  
> **username_0**: @LorenzoNajt Please post your comment as an answer.  
> **username_3**: Acyclic Matching Problem is APX-complete also for regular graphs.  See [this paper](https://link.springer.com/chapter/10.1007/978-3-030-48966-3_31).  
> **username_0**: @AmirNikabadi Please post it as an answer (preferably with a brief description of the problem to keep it self contained)  

---

## 1 answers

### Answer by username_0 on 2020-01-29. Score: 1

For all $k\geq 3$, the problem maximum induced matching is APX-hard for $k$-regular bipartite graphs. See [this](https://www.sciencedirect.com/science/article/pii/S0304397513000893) 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$.

> **Comments:**
> **username_0**: Also, maximum induced matching is APX-complete for cubic planar graphs (see https://www.sciencedirect.com/science/article/pii/S1570866704000371)  

---

