Maximum of K3 disjoint subgraphs of graph
I am trying to solve a following problem: We have some graph. How to find (only 开发者_如何学Pythonnumber) maximum of K3 complete graphs which are subgraphs of input graph and are disjoint to each other.
I DO NOT need a code, a complete solution. I need an advice where to start. I thought about DFU and some traversing but it doesn't give a solution, at least not with some good time complexity.
By disjoint I presume you mean any two triangles do not even share a vertex.
This is going to be NP-Hard.
Partition into triangles is NP-Complete, and can be reduced to your problem.
By constructing a graph of the triangles: each triangle is a vertex and two triangles are adjacent if they share a node. You could reduce it to the largest independent set problem, which probably has a lot of literature on algorithms/approximation algorithms etc.
精彩评论