1
$\begingroup$

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?

New contributor
newbie is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

newbie is a new contributor. Be nice, and check out our Code of Conduct.

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.