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?

  • 2
    $\begingroup$ 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. $\endgroup$ – D.W. May 11 '18 at 17:27
  • 1
    $\begingroup$ @D.W. Apply the definition of k-Matching or k-Disjoint-Triangles? $\endgroup$ – John May 11 '18 at 17:37
  • 1
    $\begingroup$ @D.W. I have tried but I still couldn't come up with a good solution :( $\endgroup$ – John 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?


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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 11 '18 at 22:09
  • $\begingroup$ @YuvalFilmus I think the proof given in Danial’s comment still holds in your example. $\endgroup$ – John May 13 '18 at 9:06
  • $\begingroup$ Actually, I prefer this answer because it’s simpler. $\endgroup$ – John May 20 '18 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.