# 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