Tree decompositions are a powerful tool in structural graph theory, that is traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has so far remained out of reach. Recently we obtained several results in this direction: the talk will be a survey of these results.
Given a graph where every vertex has exactly one labeled token, a swap exchanges the tokens at the two endpoints of an edge. The situation can be modelled as an exponentially large Cayley graph with a vertex for each permutation of the labels and an edge for each swap. It is easy to see that the Cayley graph is connected (every permutation of labels can be realized by a sequence of swaps). Of interest are the diameter of the Cayley graph (the worst case length of a sequence of swaps) and the complexity of computing the minimum length sequence of swaps to realize a given permutation. These token swapping problems have been studied by disparate groups of researchers in discrete mathematics, theoretical computer science, robotmotion planning, game theory, and engineering. I will survey this work and talk about hardness and approximation algorithms for token swapping on trees.
Network realization problems concern situations where given a specification S, detailing the desired values of a certain network parameter, it is required to construct a network adhering to S, or decide that no such network exists. A variety of network realization problems have been studied over the past 70 years, focusing mainly on the parameters of vertex degrees and inter-vertex distances. The talk will present some recent developments in the area of network realization.
In 1986, Kreher and Radziszowski first used the famous LLL algorithm to construct combinatorial designs. Subsequently, lattice algorithms have been applied to construct a large variety of objects in design theory, coding theory and finite geometry. Unfortunately, the use of lattice algorithms in combinatorial search is still not well established. Recently, a new enumeration strategy based on "limited discrepancy search" was used to further improve the power of this method. In this talk, we will describe the search strategy based on lattice basis reduction, compare it to widely used backtracking algorithms and integer linear programming algorithms, and will outline the recent progress.
