Time complexity of the triangle factoring problem

Question

We define the triangle factoring problem as in Triangle Factors in Random Graphs, which is, given a simple undirected graph of $3n$ nodes, find if there's a subset of edges dividing vertices into $n$ vertex-disjoint triangles.

I've seen some papers discussing about the probability of such a factoring exists, but I'm unaware of any non-trivial algorithm solving this problem or any reductions. Is it NP-Complete? or, is it in P?

Answer 1

The triangle factor problem is NP-complete in general [1] (and even for graphs of clique number 3), but solvable in polynomial time for some restricted graph classes like chordal graphs [2,3]. These references will get you up to speed easily.

---

[1] Garey, Michael R., and David S. Johnson. "Computers and Intractability: A Guide to the Theory of NP-completeness" (1979).

[2] Guruswami, Venkatesan, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, and Chak-Kuen Wong. "The vertex-disjoint triangles problem." In International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 26-37. Springer, Berlin, Heidelberg, 1998.

[3] Dahlhaus, Elias, and Marek Karpinski. "Matching and multidimensional matching in chordal and strongly chordal graphs." Discrete Applied Mathematics 84, no. 1-3 (1998): 79-91.