<p>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?</p>

<p>I'm assuming this problem is NP-hard.  Is it?</p>

<p>Is there a better term for complete k-partite subgraph (like multiclique or something)?</p>

<p>EDIT: k is not fixed.  The covering subgraphs can each have different values of k.</p>

<p>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 <a href="http://dl.acm.org/citation.cfm?id=2275596" rel="nofollow">http://dl.acm.org/citation.cfm?id=2275596</a>)</p>

CC BY-SA 3.0
2013-08-25T19:51:58.333Z
Are you familiar with the multidimensional assignment problem?
Austin Buchanan
CC BY-SA 3.0
2013-08-25T20:09:37.733Z
Not particularly.  I'm looking at http://onlinelibrary.wiley.com/doi/10.1111/j.1540-5915.1988.tb00269.x/abstract right now, but I don't yet see a connection to my problem.
dspyz
CC BY-SA 3.0
2013-08-25T21:01:27.870Z
Is the case $k=1$ the problem of finding the chromatic number?
Austin Buchanan
CC BY-SA 3.0
2013-08-25T22:31:35.150Z
No, k=1 is meaningless.  A 1-partite graph is a graph with no edges at all.
dspyz
CC BY-SA 3.0
2013-08-25T22:51:15.763Z
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
CC BY-SA 3.0
2013-08-26T00:33:38.247Z
I see the confusion.  I want to cover all the edges of the graph, not just all the vertices.  Furthermore I accept any subgraph, not just induced subgraphs.  In other words, one trivial solution for any graph is to simply include one biclique for every pair of vertices connected by an edge.  However, I want to minimize the total number of assignments of vertices to multicliques and this solution has 2E assignments which generally fails that criteria.
dspyz
<graph-theory><graph-algorithms><approximation-algorithms><set-cover><clique>
Finding assignment-minimum complete k-partite graph cover
dspyz
# Finding assignment-minimum complete k-partite graph cover

(Asked by: username_0 on 2013-08-25)

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>)

**Tags:** graph-theory, graph-algorithms, approximation-algorithms, set-cover, clique

> **Comments:**
> **username_1**: Are you familiar with the multidimensional assignment problem?  
> **username_0**: Not particularly.  I'm looking at http://onlinelibrary.wiley.com/doi/10.1111/j.1540-5915.1988.tb00269.x/abstract right now, but I don't yet see a connection to my problem.  
> **username_1**: Is the case $k=1$ the problem of finding the chromatic number?  
> **username_0**: No, k=1 is meaningless.  A 1-partite graph is a graph with no edges at all.  
> **username_1**: 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.  
> **username_0**: I see the confusion.  I want to cover all the edges of the graph, not just all the vertices.  Furthermore I accept any subgraph, not just induced subgraphs.  In other words, one trivial solution for any graph is to simply include one biclique for every pair of vertices connected by an edge.  However, I want to minimize the total number of assignments of vertices to multicliques and this solution has 2E assignments which generally fails that criteria.  

---

## 0 answers

