KAIST Discrete Math Seminar

Matroids can be seen an an abstraction for understanding the essence of algorithms for some classical graph problems: (i) optimum-weight spanning tree, and (ii) optimum-weight assignment. We will see some recent results showing how matroids have further natural roles in various combinatorial-optimization problems where some local-search and linear-programming-based algorithms find provably-good approximations. In particular, we will look at: (iii) constrained submodular-function maximization, (iv) the well-known matroid matching problem, and (v) various nonlinear-objective matroid-intersection problems.

Graph layout problems are a class of optimization problems whose goal is to find a linear ordering of an input graph in such a way that a certain objective function is optimized. The matrix rank function has been studied as an objective function. The linear rank-width of a graph G is the minimum integer k such that G admits a linear ordering satisfying that the maximum over all values $$ \operatorname{rank}A_G[\{v_1, v_2, \ldots, v_t\}, \{v_{t+1}, \ldots, v_n\}]$$ is k, where is the adjacency matrix of G and the rank is computed over the binary field.</p>

In this talk, we present a result that for every graph G that is vertex-minor minimal with the property having linear rank-width larger than p, the number of vertices in G is at most doubly exponential in . The number of vertex-minor obstructions for linear rank-width at most p is of interest because the only known fixed parameter tractable algorithm to test whether linear rank-width is at most p is using the finiteness of the number of forbidden vertex-minor obstructions. Our result gives an upper bound of the complexity on this algorithm. Our basic tools are the algebraic operations on labelled graphs introduced by Kanté and Rao, and we extend the notion of vertex-minors in our purpose. This is joint work with Mamadou Moustapha Kanté.

A hex tree is an ordered tree of which each vertex has updegree 0, 1, or 2, and an edge from a vertex of updegree 1 is either left, median, or right. In this talk, we introduce an enumeration problem of symmetric hex trees and describe a bijection between symmetric hex trees and a certain class of supertrees. Some algebraic properties of the polynomials arising in this procedure also will be discussed.

We prove the linearity (of the lengths) of some generalized Davenport-Schinzel sequences. Standard Davenport-Schinzel sequences of order 2 (avoiding abab) are linear, while those of order 3 (avoiding ababa) and higher can be superlinear. Our goal is to determine what pattern(s), in addition to ababa, must be forbidden to regain linearity. This work is motivated by an intriguing open problem: does the lower envelope of any set of degree 3 polynomials have linear complexity?

In this talk, we consider a well-known combinatorial search problem. Suppose that there are n identical looking coins and some of them are counterfeit. The weights of all authentic coins are the same and known a
priori. The weights of counterfeit coins vary but different from the weight of an authentic coin. Without loss of generality, we may assume the weight of authentic coins is 0. The problem is to find all counterfeit coins by weighing (queries) sets of coins on a spring scale. Finding the optimal number of queries is difficult even when there are only 2 counterfeit coins. We introduce a polynomial time randomized algorithm to find all counterfeit coins when the number of them is known to be at most and the weight of each counterfeit coin c satisfies for fixed constants . The query complexity of the algorithm is , which is optimal up to a constant factor. The algorithm uses, in part, random walks. The algorithm may be generalized to find all edges of a hidden weighted graph using a similar type of queries. This graph finding algorithm has various applications including DNA sequencing.