# Finding assignment-minimum complete k-partite graph cover

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)

• Are you familiar with the multidimensional assignment problem? – Austin Buchanan Aug 25 '13 at 19:51
• Not particularly. I'm looking at onlinelibrary.wiley.com/doi/10.1111/j.1540-5915.1988.tb00269.x/… right now, but I don't yet see a connection to my problem. – dspyz Aug 25 '13 at 20:09
• Is the case $k=1$ the problem of finding the chromatic number? – Austin Buchanan Aug 25 '13 at 21:01
• No, k=1 is meaningless. A 1-partite graph is a graph with no edges at all. – dspyz Aug 25 '13 at 22:31
• Yes, it is called an independent set. The chromatic number is the minimum number of independent sets needed to cover the graph. The case $k=2$ is the cover by bicliques problem. If this is not what you're looking for, please provide more information, as I am confused by your problem description. – Austin Buchanan Aug 25 '13 at 22:51