| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

3. Efficient Algorithms

These problems concern the design of efficient algorithms for various tasks related to partition sampling and counting, as well as specific computations.

    1. #3 Enumerating partitions with ZDD

          Currently, the best known algorithm for enumerating connected, balanced graph partitions is based on Zero-suppressed Decision Diagrams, or ZDD for short [Nakahata, Kawahara, and Kasahara, 2018].

      Add remark

      Problem 3.1.

      [Gabe Schoenbach, Daryl DeFord] Is ZDD the best algorithm to enumerate all balanced partitions that are $\varepsilon$-balanced? Or is there some other method?

      (a) Is there a combinatorial/geometric way to understand the pruned branches in the ZDD algorithm?

      (b) Can we analyze ZDD to get better bounds on the likelihood of approximate splittability of random trees?

        • #8 UST speedup


          Add remark

          Problem 3.2.

          [Gregory Herschlag] Is there a faster algorithm to draw an (approximately) uniformly random spanning tree, perhaps on well-behaved graph families?

            • #10 Uniform partition sampling


              Add remark

              Problem 3.3.

              [org.aimpl.user:jtuckerfoltz@gmail.com] Can we sample a uniformly random balanced graph partition into two pieces in polynomial time on well-behaved graphs? Specifically, can we do this on grid graphs? Wesley Pegden has an informal argument suggesting that simply running the flip walk would not mix in polynomial-time, so that does not work. Also, what if we drop the balance constraint?

                • #22 Recursive splitting balance constraints


                  Add remark

                  Problem 3.4.

                  [Jeanne Clelland] When recursively splitting trees to build a balanced partition, what population balance constraints should be enforced in the earlier steps to get approximate balance at the end?

                    • #31 Most likely MST on grids


                      Add remark

                      Problem 3.5.

                      [Kris Tapp] Can we find the MST probability maximizer (with iid random weights) in, say, an $8 \times 8$ grid graph? Can we approximately optimize this numerically?

                          Cite this as: AimPL: Mathematical foundations of sampling connected balanced graph partitions, available at http://aimpl.org/connectedbalanced.