View: session overviewtalk overview

14:00 | Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs ABSTRACT. A rotor walk in a directed graph can be thought of as a deterministic version of a Markov Chain, where a pebble moves from vertex to vertex following a simple rule until a terminal vertex, or sink, has been reached. The ARRIVAL problem, as defined by Dohrau and al. [7], consists in determining which sink will be reached. While the walk itself can take an exponential number of steps, this problem belongs to the complexity class NP ∩ co-NP without being known to be in P. In this work, we define a class of directed graphs, namely tree-like multigraphs, which are multigraphs having the global shape of an undirected tree. We prove that in this class, ARRIVAL can be solved in almost linear time, while the number of steps of a rotor walk can still be exponential. Then, we give an application of this result to solve some deterministic analogs of stochastic models (e.g., Markovian decision processes, Stochastic Games). |

14:25 | Skolem Meets Schanuel PRESENTER: Joris Nieuwveld ABSTRACT. The celebrated Skolem-Mahler-Lech theorem states that the set of zeros of a linear recurrence sequence is the union of a finite set and finitely many arithmetic progressions. The corresponding computational question, the Skolem Problem, asks to decide whether a given linear recurrence sequence has a zero term. Although the Skolem-Mahler-Lech theorem is almost 90 years old, decidability of the Skolem Problem remains open. The main contribution of this paper is an algorithm to solve the Skolem Problem for simple linear recurrence sequences (those with simple characteristic roots). Whenever the algorithm terminates, it produces a certificate that its output is correct---either a zero of the sequence or a witness that no zero exists. We give a proof that the algorithm terminates assuming two classical number-theoretic conjectures: the Skolem Conjecture (also known as the exponential local-global principle) and the p-adic Schanuel conjecture. |

14:50 | Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems ABSTRACT. When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change over time. Consequently, an initially stable matching may become unstable. Then, a natural goal is to find a matching which is stable with respect to the modified preferences and as close as possible to the initial one. For Stable Marriage/Roommates, this problem was formally defined as Incremental Stable Marriage/Roommates by Bredereck et al. [AAAI '20]. As they showed that Incremental Stable Roommates and Incremental Stable Marriage with Ties are NP-hard, we focus on the parameterized complexity of these problems. We answer two open questions of Bredereck et al. [AAAI '20]: We show that Incremental Stable Roommates is W[1]-hard parameterized by the number of changes in the preferences, yet admits an intricate XP-algorithm, and we show that Incremental Stable Marriage with Ties is W[1]-hard parameterized by the number of ties. Furthermore, we analyze the influence of the degree of ``similarity'' between the agents' preference lists, identifying several polynomial-time solvable and fixed-parameter tractable cases, but also proving that Incremental Stable Roommates and Incremental Stable Marriage with Ties parameterized by the number of different preference lists are W[1]-hard. |

15:15 | On the Skolem Problem for Reversible Sequences ABSTRACT. Given an integer linear recurrence sequence ⟨X_0, X_1, X_2,...⟩, the Skolem Problem asks to determine whether there is a natural number n such that X_n = 0. The decidability of the Skolem Problem is a long-standing open problem in verification. In a recent preprint, Lipton, Luca, Nieuwveld, Ouaknine, Purser, and Worrell prove that the Skolem Problem is decidable for a class of reversible sequences of order at most seven. Herein, we give an alternative proof of the result. The novelty of our approach arises from our employment of theorems concerning the polynomial relations between Galois conjugates. In particular, we make repeated use of a result due to Dubickas and Smyth for algebraic integers that lie alongside all their Galois conjugates on two (but not one) concentric circles centred at the origin. |

16:10 | On Upward-Planar L-Drawings of Graphs PRESENTER: Sabine Cornelsen ABSTRACT. In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge e is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of $e$ and of a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Recently, upward-planar L-drawings have been studied for st-graphs, i.e., planar DAGs with a single source s and a single sink t containing an edge directed from s to t. It is known that a plane st-graph, i.e., an embedded st-graph in which the edge (s,t) is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic st-ordering, which can be tested in linear time. We study upward-planar L-drawings of DAGs that are not necessarily st-graphs. On the combinatorial side, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane st-graph admitting a bitonic st-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar~embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but each biconnected component is series-parallel. |

