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?

$\endgroup$

1 Answer 1

3
$\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

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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