1
$\begingroup$

Given two sets of vertices $U$ (size $n$) and $V$ (size $m$), how many possibilities of set of edges $E$ exist that make the bipartite graph $G = (U, V, E)$ connected?

Obviously there are $2^{n m}$ different set of edges but many will be disconnected.

$\endgroup$
4
  • 1
    $\begingroup$ It's at least $2^{(n-1)(m-1)}$, If this is enough for you to see is very big. $\endgroup$
    – user742
    Jul 11, 2013 at 17:29
  • $\begingroup$ I know that it is very big. But how big? $\endgroup$
    – Unapiedra
    Jul 11, 2013 at 17:32
  • 1
    $\begingroup$ I think in this big range $2^{(m-1)(n-1)}$ is somehow precise, but you looking for the exact number? Can I ask you what's your original problem? $\endgroup$
    – user742
    Jul 11, 2013 at 17:33
  • $\begingroup$ Yes, I am trying to solve Project Euler 434. I know that a grid truss is rigid if the bipartite graph formed from it, is connected. Form the bipartite graph by having U being all rows and V being all columns, add an edge for every diagonal member in (row, col). iust.ac.ir/files/cefsse/pg.cef/Contents/chapter_3.pdf , page 98 $\endgroup$
    – Unapiedra
    Jul 11, 2013 at 18:16

1 Answer 1

0
$\begingroup$

The answer is was given by David Eisenstadt in his answer to my question.

The answer can be computed by starting with the fully connected bipartite graph and evaluating the Tutte polynomial at (1,2).

While I don't fully understand everything about this problem, the intuitive reasoning is as follows:

Start with the fully connected-graph. The Contraction-Deletion Algorithm and the Tutte polynomial at (1,1) give the number of possible spanning trees. But we are actually not interested in the number of spanning trees but also along all the still-connected graphs along the paths to get to the spanning trees.

Note:

If you can explain this further, either add your own answer, or edit mine. If you add your own answer, I will accept yours.

$\endgroup$
2
  • $\begingroup$ This is hard problem, otherwise someone here or in SO would provide a complete answer. But point of my comment was if you want to brute force on something like this, you should not do it. $\endgroup$
    – user742
    Jul 18, 2013 at 12:37
  • $\begingroup$ And you don't have to, because the Tutte polynomial gives you the answer! Also I never wanted to run anything on the set of combinations, I just wanted to know the size. Calculating this is far from brute force. One implementation I found gives me this for n=100, m=100 in about a second. $\endgroup$
    – Unapiedra
    Jul 18, 2013 at 12:41

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.