KAIST Discrete Math Seminar

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.

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.

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.

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.

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.