Is there any work on approximation algorithms (or exact algorithms) for finding an assignment-minimum cover of an arbitrary graph using complete k-partite subgraphs?
I'm assuming this problem is NP-hard. Is it?
Is there a better term for complete k-partite subgraph (like multiclique or something)?
EDIT: k is not fixed. The covering subgraphs can each have different values of k.
EDIT 2: When I say "cover", I mean a cover over all the edges of the graph (not over all the vertices). Furthermore, by "subgraph" I actually mean subgraph, not induced subgraph. k=1 no-edge subgraphs are useless and can be removed from the solution since they cover zero edges. By assignment-minimum, I mean find the solution which minimizes the number of assignments of vertices to subgraphs (as in http://dl.acm.org/citation.cfm?id=2275596)