Max-product Belief Propagation (BP) is a popular message-passing algorithm for computing a Maximum-A-Posteriori (MAP) assignment over a distribution represented by a Graphical Model (GM). It has been shown that BP can solve a number of combinatorial optimization problems including minimum weight matching, shortest path, network flow and vertex cover under the following common assumption: the respective Linear Programming (LP) relaxation is tight, i.e., no integrality gap is present. However, when LP shows an integrality gap, no model has been known which can be solved systematically via sequential applications of BP. In this paper, we develop the first such algorithm, coined Blossom-BP, for solving the minimum weight matching problem over arbitrary graphs. Each step of the sequential algorithm requires applying BP over a modified graph constructed by contractions and expansions of blossoms, i.e., odd sets of vertices. Our scheme guarantees termination in O(n2) of BP runs, where n is the number of vertices in the original graph. In essence, the Blossom-BP offers a distributed version of the celebrated Edmonds’ Blossom algorithm by jumping at once over many sub-steps with a single BP. Moreover, our result provides an interpretation of the Edmonds’ algorithm as a sequence of LPs.

The celebrated theorem of Kuratowski characterizes those graphs that require at least one crossing when drawn in the plane, by exhibiting the complete list of topologically-minimal such graphs. As it is very well known, this list contains precisely two such 1-crossing-critical graphs: $K_5$ and $K_{3,3}$. The analogous problem of producing the complete list of 2-crossing-critical graphs is significantly harder. In fact, in 1987, Kochol exhibited an infinite family of 3-connected 2-crossing-critical graphs. In the talk, I will discuss the current status of the problem, including our recent work, which includes: (i) a description of all 3-connected 2-crossing-critical graphs that contain a subdivision of the M"obius Ladder $V_{10}$; (ii) a proof that there are only finitely many 3-connected 2-crossing-critical graphs not containing a subdivision of $V_{10}$; (iii) a description of all 2-crossing-critical graphs that are not 3-connected; and (iv) a recipe on how to construct all 3-connected 2-crossing-critical graphs that do not contain a subdivision of $V_{8}$.

The clique-width parameter provides a rough measure of the complexity of structure in (classes of) graphs. A well-known result of Courcelle, Makowsky and Rotics shows that many problems on graphs which are NP-hard in general can be solved in polynomial time in any class of graphs of bounded clique-width. Unlike the better-known treewidth graph parameter, clique-width respects the induced subgraph ordering, and in particular it can handle dense graphs. However, also unlike treewidth there is no known characterisation of the minimal classes of graphs which have unbounded clique-width.

 In Bondy and Murty’s book the authors wrote that Tutte conjectured the wheels have the fewest spanning trees out of all 3-connected graphs on fixed number of vertices. The statement can easily be shown to be false and the corrected version, where we fix the number of edges and consider only the planar graphs, were also found to be false. We prove that if we consider the cycles instead of spanning trees then the wheels are indeed extremal. We also establish a lower bound for the number of spanning trees and suggest the prisms as possible extremal graphs.