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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Jun 9, 2021 at 8:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Jun 9, 2021 at 8:52
  • $\begingroup$ 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. $\endgroup$
    – karmanaut
    Commented Jun 9, 2021 at 12:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Jun 9, 2021 at 15:07
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Jun 9, 2021 at 15:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.