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)

  • $\begingroup$ Are you familiar with the multidimensional assignment problem? $\endgroup$ – Austin Buchanan Aug 25 '13 at 19:51
  • $\begingroup$ 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. $\endgroup$ – dspyz Aug 25 '13 at 20:09
  • $\begingroup$ Is the case $k=1$ the problem of finding the chromatic number? $\endgroup$ – Austin Buchanan Aug 25 '13 at 21:01
  • $\begingroup$ No, k=1 is meaningless. A 1-partite graph is a graph with no edges at all. $\endgroup$ – dspyz Aug 25 '13 at 22:31
  • $\begingroup$ 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. $\endgroup$ – Austin Buchanan Aug 25 '13 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.