Changes between Initial Version and Version 1 of Ticket #16475, comment 17

05/18/15 15:03:17 (6 years ago)


  • Ticket #16475, comment 17

    initial v1  
    15 Replying to [comment:16 ncohen]:
    17 > Helloooooooooooo,
    18 >
    19 >
    20 >
    21 >
    22 > > First of all, you say that my code was very bad, because it gave wrong results. Could you tell me why? I see no counter-example or anything to back up your claim.
    23 > >
    24 > >
    25 > >
    26 >
    27 > Oh no sorry, that's a misunderstanding! I just re-read my comment and indeed I see how you could have understood it this way. I will edit it in a second. What I meant to say is "I had forgotten about this *bug*, and it is very bad (that I forgot it) because meanwhile Sage is returning wrong results".
    28 >
    29 > I have found nothing wrong with your code. Actually, as I began reading the proof that you followed, I merely noticed that it could be done in a simpler way. Which is why I proposed this alternative implementation, hoping that you would not mind.
    30 >
    31 >
    32 >
    33 >
    34 > > In the bibliographical reference you give (which is actually what I used as well), the proof to show that a Gomory-Hu tree exists uses a Partition { C_r | r \in R }, which dictates how the two induction-obtained trees should be merged. This is what I tried to add to the code with my patch, but you have completely removed it. Why? You simply put the edge between the two trees to be {u, v} where u and v are the picked vertices. However, why would Schrijver put such rigor in proving that this tree obtained using the partition is correct, and not instead simply use 2 arbitrary vertices.
    35 > >
    36 > >
    37 > >
    38 >
    39 > What the current branch does is apply Lemma 15.14alpha (p249 in my edition of it). While I obviously cannot tell you why Schrijver wrote the proof the way he did, I suspect that it is because he wants to *prove* the algorithm while I only want to implement it.
    40 >
    41 > Right now, the code applies Lemma 15.14alpha while *assuming* that every graph has a gomory-hu Tree. Schrijver cannot do this for the very obvious reasons that he wants to *prove* this existence result.
    42 >
    43 > Assuming the existence of a gomory-hu tree, I apply Lemma 15.14alpha to two points to obtain a bipartition `U,V` of the graph, then successively contract U and V to obtain two 'reduced' graphs. In each graph you will find 'two kinds' of vertices, i.e.:
    44 > - "real vertices from the original graphs" and
    45 > - "fake vertices that only appear because of the merge operation"
    46 >
    47 > With Lemma 15.14alpha, what we know is that the max flow between any two "real points" u,v of a specific "new" graph is equal to their max flow in the original graph. Consequently, the three that is being built must indeed be the gomory-hu tree (that we know exists).
    48 >
    49 >
    50 >
    51 > > You say you have fixed the algorithm by a single line of code, however I still think that it might give incorrect results in some cases, for reasons above. Would you agree?
    52 > >
    53 > >
    54 > >
    55 >
    56 > Do you believe that the way it is done is wrong? Or do you believe that it is suspect of being wrong because it is a simpler algorithm than the one given by Schrijver's proofs?
    57 >
    58 > In my experience, writing the proof of an algorithm requires much more theoretical machinery than what is actually needed when one implements it. Sometimes, it is even easier to make the (theoretical) algorithm a bit slower in order to make the explanation simpler. Very recently, I had to give a formal proof of an algorithm needed for some research problem: while it was easy to explain on a table, it was so complicated to explain it on paper that I started trying to change the algorithm itself to make the proof easier.
    59 >
    60 > Sorry for the misunderstanding, and thank you for your attention with respect to this issue.
    61 >
    62 > Nathann