<p>Consider a tripartite graph over <span class="math-container">$n^{1-\epsilon}$</span> vertices each in sets <span class="math-container">$I, J, K$</span>. Suppose we impose a constraint that every vertex has degree <span class="math-container">$n^\epsilon/c$</span> for some constant <span class="math-container">$\epsilon &gt; 0$</span> and constant integer <span class="math-container">$c \geq 2$</span>. The edges are present between vertices in <span class="math-container">$I$</span> and <span class="math-container">$J$</span>, <span class="math-container">$J$</span> and <span class="math-container">$K$</span>, and <span class="math-container">$I$</span> and <span class="math-container">$K$</span>. This means that the total number of edges in the graph is <span class="math-container">$m = 3 \cdot n^{1-\epsilon} \cdot \Theta(n^\epsilon) = \Theta(n)$</span>.</p>
<p>Is it known that exact triangle detection is hard (i.e it requires super-linear time) for regular graphs (i.e each vertex has the same degree)? I am aware that triangle detection is hard in general (requires <span class="math-container">$\Omega(n^{1+\delta})$</span> time where <span class="math-container">$\delta$</span> is conjectured to be as large as <span class="math-container">$1/3$</span>) but I am looking for references on hardness/conjectures for regular graphs.</p>

CC BY-SA 4.0
2021-06-09T08:33:52.853Z
There are methods to add gadgets to make the graph regular, however, they usually blow up the number of vertices of the graph, e.g. here you can find a recent result of mine for an independent set which also works for triangle finding in bounded degree regular graphs: https://www.sciencedirect.com/science/article/abs/pii/S0020019021000375
, that paper does not completely answer your question though. But there is a small difference between the two problem, in the one I considered, I tried to show hardness for every d (d-regular), but I think you are happy if it is hard in any d-regular graph.
Saeed
CC BY-SA 4.0
2021-06-09T08:52:44.970Z
For instance for your case, for each vertex $u$ of degree < d take a complete bipartite graph with each partition having d-1 vertices, then connect $u$ to vertices of the bipartite graph to make its degree $d$. In the end, some of the vertices of bipartite graphs have degree d-1, then for every d such vertices, create a new vertex $v$, connect those d vertices to $v$. At the very end there might remain $t\le d-1$ vertices of degree $d-1$, you can add $O(d)$ many new vertices and connect them to that vertices to make the whole graph regular. Bipartite graphs don't add any triangle.
Saeed
CC BY-SA 4.0
2021-06-09T12:31:53.470Z
Thank you for the reference. There is one critical difference though. For MIS, the problem is hard even when $d$ is a constant but for triangle detection, it is trivial when $d$ is a constant because you can simply compute all open $2$-paths and check if there is a triangle or not. When $d$ is not a constant, your gadget construction may take super-linear time.
karmanaut
CC BY-SA 4.0
2021-06-09T15:07:12.400Z
yes, that's a subtle difference between the two. Anyways, I think it should be doable by this idea: let suppose the average degree is d and maximum degree is t=O(d) (in the original graph), and let's say there are n vertices. Add a pool of O(n) vertices W, and greedily assign them to the vertices of degree < t in G: it means take one vertex u with d_u < t, connect it to the first available t-d_u vertices of W, a vertex of W is available if its degree is less than t. Continue this to cover all vertices of G. At the end O(t) vertices of W will have degree < t but you can handle it.
Saeed
CC BY-SA 4.0
2021-06-09T15:50:48.220Z
I've noticed the above construction is bogus, since it creates new triangles, but I'll leave it since I think idea around this should work.
Saeed
<ds.algorithms><np-hardness><lower-bounds>
Triangle detection hardness in regular graphs
karmanaut
# Triangle detection hardness in regular graphs

(Asked by: username_0 on 2021-06-08)

Consider a tripartite graph over $n^{1-\epsilon}$ vertices each in sets $I, J, K$. Suppose we impose a constraint that every vertex has degree $n^\epsilon/c$ for some constant $\epsilon > 0$ and constant integer $c \geq 2$. The edges are present between vertices in $I$ and $J$, $J$ and $K$, and $I$ and $K$. This means that the total number of edges in the graph is $m = 3 \cdot n^{1-\epsilon} \cdot \Theta(n^\epsilon) = \Theta(n)$.

Is it known that exact triangle detection is hard (i.e it requires super-linear time) for regular graphs (i.e each vertex has the same degree)? I am aware that triangle detection is hard in general (requires $\Omega(n^{1+\delta})$ time where $\delta$ is conjectured to be as large as $1/3$) but I am looking for references on hardness/conjectures for regular graphs.

**Tags:** ds.algorithms, np-hardness, lower-bounds

> **Comments:**
> **username_1**: There are methods to add gadgets to make the graph regular, however, they usually blow up the number of vertices of the graph, e.g. here you can find a recent result of mine for an independent set which also works for triangle finding in bounded degree regular graphs: https://www.sciencedirect.com/science/article/abs/pii/S0020019021000375 , that paper does not completely answer your question though. But there is a small difference between the two problem, in the one I considered, I tried to show hardness for every d (d-regular), but I think you are happy if it is hard in any d-regular graph.  
> **username_1**: For instance for your case, for each vertex $u$ of degree < d take a complete bipartite graph with each partition having d-1 vertices, then connect $u$ to vertices of the bipartite graph to make its degree $d$. In the end, some of the vertices of bipartite graphs have degree d-1, then for every d such vertices, create a new vertex $v$, connect those d vertices to $v$. At the very end there might remain $t\le d-1$ vertices of degree $d-1$, you can add $O(d)$ many new vertices and connect them to that vertices to make the whole graph regular. Bipartite graphs don't add any triangle.  
> **username_0**: Thank you for the reference. There is one critical difference though. For MIS, the problem is hard even when $d$ is a constant but for triangle detection, it is trivial when $d$ is a constant because you can simply compute all open $2$-paths and check if there is a triangle or not. When $d$ is not a constant, your gadget construction may take super-linear time.  
> **username_1**: yes, that's a subtle difference between the two. Anyways, I think it should be doable by this idea: let suppose the average degree is d and maximum degree is t=O(d) (in the original graph), and let's say there are n vertices. Add a pool of O(n) vertices W, and greedily assign them to the vertices of degree < t in G: it means take one vertex u with d_u < t, connect it to the first available t-d_u vertices of W, a vertex of W is available if its degree is less than t. Continue this to cover all vertices of G. At the end O(t) vertices of W will have degree < t but you can handle it.  
> **username_1**: I've noticed the above construction is bogus, since it creates new triangles, but I'll leave it since I think idea around this should work.  

---

## 0 answers

