Timeline for How to find a random cycle in a large graph?
Current License: CC BY-SA 4.0
35 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 29, 2020 at 19:47 | answer | added | Elle Najt | timeline score: 3 | |
| Aug 29, 2020 at 10:37 | comment | added | Emil Jeřábek | @LorenzoNajt I think you should post your insightful comments as an answer. | |
| Aug 29, 2020 at 10:24 | answer | added | Max Alekseyev | timeline score: 3 | |
| Aug 28, 2020 at 21:33 | comment | added | Elle Najt | This got bumped again, so let me add a few more tools you can look into: 1) Binary decision diagrams / ZDDs ( there is a python library for this tool link.springer.com/article/10.1007/s10009-014-0352-z ) ... if you can construc the ZDD you can count, sample , optimize... this tends to work for 'medium' sized problems 2) You can sample if you can compute the marginal probabilities. All of these can be encoded as SAT problems, and you can feed it to a #SAT solver. 3) If the underlying graph has small treewidth, you can use (complicated) a dynamic program. | |
| Aug 28, 2020 at 21:00 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 30, 2020 at 20:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jan 1, 2020 at 20:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Sep 3, 2019 at 19:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| May 6, 2019 at 19:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jan 6, 2019 at 19:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 7, 2018 at 19:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 7, 2018 at 19:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 8, 2018 at 19:00 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Sep 8, 2018 at 18:29 | answer | added | Ian | timeline score: 0 | |
| Sep 8, 2018 at 17:22 | history | edited | Ian | CC BY-SA 4.0 |
added 63 characters in body
|
| Sep 8, 2018 at 16:35 | history | edited | Ian | CC BY-SA 4.0 |
added 61 characters in body
|
| Sep 8, 2018 at 15:25 | comment | added | Elle Najt | There's no general efficient algorithm to sample uniformly a directed simple cycle (unless RP = NP) - see Jerrum-Valiant-Vazirani '86, proposition 5.1. This doesn't mean that it's hopeless for your graphs - e.g. there might be some Markov chain that happens to mix rapidly for the kind of graphs you care about. (Do you want simple cycles or are cycles with points of degree > 2 allowed?) | |
| Sep 8, 2018 at 15:22 | comment | added | Gerhard Paseman | I am not convinced either. However, no one has answered the question yet. Can you come up with a better answer? Gerhard "Gave It A Shot Already" Paseman, 2018.09.08. | |
| Sep 8, 2018 at 15:19 | comment | added | Gerhard Paseman | Also, there may be a way to sample the cycles, but it is not clear that the sample is uniform. This is the point of the question. My suggestion may not be fast, but I can prove that the cycle distribution is uniform. Gerhard "Slow But Steady Wins Proof" Paseman, 2018.09.08. | |
| Sep 8, 2018 at 15:16 | comment | added | Nate Eldredge | @GerhardPaseman: Yes, I misunderstood. But I'm still not very convinced that one can't do much better. | |
| Sep 8, 2018 at 15:15 | comment | added | Gerhard Paseman | @Nate, the n bit number has k bits which are ones. The cycle if it exists has k edges. Gerhard "Does It Make Sense Now?" Paseman, 2018.09.08. | |
| Sep 8, 2018 at 15:15 | comment | added | Nate Eldredge | @GerhardPaseman: Often graph algorithms can be better than you think. For instance, a somewhat similar question is how to randomly (uniformly) select a spanning tree, say in $K_n$. If you randomly choose $n-1$ edges, then the probability that they make a spanning tree is something like $1/n^n$ so it will take an extremely long time to get one that works. But Wilson's algorithm samples one in polynomial time. | |
| Sep 8, 2018 at 15:07 | history | edited | Ian | CC BY-SA 4.0 |
added 37 characters in body
|
| Sep 8, 2018 at 15:05 | history | edited | Ian | CC BY-SA 4.0 |
added 80 characters in body
|
| Sep 8, 2018 at 14:55 | history | edited | Ian | CC BY-SA 4.0 |
added 310 characters in body; edited tags
|
| Sep 8, 2018 at 14:34 | comment | added | Gerhard Paseman | If there is no ring, you never get to step 2. Although you mention doing things quickly, you never mention stopping. As a result, my method does not slow things down substantially when there are no rings. Gerhard "Thinks Cycles Is Better Term" Paseman, 2018.09.08. | |
| Sep 8, 2018 at 14:29 | comment | added | Ian | @GerhardPaseman That's a way to solve this. But what if there's no ring in this graph? If we choose edges randomly, it could take very long time to form a ring or to find there's no ring in this graph. | |
| Sep 8, 2018 at 14:25 | comment | added | Ian | @DavidG.Stork Actually, after reversing all the directions of the edges in a ring, this will not destroy this ring, which will still be a ring. What I consider is whether changing the edges could create new rings or destroy other rings. And how we find rings in the next iteration could be influenced. | |
| Sep 8, 2018 at 14:21 | comment | added | Ian | @RobertIsrael Yes, I have already edit the question to be more detailed. | |
| Sep 8, 2018 at 14:20 | history | edited | Ian | CC BY-SA 4.0 |
To be more detailed
|
| Sep 8, 2018 at 3:52 | comment | added | David G. Stork | But reversing a ring will destroy cycles ("rings") from the original graph $G$, so they will never be found. Moreover, the directed cycles that you do find by this algorithm will be dependent upon the random sequence that the cycles are found. Surely you don't want to create a table that 1) contains cycles that were not in the original graph, and 2) depend upon the random sequence of discovery. Right? | |
| Sep 8, 2018 at 1:46 | comment | added | Robert Israel | What do you mean by a ring? A simple directed cycle? | |
| Sep 8, 2018 at 0:55 | comment | added | Gerhard Paseman | Suppose there are n edges. Generate uniformly an n bit binary number, and use this to select edges. If the edges form a ring, go with it. Otherwise, try again. Since there are potentially exponentially many rings, I do not see how you are going to do much better. Gerhard "There Are Lots Of Cycles" Paseman, 2018.09.07. | |
| Sep 8, 2018 at 0:15 | review | First posts | |||
| Sep 8, 2018 at 0:26 | |||||
| Sep 8, 2018 at 0:11 | history | asked | Ian | CC BY-SA 4.0 |