16:35 | Extending Partial Representations of Circle Graphs in Near-Linear Time ABSTRACT. The \emph{partial representation extension problem} generalizes the recognition problem for geometric intersection graphs. The input consists of a graph $G$, a subgraph $H \subseteq G$ and a representation~$\mathcal H$ of $H$. The question is whether $G$ admits a representation $\mathcal G$ whose restriction to $H$ is $\mathcal H$. We study this question for \emph{circle graphs}, which are intersection graphs of chords of a circle. Their representations are called \emph{chord diagrams}. We show that for a graph with $n$ vertices and $m$ edges the partial representation extension problem can be solved in $O((n + m) \alpha(n + m))$ time, where $\alpha$ is the inverse Ackermann function. This improves over an $O(n^3)$-time algorithm by Chaplick, Fulek and Klav\'ik~[2019]. The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph $G$, which is of independent interest. |

17:00 | RAC Drawings of Graphs with Low Degree PRESENTER: Julia Katheder ABSTRACT. Motivated by cognitive experiments providing evidence that large crossing-angles have a limited impact on the readability of a graph drawing, RAC (Right Angle Crossing) drawings were introduced to address the problem of producing readable representations of non-planar graphs by supporting the optimal case in which all crossings form 90° angles. In this work, we make progress on the problem of finding RAC drawings of graphs of low degree. In this context, a long-standing open question asks whether all degree-3 graphs admit straight-line RAC drawings. This question has been positively answered for the Hamiltonian degree-3 graphs. We improve on this result by extending to the class of 3-edge-colorable degree-3 graphs. When each edge is allowed to have one bend, we prove that degree-4 graphs admit such RAC drawings, a result which was previously known only for degree-3 graphs. Finally, we show that 7-edge-colorable degree-7 graphs admit RAC drawings with two bends per edge. This improves over the previous result on degree-6 graphs. |

16:10 | Continuous rational functions are deterministic regular ABSTRACT. A word-to-word function is rational if it can be realized by a non-deterministic one-way transducer. Over finite words, it is a classical result that any rational function is regular, i.e. it can be computed by a deterministic two-way transducer, or equivalently, by a deterministic streaming string transducer (a one-way automaton which manipulates string registers). This result no longer holds for infinite words, since a non-deterministic one-way transducer can guess, and check along its run, properties such as infinitely many occurrences of some pattern, which is impossible for a deterministic machine. In this paper, we identify the class of rational functions over infinite words which are also computable by a deterministic two-way transducer. It coincides with the class of rational functions which are continuous, and this property can thus be decided. This solves an open question raised in a previous paper of Dave et al. |

16:35 | Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order ABSTRACT. We study constraint automata that recognize data languages on finite string values. Each transition of the automaton is labelled with a constraint restricting the string value at the current and the next position of the data word in terms of the prefix and the suffix order. We prove that the emptiness problem for such constraint automata with Büchi acceptance condition is NL-complete. We remark that since the constraints are formed by two partial orders, prefix and suffix, we cannot exploit existing techniques for similar formalisms. Our decision procedure relies on a decidable characterization for those infinite paths in the graph underlying the automaton that can be complemented with string values to yield a Büchi-accepting run. Our result is - to the best of our knowledge - the first work in this context that considers both prefix and suffix, and it is a first step into answering an open question posed by Demri and Deters. |

17:00 | Learning Deterministic Visibly Pushdown Automata under Accessible Stack PRESENTER: Jakub Michaliszyn ABSTRACT. We study the problem of active learning deterministic visibly pushdown automata. We show that in the classical L*-setting, efficient active learning algorithms are not possible. To overcome this difficulty, we propose the accessible stack setting, where the algorithm has the read and write access to the stack. In this setting, we show that active learning can be done in polynomial time in the size of the target automaton and the counterexamples provided by the teacher. As counterexamples of exponential size are sometimes inevitable, we consider an algorithm working with words in a compressed representation via (visibly) Straight-Line Programs. Employing compression allows us to obtain an algorithm where the teacher and the learner work in time polynomial in the size of the target automaton alone. |