February 3rd, 2016
On properties of almost all matroids
Seongmin Ok (옥성민)
Department of Applied Mathematics and Computer Science, Technical University of Denmark, Denmark
2016/02/12 Fri 4PM-5PM
In this talk, I attempt to provide a comprehensive introduction to the matroid properties that hold for almost all matroids.
Welsh conjectured that almost all matroids are paving, open for nearly 50 years. If true, the properties of paving matroids translate to almost all matroids, such as non-representability, concentrated ranks, high connectivity and so on. We shall see the related properties that are shown to hold for almost all matroids with some of the proofs. An overview of recent progress and possible further directions will also be presented.
November 10th, 2015
Belief Propagation for Combinatorial Optimization
2015/11/19 4:15PM-5:15PM (Room 1501, Bldg. E6)
Belief propagation (BP) is a popular message-passing algorithm for computing a maximum-a-posteriori assignment in a graphical model. It has been shown that BP can solve a few classes of Linear Programming (LP) formulations to combinatorial optimization problems including maximum weight matching and shortest path. However, it has been not clear what extent these results can be generalized to. In this talk, I first present a generic criteria that BP converges to the optimal solution of given LP, and show that it is satisfied in LP formulations associated to many classical combinatorial optimization problems including maximum weight perfect matching, shortest path, network flow, traveling salesman, cycle packing and vertex cover. Using the criteria, we also construct the exact distributed algorithm, called Blossom-BP, solving the maximum weight matching problem over arbitrary graphs. In essence, Blossom-BP offers a distributed version of the celebrated Blossom algorithm (Edmonds 1965) jumping at once over many sub-steps of the Blossom-V (most recent implementation of the Blossom algorithm due to Kolmogorov, 2011). Finally, I report the empirical performance of BP for solving large-scale combinatorial optimization problems. This talk is based on a series of joint works with Sungsoo Ahn (KAIST), Michael Chertkov (LANL), Inho Cho (KAIST), Dongsu Han (KAIST) and Sejun Park (KAIST).
November 10th, 2015
Characterizing 2-crossing-critical graphs
Department of Mathematics, Louisiana State University, Baton Rouge, LA , USA
2015/11/18 Wed 5PM-6PM
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: K5 and K3,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öbius Ladder V10; (ii) a proof that there are only finitely many 3-connected 2-crossing-critical graphs not containing a subdivision of V10; (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 V8.
This is a joint work with Drago Bokal, Bruce Richter, and Gelasio Salazar.
November 1st, 2015
Characterising structure in classes with unbounded clique-width
Department of Mathematics and Statistics, The Open University, Milton Keynes, UK
2015/11/11 Wed 5PM-6PM
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 this talk, I will survey a number of results and techniques for studying the interface between bounded and unbounded clique-width. Of particular interest are insights from the combinatorial study of permutations (“permutation patterns”), which has brought to light several more minimal graph classes with unbounded clique-width, and also suggests that a restricted version of the parameter, called linear clique-width, often appears to characterise the interface. Time-permitting, I will also discuss recent developments and open problems in the relationship between clique-width and well-quasi-ordering.
November 1st, 2015
Minimum Weight Perfect Matching via Blossom Belief Propagation
School of Electrical Engineering, KAIST
2015/12/2 Wed 5PM-6PM
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.
This is a joint work with Sejun Park, Michael Chertkov, and Jinwoo Shin.