KAIST Discrete Math Seminar

Branch-width and path-width are width parameters of graphs and matroids, which measure how easy it is to decompose a graph or a matroid into a tree-like or path-like structure via separations of small order. These parameters have been used not only for designing efficient algorithms with the inputs of small branch-width or path-width, but also for proving theoretical structural theorems by providing a rough structural description. We will describe a polynomial-time algorithm to construct a path-decomposition or a branch-decomposition of width at most k, if it exists, for a matroid represented over a fixed finite field for fixed k. Our approach is based on the dynamic programming combined with the idea developed by Bodlaender for his work on tree-width of graphs. For path-width, this is a new result. For branch-width, this improves the previous work by Hlineny and Oum (Finding branch-decompositions and rank-decompositions, SIAM J. Comput., 2008) which was very indirect; their algorithm is based on the upper bound on the size of minor obstructions proved by Geelen et al. (Obstructions to branch-decompositions of matroids, JCTB, 2006) and requires testing minors for each of these obstructions. Our new algorithm does not use minor obstructions. As a corollary, for graphs, we obtain an algorithm to construct a rank-decomposition of width at most k if it exists for fixed k. This is a joint work with Jisu Jeong (KAIST) and Eun Jung Kim (CNRS-LAMSADE).

I describe a construction that maps any connected graph G on three or more vertices into a larger graph, H(G), whose independence number is strictly smaller than its Lovasz number which is equal to its fractional packing number. The vertices of H(G) represent all possible events consistent with the stabilizer group of the quantum graph state associated with G, and exclusive events are adjacent. The graph H(G) corresponds to the orbit of G under local complementation. Physically, the construction translates into graph-theoretic terms the connection between a graph state and a Bell inequality maximally violated by quantum mechanics. In the context of zero-error information theory, the construction suggests a protocol achieving the maximum rate of entanglement-assisted capacity, a quantum mechanical analogue of the Shannon capacity, for each H(G). The violation of the Bell inequality is expressed by the one-shot version of this capacity being strictly larger than the independence number. The construction also describes a pseudo-telepathy game which is always won when using quantum resources but not always using classical resources. Finally we generalise the graph state to the mixed graph state and discuss how the previous construction may, therefore, be generalized. Joint work with: Cabello, Scarpa, Severini, Riera, Rahaman.

We develop a new paradigm to construct polytopes whose vertices can be obtained by an effective oracle in a unique fashion. Our main motivation comes from computational algebraic geometry. From this perspective these polytopes, called resultant polytopes, characterize polynomials better than total degree thus offering the fundamental representation in sparse elimination theory. We propose an output-sensitive algorithm that requires the minimum number of oracle calls, each reducing to the construction of a regular triangulation of the input set of points. Its implementation has been proven, among others, a valuable computational tool in our study of the combinatorial characterization of 4-dimensional resultant polytopes. We present the results of this study, that is, upper and lower bounds on the number of faces of 4-dimensional resultant polytopes.

An r-dynamic proper k-coloring of a graph G is a proper k-coloring of G such that every vertex in V(G) has neighbors in at least different color classes. The r-dynamic chromatic number of a graph G, written , is the least k such that G has such a coloring. By a greedy coloring algorithm, and the equality holds if and only if G is r-regular with diameter 2 and girth 5. We improve the bound to when . In terms of the chromatic number, we prove when G is k-regular with and show that may exceed when k=r. We prove when G has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, when G has diameter 3, which is sharp. This is joint work with Sogol Jahanbekam, Suil O, and Douglas B. West.

We describe how to approximate, in quasi-polynomial time, the largest independent set of polygons, in a given set of polygons. Our algorithm works by extending the result of Adamaszek and Wiese [AW13, AW14] to polygons of arbitrary complexity. Surprisingly, the algorithm also works for computing the largest subset of the given set of polygons that has some sparsity condition. For example, we show that one can approximate the largest subset of polygons, such that the intersection graph of the subset does not contain a cycle of length 4 (i.e., K2,2). To appear in SoCG 2014.