algorithms – Time complexity of the triangle factoring problem

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.