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.

6/11 2018 |

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.

2/10 2018 |

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.

11/9 2018 |

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.

15/5 2018 |

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 $k$-arc strong orientation.

17/4 2018 |

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.

6/3 2018 |

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 $\Omega (log\; n)$ lower bound on the barrier problem
for sorting by transpositions.

6/2 2018 |

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.