# Complexity of bipartite graphs and their matchings.

My question concerns a hypothetical family of bipartite graphs, $G_i$.

Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled by their color and a binary string of length $i$. Every edge in $G_i$ connects some red node to some blue node, and one fixed polynomial time algorithm (time polynomial in $i$) determines uniformly whether or not an edge connects a given red and blue node in any given $G_i$.

Now assume regularity for every $G_i$ --- every node in $G_i$ has the same degree as every other node in $G_i$. (The degree can vary with $i$.)

Matching theory says that every $G_i$ necessarily admits some matching (a.k.a. a factorization).

Must there exist (modulo standard conjectures, perhaps) an algorithm, time polynomial in $i$, that uniformly recognizes those edges present in some (uniform) family of matchings?

• I must not understand the question. How can you even find one edge in time polynomial in $i$? Oct 18, 2011 at 3:52
• I understood the question as there is a characterization of the edges based on the labels of its endpoints, so that given two labels it can easily be calculated whether there is an edge between them and now is the question whether this can be restricted to just the edges of a matching of the original graph. But of course I can be mistaken. I don't have psychic powers, I'm just writing how I understood the question. ;-) Oct 18, 2011 at 5:30
• Yes, I agree, but suppose you have one vertex on the left. How do you find a vertex on the right adjacent to it? There are $2^i$ possibilities and maybe only one of them works. Without more structure, you have to test them all. Oct 18, 2011 at 6:32
• Yes, but as I understand it, there exists a polynomial algorithm to find the right neighbours based on the bits of the label of the left vertex. (e.g. a vertex is adjacent to all other colour vertices at hamming distance 1) I think the OP means that there exists such an algorithm, but there is no specific algorithm given. My guess would be that the problem can't be solved for such a general setting. It will be possible for some specific families, but it needs to be look at case by case. Oct 18, 2011 at 7:09
• Here is my variation. Suppose I have a quick algorithm E that tells you, given i, n and m, if G_i has an edge between n and m (and G_i is regular, bipartite, etc.) . Theory will say there is a matching. Must there be a program M that, given i,n and m, tells us quickly if the matching has an edge between n and m? The problem I have with his version is that he might be asking for 2^i edges in time i. Gerhard "Ask Me About System Design" Paseman, 2011.10.18 Oct 18, 2011 at 15:19