# Is it NP complete to decide whether a graph has $k$ disjoint triangles?

I'm trying to prove that $$k\text{-Matching}\le_p k\text{-Disjoint-Triangles}$$ but I was told that the $k\text{-Matching}$ (decide whether a graph has a matching of size $k$ ) can be solve in polynomial time. Then I'm stuck here.

Could anyone help me out here?

• Try applying the definition. See if you can figure out what you need to prove. It will probably help to know that there is an algorithm for k-Matching. – D.W. May 11 '18 at 17:27
• @D.W. Apply the definition of k-Matching or k-Disjoint-Triangles? – Mengfan Ma May 11 '18 at 17:37
• @D.W. I have tried but I still couldn't come up with a good solution :( – Mengfan Ma May 11 '18 at 17:41

For the special case where $$n$$ is a multiple of 3 and $$k=n/3$$, this is the PARTITION-INTO-TRIANGLES problem, which is proved to be NP-complete here.

The idea is to reduce 3-DIMENSIONAL-MATCHING (3DM) to PARTITION-INTO-TRIANGLES. I quote the construction here. Let $$X = \{x_1, x_2, \ldots, x_q\}$$, $$Y = \{y_1, y_2, \ldots, y_q\}$$, $$W = \{w_1, w_2, \ldots, w_q\}$$ and $$M \subseteq X\times Y\times Z$$ be the generic input instance of 3DM. Construct an initial set of vertices $$V$$, called the "public vertices", as the union of $$X$$, $$Y$$ and $$W$$. For every triple $$m = (x_a, y_b, w_c)$$ in $$M$$, construct the graph $$G_m = (V_m, E_m)$$, depicted in Figure 1. Here $$V_m$$ contains the three public vertices $$x_a$$, $$y_b$$ and $$w_c$$ plus three "private vertices" $$v_m^1$$, $$v_m^2$$ and $$v_m^3$$. The ten edges in $$E_m$$ are $$v_m^1v_m^2$$, $$v_m^1v_m^3$$, $$v_m^2v_m^3$$, $$x_av_m^3$$, $$x_av_m^2$$, $$y_bv_m^3$$, $$y_bv_m^1$$, $$w_cv_m^1$$, $$w_cv_m^2$$ and $$x_1y_b$$. The whole graph $$G_M$$ is obtained from the union of all the gadgets $$G_m$$ as follows: $$G_M = (V_M, E_M) = (\cup_m V_m,\cup_m E_m)$$.

Isn't it 3 dimensional matching?

https://en.wikipedia.org/wiki/3-dimensional_matching

Let us reduce 3-dimensional matching to deciding whether a graph has k disjoint triangles.

Let I be an instance o 3DM. Construct a graph G with X x Y x Z vertices and there is the edges of a triangle between vertices in x1 y1 z1 in G if there is the triple (x1 y1 z1) in the instance I. G has k disjoint triangles iff I has a 3DM M of size k. So, solve k-disjoint triangle in this class of graphs obtained from instances of 3DM solves 3DM for all its instances. As 3DM is NP-complete, k-disjoint triangles is NP-hard, and as it is clearly NP, it is also NP-complete.

• If your 3DM instance contains $(x',y,z),(x,y',z),(x,y,z')$ then your $k$-disjoint triangles instance contains the triangle $(x,y,z)$. This could be a problem. – Yuval Filmus May 11 '18 at 22:09
• @YuvalFilmus I think the proof given in Danial’s comment still holds in your example. – Mengfan Ma May 13 '18 at 9:06
• Actually, I prefer this answer because it’s simpler. – Mengfan Ma May 20 '18 at 7:02