Department of Applied Mathematics & Statistics, SUNY Korea, Incheon

bounds for the second largest eigenvalue in (an n-vertex) d-regular graph to

guarantee a certain vertex-connectivity.

Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.

The second largest eigenvalue and vertex-connectivity in regular graphs

Suil O (오수일)

Department of Applied Mathematics & Statistics, SUNY Korea, Incheon

Department of Applied Mathematics & Statistics, SUNY Korea, Incheon

2017/2/3 Fri 4PM-5PM

In this talk, for a fixed positive integer d at least 3, we study upper

bounds for the second largest eigenvalue in (an n-vertex) d-regular graph to

guarantee a certain vertex-connectivity.

bounds for the second largest eigenvalue in (an n-vertex) d-regular graph to

guarantee a certain vertex-connectivity.

Tree packing conjecture for bounded degree trees

Jaehoon Kim (김재훈)

School of Mathematics, Birmingham University, UK

School of Mathematics, Birmingham University, UK

2016/12/28 Wed 4PM-5PM

We prove that if T_{1},…, T_{n} is a sequence of bounded degree trees so that T_{i} has i vertices, then K_{n} has a decomposition into T_{1},…, T_{n}. This shows that the tree packing conjecture of Gyárfás and Lehel from 1976 holds for all bounded degree trees.

We deduce this result from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs.

In this talk, we discuss the ideas used in the proof.

This is joint work with Felix Joos, Daniela Kühn and Deryk Osthus.

We deduce this result from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs.

In this talk, we discuss the ideas used in the proof.

This is joint work with Felix Joos, Daniela Kühn and Deryk Osthus.

Analyzing Markov Chains using Belief Propagation

Eric Vigoda

School of Computer Science, Georgia Institute of Technology, Atlanta, Georgia, USA

School of Computer Science, Georgia Institute of Technology, Atlanta, Georgia, USA

2016/12/16 *Friday 3PM-4PM*

For counting weighted independent sets weighted by a parameter λ (known as the hard-core model) there is a beautiful connection between statistical physics phase transitions on infinite, regular trees and the computational complexity of approximate counting on graphs of maximum degree D. For λ below the critical point there is an elegant algorithm devised by Weitz (2006). The drawback of his algorithm is that the running time is exponential in log D. In this talk we’ll describe recent work which shows O(n log n) mixing time of the single-site Markov chain when the girth>6 and D is at least a sufficiently large constant. Our proof utilizes BP (belief propagation) to design a distance function in our coupling analysis. This is joint work with C. Efthymiou, T. Hayes, D. Stefankovic, and Y. Yin which appeared in FOCS ’16.

Solving the half-integral disjoint paths problem in highly connected digraphs

Paul Wollan

Department of Computer Science, University of Rome, Rome, Italy

Department of Computer Science, University of Rome, Rome, Italy

2016/11/30 Wed 4PM-5PM

The k disjoint paths problem, which was shown to be efficiently solvable for fixed k in undirected graphs in a breakthrough result by Robertson and Seymour, is notoriously difficult in directed graphs. In directed graphs, he problem is NP-complete even in the case when k=2. In an attempt to make the problem more tractable, Thomassen conjectured that if a digraph G were sufficiently strongly connected, then every k disjoint paths problem in G would be feasible. He later answered his conjecture in the negative, showing that the problem remains NP-complete when k=2, even when we assume that the graph is arbitrarily highly connected.

We consider the following further relaxation of the problem: a half-integral solution to a k disjoint paths problem is a set of paths linking the desired vertices such that each vertex of the graph is in at most two of the paths. We will present the new result that the half-integral k disjoint paths problem can be efficiently solved (even when the parameter k is included as part of the input!) if we assume the graph is highly connected.

This is joint work with Irene Muzi and Katherine Edwards.

Generalized feedback vertex set problems on bounded-treewidth graphs

O-joung Kwon (권오정)

Technische Universitat Berlin, Berin, Germany

Technische Universitat Berlin, Berin, Germany

2016/11/25 Fri 4PM-5PM

It has long been known that Feedback Vertex Set can be solved in time 2^{O(w log w)}n^{O(1)} on graphs of treewidth w, but it was only recently that this running time was improved to 2^{O(w)}n^{O(1)}, that is, to single-exponential parameterized by treewidth. We consider a natural generalization of this problem, which asks given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices of G such that each block of G-S has at most d vertices. The central question of this talk is: “Can we obtain an algorithm that runs in single-exponential time parameterized by treewidth, for every fixed d?” The answer is negative. But then, one may be curious which properties of Feedback Vertex Set that make it allow to have a single-exponential algorithm. To answer this question, we add an additional condition in the general problem, and provide a dichotomy result.

Formally, for a class 𝒫 of graphs, the Bounded 𝒫-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices of G such that each block of G-S has at most d vertices and is in 𝒫. Assuming that 𝒫 is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d:

Formally, for a class 𝒫 of graphs, the Bounded 𝒫-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices of G such that each block of G-S has at most d vertices and is in 𝒫. Assuming that 𝒫 is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d:

- if 𝒫 consists only of chordal graphs, then the problem can be solved in time 2
^{O(wd^2)}n^{O(1)}, - if 𝒫 contains a graph with an induced cycle of length ℓ≥4, then the problem is not solvable in time 2
^{o(w log w)}n^{O(1)}even for fixed d=ℓ, unless the ETH fails.

We further show that it is W[1]-hard parameterized by only treewidth, when 𝒫 consists of all graphs. This is joint work with Édouard Bonnet, Nick Brettell, and Daniel Marx.