Timeline for Graph to Bipartite conversion preserving number of perfect matchings
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 29, 2017 at 14:13 | answer | added | Peter Heinig | timeline score: 2 | |
| Aug 29, 2017 at 13:01 | comment | added | Peter Heinig | @TimothyChow: just writing to second your comment: it seems to me that currently neither existence, nor complexity of computation, let alone any reasonable sense of uniqueness of the required '777-nf' is settled. Although I think that existence should be routine to decide, given the wealth of knowledge in the literature on permanents. (Of course, the number of perfect matchings equals the permanent, over $\mathbb{Q}$, of the adjacency matrix of the graph in question. It would be quite embarassing if one could not quickly determine whether enough is known about the ranges of permanents.) | |
| Aug 28, 2017 at 21:55 | comment | added | Turbo | @TimothyChow Given two bipartites with $\#$ of perfect matchins $M_1$ and $M_2$ can we construct a bipartite of at most poly size of given graphs with $\#$ of perfect matchings $M_1+M_2$ in exponential time? | |
| Aug 28, 2017 at 18:07 | comment | added | Timothy Chow | @777 : I did not say that $B$ cannot exist, just that it is not clear to me that $B$ does exist. To put the question simply, do you know for sure that there exists a balanced bipartite graph with 1249180293809121 perfect matchings? | |
| Aug 28, 2017 at 9:05 | comment | added | Turbo | @TimothyChow why do you say $B$ cannot exist? | |
| Aug 28, 2017 at 7:00 | comment | added | Peter Heinig | @777: Do you require that along the way the number of perfect matchings is preserved? (Wilson's vertex splitting operations provide this, while alas they don't do anything about odd circuits.) Or do you permit 'straying outside the variety of graphs with a given number of perfect matchings'? (If so, then there may be 'shortcuts' to the 777-nf...) (Explanation: for brevity I propose calling '777-nf' (for 777-normal form) any balanced bipartite graph having exactly the same number of perfect matchings as the given graph.) | |
| Aug 28, 2017 at 6:56 | comment | added | Peter Heinig | Dear @777: thanks for clarifying. You seem to be right in saying that the quantitative condition of requiring to the conversion to happen in $O(n^c)$ steps is enough to make this a very interesting and legitimate research question. I deleted my comment saying that the problem is not sufficiently constrained. I think it might be useful to others trying to solve this to summarize: the OP is asking for how far w.r.t. a reasonable 'edit-metric' a finite graph can at worst be to a balanced bipartite graph with the same number of 1-factors. This suggests a clarification question:[...] | |
| Aug 27, 2017 at 22:44 | comment | added | Timothy Chow | @777 : It is clear that you are asking for a construction in polynomial time, but even without this proviso I am not sure the question is trivial. As Jon Noel pointed out, it is not even clear to me, for question 1, whether $B$ even exists, let alone is constructible in polynomial time. | |
| Aug 27, 2017 at 21:31 | comment | added | Jon Noel | So, if I understand correctly, you want to take an input graph with an unknown number of perfect matchings and produce a bipartite graph with the same (or close to the same) number of perfect matchings. And you want to do this in polynomial time, even if the number of perfect matchings is, say, exponential. Its an interesting question. | |
| Aug 27, 2017 at 20:46 | comment | added | Turbo | @ColinMcQuillan I misread your comment (you are right). | |
| Aug 27, 2017 at 19:09 | comment | added | Turbo | @ColinMcQuillan not if we seek deterministic polynomial time which is what I meant when I avoided the word 'randomized'. | |
| Aug 27, 2017 at 19:08 | history | edited | Turbo | CC BY-SA 3.0 |
added 14 characters in body
|
| Aug 27, 2017 at 18:49 | comment | added | Colin McQuillan | 2 is probably unknown since there is a randomized approximation algorithm for counting perfect matchings in bipartite graphs (Jerrum-Sinclair), but none known for general graphs. | |
| Aug 27, 2017 at 17:37 | comment | added | Turbo | @PeterHeinig we need a construction in polynomial time or else it is trivial. | |
| Aug 27, 2017 at 17:36 | comment | added | Turbo | @JonNoel we need a construction in polynomial time or else it is trivial. | |
| Aug 27, 2017 at 16:10 | review | Suggested edits | |||
| Aug 27, 2017 at 17:16 | |||||
| Aug 27, 2017 at 11:57 | comment | added | Jon Noel | It is probably true that, for every non-negative integer $k$, there exists a bipartite graph with "not too many" vertices and exactly $k$ perfect matchings (although I don't immediately see the construction). Would this be enough to solve your problem? Or do you want the bipartite graph $B$ to have some stronger relationship to $G$? | |
| Aug 27, 2017 at 9:58 | history | asked | Turbo | CC BY-SA 3.0 |