# 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$? – Brendan McKay Oct 18 '11 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. ;-) – nvcleemp Oct 18 '11 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. – Brendan McKay Oct 18 '11 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. – nvcleemp Oct 18 '11 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 – Gerhard Paseman Oct 18 '11 at 15:19