# Triangle detection hardness in regular graphs

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.

• 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: 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. Jun 9 '21 at 8:33
• 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. Jun 9 '21 at 8:52
• 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. Jun 9 '21 at 12:31
• 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. Jun 9 '21 at 15:07
• 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. Jun 9 '21 at 15:50