2
$\begingroup$

Given a bipartite graph G and a number N, what's the minimum number of edges I have to add to G in order to be able to cover the resulting graph with no more than N complete bipartite subgraphs?

For example, consider the bipartite graph A1 - B1, A1 - B2, A1 - B3, A2 - B1, A2 - B3, A3 - B1, A3 - B2, A3 - B3, A4 - B4, A4 - B5, A5 - B4, and N = 2. The answer would be 2, because by adding A2 - B2 and A5 - B5, I can cover the graph with the biclique (A1 A2 A3 x B1 B2 B3) and (A4 A5 x B4 B5).

I can't seem to find the class of problems this is called - everything I find is about covering with subgraphs, but I actually want an over-cover while creating few extra edges. Anybody enlighten me? :)

Improve this question
$\endgroup$
1
  • $\begingroup$ Only tangentially relevant: what comes to mind is the classical concept of Dushnik and Miller of representing a poset as the intersection of linear orderings on the same ground set. This is different, yet somehow in the same spirit: analysing a structure in terms of simpler_over_structures. See Dushnik--Miller: Partially Ordered sets, American Journal of Mathematics 63 (1941), perhaps this might help. $\endgroup$
    – Peter Heinig
    May 9, 2017 at 8:59

1 Answer 1

Reset to default
1
$\begingroup$

The kind of problem you are looking is called graph editing problems. There are many variations but, in general, in such kind of problem you are given a graph $G$ and you are asked the minimum number of edges (or vertices) you have do remove (or add, or both) in order to the graph satisfy a certain property $\Pi$.

A very close example of your question is the The Bicluster Graph Editing Problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.