Problem 10: Find the Max-Cut of a Social Graph


Obtain the graph you need for this problem here: NetworkX florentine_families_graph().  Your answer should be the number of nodes in the smaller of the two subsets of the Max-Cut.



  • DWave Sampler (best result over 10 repetitions and 1000 reads)

    Florentine Families: 6

    Karate Club: 11

    Davis Southern Woman: 14

    ExactSolver results:

    Florentine Families: 6

    Karate Club: Took Too Much Time

    Davis Southern Woman: Took Too Much Time

    Here is the code on GitHub:

    I have some doubts:
    1) Every run I get different results, in order to get the best out of DWave chip, should I put more reads, or to run the same experiments from scratch from the notebook? Does this make any difference at all? I mean it's better 10 experiments of 1000 reads or 10000 reads in 1 experiment?

    2) During my trials I've found that very rarely the Florentine Families problem get solved with 5 nodes in the smallest set, but this is not even the result of the Exact Solver, which make me think that this is wrong answer, even if it's the minimum correct? Should I take the most probable, meaning the ones that showed up more time or should I pick the absolute minimum solution?

    DISCALMIER: The results posted here might be different from the ones in the Notebook on GitHub since I'm doing many trials and this way the results change, I reported here only the Absolute Minimum answers that I found along the way...something inside me is telling me that this is wrong and I should take the most probable, but I wait for any confirmation :) Thank you !

    @EDIT: Changed the strategy from the absolute minimum to the most probable in the results & in the github.


    Comment actions Permalink
  • Nice job, Calogero.  Yes, we were looking for the answer 6.

    Comment actions Permalink
  • I am late again. Below are the answer screen and the code.

    Max Cut for families in Renaissance-era Florence graph is 6.
    Max Cut for Karate club graph is 10.
    Max Cut for Davis Southern women graph is 14. 

    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post