I'm looking for an algorithm/insight into a problem that's an extension of the Maximum Weight Matching problem. The maximum weight matching problem looks for the max-weight set of edges that contain 0 common vertices. The problem can be thought of as grouping the vertices into sets of 2 such that no vertex belongs to more than 1 group.

I'm looking to extend the problem such that the vertices can be split into groups of 3. For an undirected graph, this translates into looking for cliques/cycles of size 3 that do not contain common vertices. Any guidance on how to approach this problem either deterministically or with an approximation/heuristic algorithm?

Note: the graphs I'm working with are typically dense


This problem is NP-complete even when all edge weights are 1, since that restriction is equivalent to the problem Partition Into Triangles, which "Computers and Intractability" (Garey and Johnson, 1979) lists as NP-complete on p. 192, attributing the result to a personal communication from T. J. Schaefer in 1974, apparently based on a reduction from 3-Dimensional Matching.

So, no efficient algorithm can be expected. For an exponential-time exact algorithm, I would probably try branch and bound intertwined with maximum bipartite (2-)matching, as follows: At each stage, we have a vertex $v_i$, which we will take to be the lowest-numbered vertex of a triangle, and the decision is which of its neighbour vertices $v_j$ should become the highest-numbered vertex in the triangle. For each possible $v_j$, to test feasibility of the choice, create a new, bipartite graph with a vertex for each low+high vertex pair decided so far, as well as a vertex for each as-yet unprocessed vertex, and an edge between two vertices whenever the low+high pair represented by one would form a triangle in the original graph with the other and the latter vertex is numbered between the low and high vertices represented by the former. Run maximum bipartite matching on this new graph, and check that every low+high pair decided so far is saturated (adjacent to a matched edge) -- if this fails, then the current assignment of low+high vertices cannot be extended to a full triangle partition and the branch can be pruned. I think this algorithm, which chooses just 2 vertices within each triangle, will result in B&B tree depths of around 2/3rds the fully naive approach in which all 3 vertices of each triangle are chosen.


Your Answer

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.