4
$\begingroup$

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?

Improve this question
$\endgroup$
15
  • 1
    $\begingroup$ I must not understand the question. How can you even find one edge in time polynomial in $i$? $\endgroup$
    – Brendan McKay
    Commented Oct 18, 2011 at 3:52
  • $\begingroup$ 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. ;-) $\endgroup$
    – nvcleemp
    Commented Oct 18, 2011 at 5:30
  • $\begingroup$ 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. $\endgroup$
    – Brendan McKay
    Commented Oct 18, 2011 at 6:32
  • $\begingroup$ 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. $\endgroup$
    – nvcleemp
    Commented Oct 18, 2011 at 7:09
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Oct 18, 2011 at 15:19

1 Answer 1

Reset to default
-2
$\begingroup$

Construct V times BFS trees starting as root each tree from another vertex as root. Partitioning - side A odd depths, side B even depths. If within same depth no edges in original graph, then graph it's bipartile.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Given that this question has been unanswered for 4 years you need to provide a very detailed answer. $\endgroup$
    – Chris Ramsey
    Commented Jan 31, 2016 at 21:33
  • $\begingroup$ Also, the English is very hard to understand. If you do give a more detailed answer, then consider having someone who is fluent in English read it over before posting. $\endgroup$
    – Todd Trimble
    Commented Jan 31, 2016 at 22:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .