Open Problems Sessions
|Next Meeting||11/12 2018|
On December 11, 14:15 (IMADA's seminar room): Jørgen will talk about construction of digraphs with certain antipath properties.
Thomas Bellitto presented restricted-walk graph problems. He first considered forbidden-transition graphs where a set of forbidden (or permitted) transitions are given. A transition is two different consecutive edges. Examples include properly-colored walks, where no two consecutive edges have the same color, and antidirected walks, alternating between forward/backward edges in a digraph. The concept can of course be generalized to forbidden subpaths. A graph is T-connected if there is a T-compatible walk between any two vertices, and then T is a connecting transition set. Finding a minimum connecting transition set is NP-complete. MST gives a trivial upper bound of n-2. A better upper bound can be expressed in terms of connected components of the complementary graph. An important observation is that the problem is the same as finding a connecting hypergraph of minimum cost, and a quadratic 3/2-approximation can be derived from this. At the end, open problems on coloring and odd cycles, as well as connectivity questions in a variety of graph classes were discussed.
Joan told about a complexity class for online algorithms, AOC. The complete problems for this class include many accept/reject problems that require large amounts of advice to achieve good competitive ratios. The work defining and analyzing this complexity class was joint with Lene, Christian Kudahl, and Jesper With Mikkelsen. A couple of harder and easier complexity classes were mentioned at the end. Joan is interested in defining further complexity classes for online algorithms.
Lene introduced advice complexity for online algorithms, using multi-coloring on the line and paging as motivating problems. She introduced advice bits and defined advice complexity of an algorithm and of a problem. Then she discussed trade-offs between the competitive ratio (the quality of a solution) and the amount of advice, and introduced the idea of using covering designs to reduce the number of advice bits at a small cost in approximation factor. The talk continued with graph problem examples and the concept of a reduction between these problems, starting with string guessing. In connection with questions from the audience, she discussed the implications of these results in connection with real-life problems. At the end, she discussed the connection between randomized algorithms and algorithms with advice.
Jørgen talked on graph orderings, starting with proper circular arc graphs, concave and convex round graphs, and interval-enumerable graphs, ending with excellent/nice orderings, and open problems for -arc strong orientation.
Joan introduced priority algorithms, with emphasis on the newer concept of priority stack algorithms, applying this to maximal weighted independent set for chordal graphs. She continued with vertex cover approximation in the setting of fixed and adaptive priority algorithms, respectively.
Daniel explained modeling chemical reactions via hypergraph transformations, and accounted for the use of graph grammars, generating functions, and Boltzmann sampling. Anders detailed progress on Kim's problem from last time, giving a lower bound on the barrier problem for sorting by transpositions.
Kim talked about sorting by transpositions and the question of what the maximal number of swaps across a fixed barrier could be. Anders introduced transversal numbers in hyper graphs and existence of Euler tours in edge-colored graphs, where two consecutive edges must have different color. Finally, Jing discussed non-crossing partial matchings on top of a line-graph, transitions between two such structures, and best sequences of such transitions relative to some stability measure.