ilyakava
Use backtracking
Here's a simple and effective approach: https://github.com/dblock/slack-sup/blob/master/slack-sup/models/round.rb#L64. Could use some improvement as described in https://github.com/jimwise/ambit/issues/1
Nice repo you've got there. You'll notice I closed a bunch of issues here b/c your repo should be the future of sup. Any code that I may write in the future would be only related to taking a graph as input, and throwing a partition into triangles as output.
As far as backtracking goes, this repo uses the concept.
As you note in the comment on ambit, for this particular problem, there are so many bad triplets. If we take a look at a graph where connects indicate a person may meet with another person, it is very sparse. That is the motivation for not using a generate and check method in this repo.
In the 3DM and PIT issues in fact the assumption is that all valid triplets have been generated, and all that remains is to pick as many as possible that don't overlap. This latter problem is much more computationally intensive.