2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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
    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
    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
    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
    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
    Jun 9, 2021 at 15:50

0

Reset to default

Your Answer

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