Seminars in May 2014

  • Eunjung Kim, A polynomial-time algorithm for outerplanar diameter improvement
    A polynomial-time algorithm for outerplanar diameter improvement
    Eunjung Kim
    CNRS, LAMSADE, Paris, France
    2014/05/26 Monday 4PM-5PM
    Room 1409
    The Outerplanar Diameter Improvement problem asks, given a graph G and an integer D, whether it is possible to add edges to G in a way that the resulting graph is outerplanar and has diameter at most D. We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.
    Tags:

  • Kwang Ju Choi, Nearly planar graphs and graph minor obstructions for embedding on the spindle surface
    Nearly planar graphs and graph minor obstructions for embedding on the spindle surface
    Kwang Ju Choi
    NIMS
    2014/05/19 Monday 4PM-5PM
    Room 1409
    In this talk, we define nearly planar graphs, that is, graphs that are edgeless or have an edge whose deletion results in a planar graph. We show that all but finitely many graphs that are not nearly planar and do not contain one particular graph have a well-understood structure based on large Mobius ladders. D. Archdeacon and C. Bonnington proved that a cubic obstruction for near-planarity is the same as an obstruction for embedding on the spindle surface and they gave the topological obstruction set for cubic nearly planar graphs. Now, we are searching graph minor obstructions for embedding on the spindle surface. This is a joint work with Bogdan Oporowski and Guoli Ding.
    Tags:

  • Gena Hahn, Cops, robbers, infinite graphs and related problems
    Cops, robbers, infinite graphs and related problems
    Gena Hahn
    University of Montreal, Canada
    2014/05/14 Wednesday 4PM-5PM
    Room 1409
    We briefly survey the game of cops-and-robbers on graphs and its variants in the fi nite case and then concenrate on in finite graphs, stressing the diff erence between the fi nite and the in finite. Along the way we show (time allowing) how to construct in finite vertex transitive graphs from any graphs and point out some strange properties of the construction. We also suggest several open problems, both fi nite and infi nite. The talk is based on work with A. Bonato, C.Tardif and R.E. Woodrow.
    Tags:

  • Michael Lampis, Parameterized Approximation Schemes using Graph Widths
    Parameterized Approximation Schemes using Graph Widths
    Michael Lampis
    Kyoto University, Japan
    2014/05/13 Tuesday 4PM-5PM
    Room 1409
    A number of natural graph problems are known to be W-hard to solve exactly when parameterized by standard widths (treewidth or clique-width). At the same time, such problems are typically hard to approximate in polynomial time. In this talk we will present a natural randomized rounding technique that extends well-known ideas and can be used to obtain FPT approximation schemes for several such problems, evading both polynomial-time inapproximability and parameterized intractability bounds.
    Tags:

  • Valia Mitsou, The computational complexity of the game of SET and its theoretical applications
    The computational complexity of the game of SET and its theoretical applications
    Valia Mitsou
    University of New York, USA
    2014/05/12 Monday 4PM-5PM
    Room 1409
    The game of SET is a popular card game in which the objective is to form Sets (triplets of cards that match in a particular sense) using cards from a special deck. For more details regarding the game, please visit the official website: http://www.setgame.com/.
    We analyze the computational complexity of some variations of the game of SET, presenting positive as well as hardness results in the classical and parameterized sense. Along the way, we make interesting connections of these generalizations of the game with other combinatorial problems, like Perfect Multi-Dimensional Matching, Set Packing, Independent Edge Dominating Set, and a two-player game played on graphs called Arc Kayles.
    Tags:

  • Woong Kook, Combinatorial Laplacians and high dimensional tree numbers
    Combinatorial Laplacians and high dimensional tree numbers
    Woong Kook
    Seoul National University
    2014/05/08 Thursday 4PM-5PM
    Room 1409
    Combinatorial Laplacians provide important enumeration methods in topological combinatorics. For a finite chain complex \{C_{i},\partial_{i}\}, combinatorial Laplacians \Delta_{i} on C_{i} are defined by </p>
    \Delta_{i}=\partial_{i+1}\partial_{i+1}^{t}+\partial_{i}^{t}\partial_{i}\, .

    We will review applications of \Delta_{0} in computing the tree numbers for graphs and in solving discrete Laplace equations for networks. In general, the boundary operators \partial_{i} are used to define high-dimensional trees as a generalization of spanning trees for graphs. We will demonstrate an intriguing relation between high-dimensional tree numbers and \det\Delta_{i} for acyclic complexes, based on combinatorial Hodge theory. As an application, a formula for the top-dimensional tree-number of matroid complexes will be derived. If time permits, an important role of combinatorial Laplacians in topological data analysis (TDA) will be briefly discussed.

    Tags:

Monthly Archives