Timeline for Complexity of bipartite graphs and their matchings.
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 31, 2016 at 20:06 | answer | added | user86008 | timeline score: -2 | |
| Oct 19, 2011 at 6:21 | comment | added | David Feldman | @Daniel It can't and it doesn't have to. The algorithm specifies a matching. It just has to recognize whether one given edge of G_i belongs to the matching it specifies in time polynomial in the lengths of the labels of the endnodes of the edge. | |
| Oct 19, 2011 at 5:42 | comment | added | Daniel Mansfield | How can an algorithm check all $2^i$ edges of a matching in polynomial time in the order of $i$? | |
| Oct 19, 2011 at 2:16 | comment | added | David Feldman | From a closeable question to the foundation of a discipline in one hour! Progress! :) "Generate portions" sounds different to me than "recognize" portions, so I wonder if you haven't framed a parallel question, Gerhard. Certainly rapid enumeration doesn't automatically give a rapid answer to my decision questions. And for problems as general as you propose, one might not have a converse. Mixtures of model theory and recursion theory already exist, so doubtless there exist model theory-complexity theory hybrids too? | |
| Oct 18, 2011 at 23:56 | comment | added | Gerhard Paseman | Alternatively, you might found a new discipline (or explanation of an existing discipline) which might be named algebraic computational complexity: objects are programs which (fixing a structural type like that of semigroups or complemented lattices) will generate portions of a sequence of structures <S>, and morphisms are known or perhaps unknown transformations to programs that produce portions of a sequence of substructures <T>. The key ideas will be uniformity and low complexity, so as to get applicable results quickly. Gerhard "Ask Me About System Design" Paseman, 2011.10.18 | |
| Oct 18, 2011 at 23:46 | comment | added | Gerhard Paseman | The combination of comments and question make sense to me. I would rewrite it with the following sequence of emphasis : set up sequence <G>, observe sequence of matchings <M>, posit a Turing machine G or formal computational model to produce <G>, ask for existence of M that makes pieces of <M> and is suitably quick. I think this makes it more clear, and suggests that solving this will be as easy as resolving P vs NP. There may even be an equivalence. Gerhard "Ask Me About System Design" Paseman, 2011.10.18 | |
| Oct 18, 2011 at 22:19 | comment | added | David Feldman | Gerhard, I also bet no, but certainly this is a complexity theory, not recursion theory question. After all, one can find matchings for the G_i's in pseudo-polynomial time (polynomial in the number of nodes or edges of the graphs). | |
| Oct 18, 2011 at 22:16 | comment | added | David Feldman | I have edited the original question in a way that I think eliminates the possibility of confusion. Right? | |
| Oct 18, 2011 at 22:15 | history | edited | David Feldman | CC BY-SA 3.0 |
added 7 characters in body
|
| Oct 18, 2011 at 22:14 | comment | added | David Feldman | Gerhard Paseman interpretation is almost what I meant/said. I would edit his exegesis as follows: 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 a yes or a no, and such that the edges to which M says yes constitute a matching? | |
| Oct 18, 2011 at 15:27 | comment | added | Gerhard Paseman | I think the answer is no, in that a matching which encodes the halting function can be embedded inside the graphs G_i. However, I don't know how to make the matching unique enough while making the graph description uniform. There are techniques of creating recursive x-y plots with nonrecursive projections onto the x axis that might aid in showing the answer is no. Gerhard "Ask Me About System Design" Paseman, 2011.10.18 | |
| Oct 18, 2011 at 15:19 | comment | added | Gerhard Paseman | 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 10:51 | comment | added | Brendan McKay | Either David should edit the question to make sense, or it should be closed. | |
| Oct 18, 2011 at 7:09 | comment | added | nvcleemp | 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 6:32 | comment | added | Brendan McKay | 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 5:30 | comment | added | nvcleemp | 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 3:52 | comment | added | Brendan McKay | I must not understand the question. How can you even find one edge in time polynomial in $i$? | |
| Oct 18, 2011 at 3:49 | history | edited | David Feldman | CC BY-SA 3.0 |
added 38 characters in body
|
| Oct 18, 2011 at 2:20 | history | asked | David Feldman | CC BY-SA 3.0 |