FCT 2021

23rd International Symposium on
Fundamentals of Computation Theory
September 12-15, 2021, Athens, Greece (virtually)

Detailed Program

Sunday, September 12

13:30-14:00 Welcome
14:00-16:30 Tutorial

David Richerby
The Complexity of Counting Problems   View details  View video

16:30-17:00 Break
17:00-18:30 Young Researchers' Forum (informal meeting) View details  View video
18:30-19:30 Social Meeting

Monday, September 13

11:30-12:00 Welcome - Opening
12:00-13:00 Plenary Talk I (chair: Aris Pagourtzis)

Nobuko Yoshida
Communicating Finite State Machines meet Multiparty Session Types   View details  View video

13:00-13:15 Break
13:15-14:15 Session 1 [Logic, Languages, Complexity] (chair: Nikos Tzevelekos)

Bharat Adsul, Saptarshi Sarkar and A V Sreejith
First-Order logic and its Infinitary Quantifier Extensions over Countable Words   Go to Abstract  View video

Abstract: We contribute to the refined understanding of the language-logic-algebra interplay in the context of first-order properties of countable words. We establish decidable algebraic characterizations of FO[1] -- one variable fragment of FO as well as boolean closure of existential fragment of FO via a strengthening of Simon's theorem about piecewise testable languages. We propose a new extension of FO which admits infinitary quantifiers to reason about the inherent infinitary properties of countable words. We provide very natural and hierarchical block-product based characterization of the new extension. We also explicate its role in view of other natural and classical logical systems such as WMSO and FO[cut] - an extension of FO where quantification over Dedekind-cuts is allowed. We rule out the possibility of a finite-basis for a block-product based characterization of these logical systems. Finally, we report simple but novel algebraic characterizations of one variable fragments of the hierarchies of the new proposed extension of FO.

Miroslav Chodil and Antonin Kucera
The Satisfiability Problem for a Quantitative Fragment of PCTL   Go to Abstract  View video

Abstract: We give a sufficient condition under which every finite-satisfiable formula of a given PCTL fragment has a model with at most doubly exponential number of states (consequently, the finite satisfiability problem for the fragment is in 2-EXPSPACE). The condition is semantic and it is based on enforcing a form of ``progress'' in non-bottom SCCs contributing to the satisfaction of a given PCTL formula. We show that the condition is satisfied by PCTL fragments beyond the reach of existing methods.

Hermann Gruber, Markus Holzer and Simon Wolfsteiner
On Minimizing Regular Expressions Without Kleene Star   Go to Abstract  View video

Abstract: Finite languages lie at the heart of literally every regular expression. Therefore, we investigate the approximation complexity of minimizing regular expressions without Kleene star, or, equivalently, regular expressions describing finite languages. On the side of approximation hardness, given such an expression of size~$s$, we prove that it is impossible to approximate the minimum size required by an equivalent regular expression within a factor of $O\left(\frac{s}{(\log s)^{\delta}}\right)$ if the running time is bounded by a quasipolynomial function depending on $\delta$, for every $\delta>1$, unless the exponential time hypothesis (ETH) fails. For approximation ratio $O(s^{1-\delta})$, we prove an exponential-time lower bound depending on $\delta$, assuming ETH. The lower bounds apply to alphabets of constant size. On the algorithmic side, we show that the problem can be approximated in polynomial time within $O(\frac{s\log\log s}{\log s})$, with~$s$ being the size of the given regular expression. For constant alphabet size, the bound improves to $O(\frac{s}{\log s})$. Finally, we devise a familiy of superpolynomial approximation algorithms with approximation ratios matching the lower bounds, while the running times are just above the lower bounds excluded by the exponential time hypothesis.

14:15-14:30 Break
14:30-15:30 Session 2 [Automata and Complexity] (chair: Stefan Hoffmann)

Henning Fernau and Kshitij Gajjar
The Space Complexity of Sum Labelling   Go to Abstract  View video

Abstract: A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of computational complexity. Note that every n-vertex sum graph can be represented by a sorted list of n positive integers where edge queries can be answered in O(log n) time. Thus, limiting the size of the vertex labels upper bounds the space complexity of storing the graph. We show that every n-vertex, m-edge, d-degenerate graph can be made a sum graph by adding at most m isolated vertices to it such that the size of each vertex label is at most O(n^2d). This enables us to store the graph using O(m log n) bits of memory. For sparse graphs (graphs with O(n) edges), this matches the trivial lower bound of Omega(n log n). Since planar graphs and forests have constant degeneracy, our result implies an upper bound of O(n^2) on their label size. The previously best known upper bound on the label size of general graphs with the minimum number of isolated vertices was O(4^n), due to Kratochvil, Miller & Nguyen. Furthermore, their proof was existential whereas our labelling can be constructed in polynomial time.

Peter Leupold and Sebastian Maneth
Deciding Top-Down Determinism of Regular Tree Languages   Go to Abstract  View video

Abstract: It is well known that for a regular tree language, it is decidable whether or not it can be recognized by a deterministic top-down tree automaton (DTA). However, the computational complexity of this problem has not been studied. We show that for a given deterministic bottom-up tree automaton it can be decided in quadratic time whether or not its language can be recognized by a DTA. Since there are finite tree languages that cannot be recognized by DTAs, we also consider finite unions of DTAs and show that also here, definability within deterministic bottom-up tree automata is decidable in quadratic time.

Markus Lohrey
Complexity of word problems for HNN-extensions   Go to Abstract  View video

Abstract: We study the computational complexity of the word problem in HNN-extension of groups. HNN-extension are a fundamental construction in geometric and combinatorial group theory. We show that the word problem for an ascending HNN-extension of a group H is logspace reducible to the so-called compressed word problem for H. The main result of the paper shows that the word problem for an HNN-extension of a hyperbolic group H, where the associated subgroups are cyclic, can be solved in polynomial time. This result can be easily extended to fundamental groups of graphs of groups, where all vertex nodes are hyperbolic and all edge groups are cyclic.

15:30-16:30 Long Break
16:30-17:50 Session 3 [Automata, Complexity, Formal Methods] (chair: David Richerby)

Jin-Yi Cai, Austen Fan and Yin Liu
Bipartite 3-Regular Counting Problems with Mixed Signs   Go to Abstract  View video

Abstract: We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. For every problem of the form Holant(f | =_3), where f is any integer-valued ternary symmetric constraint function on Boolean variables, we prove that it is either P-time computable or #P-hard, depending on an explicit criterion of f. The constraint function can take both positive and negative values, allowing for cancellations. In addition, we discover a new phenomenon: there is a set F with the property that for every f in F the problem Holant(f |=_3) is planar P-time computable but #P-hard in general, yet its planar tractability is by a combination of a holographic transformation by [1 1 \\ 1 -1] to FKT together with an independent global argument.

Vrunda Dave, Taylor Dohmen, Shankara Narayanan Krishna, Ashutosh Trivedi
Regular Model Checking with Regular Relations   Go to Abstract  View video

Abstract: Regular model checking is an exploration technique for infinite state systems where state spaces are represented as regular languages and transition relations are expressed using rational relations over infinite (or finite) strings. We extend the regular model checking paradigm to permit the use of more powerful transition relations: the class of regular relations, of which the rational relations are a strict subset. We use the language of monadic second-order logic (\mso{}) on infinite strings to specify such relations and adopt streaming string transducers (\sst{}s) as a suitable computational model. We introduce nondeterministic \sst{}s over infinite strings (\wnsst{}s) and show that they precisely capture the relations definable in \mso{}. We further explore theoretical properties of \wnsst{}s required to effectively carry out regular model checking. In particular, we establish that the regular type checking problem for \wnsst{}s is decidable in \pspace{}. Since the post-image of a regular language under a regular relation may not be regular (or even context-free), approaches that iteratively compute the image can not be effectively carried out in this setting. Instead, we utilize the fact that regular relations are closed under composition, which, together with our decidability result, provides a foundation for regular model checking with regular relations.

S. Raja and G. V. Sumukha Bharadwaj
On the Hardness of the Determinant: Sum of Regular Set-Multilinear Circuits   Go to Abstract  View video

Abstract: In this paper, we study the computational complexity of the commutative determinant polynomial computed by a class of set-multilinear circuits which we call regular set-multilinear circuits. Regular set-multilinear circuits are commutative circuits with a restriction on the order in which they can compute polynomials. A regular set-multilinear circuit can be seen as the commutative analogue of the ordered circuit defined by Hrubes, Wigderson and Yehudayoff [HWY10]. We show that if the commutative determinant polynomial has a small representation in the sum of constantly many regular set-multilinear circuits, then the commutative permanent polynomial also has a small arithmetic circuit.

Stefan Hoffmann
Computational Complexity of Synchronization under Sparse Regular Constraints   Go to Abstract  View video

Abstract: The constrained synchronization problem asks for a synchronizing word of a given input automaton contained in a a regular set of constraints. It could be viewed as a special case of synchronization of a discrete event system under supervisory control. Here, we study the computational complexity of the constrained synchronization problem for the class of sparse regular constraint languages. We give a new characterization of sparse regular sets, which equal the bounded regular sets and give a full classification of the computational complexity of the constrained synchronization problem for strictly bounded regular languages. In addition, we derive a polynomial time decision procedure for the complexity of the constrained synchronization problem, given a constraint automaton recognizing a strictly bounded regular language as input. Then, we introduce strongly self-synchronizing codes and investigate the constrained synchronization problem for bounded languages induced by these codes. With our previous result, we deduce a full classification for these languages as well. In both cases, depending on the constraint language, our problem becomes $NP$-complete or polynomial time solvable.

17:50-18:00 Break
18:00-19:00 Plenary Talk II (chair: Stathis Zachos)

Constantinos Daskalakis
Min-Max Optimization: From von Neumann to Deep Learning   View details  View video


Social Programme

The Athenian Acropolis through the Ages (19:30-20:15)
Aristotle Koskinas   Go to Abstract  View video

The Acropolis is one of the most famous Greek landmarks and one of the most historic locations of Athens.
It is the place where the first traces of human habitation in Athens (6 millenia ago) have been found. By Mycaenean times (13th century BCE) the small Neolithic settlement of the 3rd millenium BCE had evolved into a strong citadel.
A few centuries later, in the Geometric Era, the Acropolis became a sanctuary and its transformation into a religious centre began. The first monumental temples were built in the 6th century; after the Persian Wars, the Acropolis began to gradually take the form we know today. Its masterpieces (like the Parthenon and the Propylaea) are considered the best examples of Greek architecture.
The Acropolis changed through the ages, mirroring the history of Athens. During the Middle Ages, its temples were turned into churches, whereas the hill became a castle. Due to its strategic position, its monuments suffered the impact of various conflicts, until the Greek War of Independence; their marks are visible to this day.
The Acropolis of Athens is the city’s symbol. It is also a place enriched by the happy convergence of art, history and mythology.

Aristotle Koskinas studied classical archaeology at the University of Ioannina, Greece. He specialized in the study of architectural terracottas (rooftiles). For several years he participated in various excavations conducted by the Greek Ministry of Culture. He took part in the surface survey project conducted in Western Achaia by the Center for Greek and Roman Studies of the National Research Foundation, as well as in the Sicyon surface survey conducted by the University of Thessaly. He published material from both projects.
In 2003 he graduated from the Greek School of Tourist Guides and has since been working as a guide. He specialises in organising thematic and/or educational tours for interested parties, such as universities, historic societies etc. He has been working closely with several universities, such as the universities of Princeton, Missouri, Longwood, et.al.
He is also an accomplished narrator, and is a regular participant (by invitation of the National Archaeological Museum and the Greek Narration Festival) to participate in their yearly narration events.
He lectures on Greek history and archaeology, while continuing to study and publish material from excavations of the Ministry of Culture. His other interests lay in the field of military history and conflict archaeology and he has been involved in historical reenactment events.

Professional blog

Tuesday, September 14

12:00-13:00 Plenary Talk III (chair: Dimitris Fotakis)

Daniel Marx
Tight complexity results for algorithms using tree decompositions   View details  View video

13:00-13:15 Break
13:15-14:15 Session 4 [Parameterized Complexity and Algorithms] (chair: Henning Fernau)

Lukas Behrendt, Katrin Casel, Tobias Friedrich, J. A. Gregor Lagodzinski, Alexander Löser and Marcus Wilhelm
From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization   Go to Abstract  View video

Abstract: We generalize the tree doubling and Christofides algorithm to parameterized approximations for ATSP. The parameters we consider for the respective generalizations are upper bounded by the number of asymmetric distances in the given instance which yields algorithms to efficiently compute good approximations also for moderately asymmetric TSP instances. As generalization of the Christofides algorithm, we derive a parameterized 2.5-approximation, where the parameter is the size of a vertex cover for the subgraph induced by the asymmetric edges. Our generalization of the tree doubling algorithm gives a parameterized 3-approximation, where the parameter is the minimum number of asymmetric edges in a minimum spanning arborescence. Further, we combine these with a notion of symmetry relaxation which allows to trade approximation guarantee for runtime. Since the two parameters we consider are theoretically incomparable, we present experimental results which show that generalized tree-doubling frequently outperforms generalized Christofides with respect to parameter size.

David Eppstein, Siddharth Gupta and Haleh Havvaei
Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes   Go to Abstract  View video

Abstract: We investigate the parameterized complexity of finding subgraphs with hereditary properties on graphs belonging to a hereditary graph class. Given a graph $G$, a non-trivial hereditary property $\Pi$ and an integer parameter $k$, the general problem $P(G,\Pi,k)$ asks whether there exists $k$ vertices of $G$ that induce a subgraph satisfying property $\Pi$. This problem, $P(G,\Pi,k)$ has been proved to be NPC by Lewis and Yannakakis. The parameterized complexity of this problem is shown to be WO-complete by Khot and Raman, if $\Pi$ includes all trivial graphs but not all complete graphs and vice versa; and is fixed-parameter tractable (FPT), otherwise. As the problem is WO-complete on general graphs when $\Pi$ includes all trivial graphs but not all complete graphs and vice versa, it is natural to further investigate the problem on restricted graph classes. Motivated by this line of research, we study the problem on graphs which also belong to a hereditary graph class and establish a framework which settles the parameterized complexity of the problem for various hereditary graph classes. In particular, we show that:
  • $P(G,\Pi,k)$ is solvable in polynomial time when the graph $G$ is co-bipartite and $\Pi$ is the property of being planar, bipartite or triangle-free (or vice-versa).
  • $P(G,\Pi,k)$ is FPT when the graph $G$ is planar, bipartite or triangle-free and $\Pi$ is the property of being planar, bipartite or triangle-free, or graph $G$ is co-bipartite and $\Pi$ is the property of being co-bipartite.
  • $P(G,\Pi,k)$ is WO-complete when the graph $G$ is $C_4$-free, $K_{1,4}$-free or a unit disk graph and $\Pi$ is the property of being either planar or bipartite.

Jelle Oostveen and Erik Jan van Leeuwen
Streaming Deletion Problems Parameterized by Vertex Cover   Go to Abstract  View video

Abstract: Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work of Bishnu et al. [COCOON 2020]. We show the further potency of combining this parameter with the Adjacency List streaming model to obtain results for vertex deletion problems. This includes kernels, parameterized algorithms, and lower bounds for the problems of Pi-free Deletion, H-free Deletion, and the more specific forms of Cluster Vertex Deletion and Odd Cycle Transversal. We focus on the complexity in terms of the number of passes over the input stream, and the memory used. This leads to a pass/memory trade-off, where a different algorithm might be favourable depending on the context and instance. We also discuss implications for parameterized complexity in the non-streaming setting.

14:15-14:30 Break
14:30-15:30 Session 5 [Multiagent Systems] (chair: Tomasz Radzik)

Joseph Livesey and Dominik Wojtczak
Propositional Gossip Protocols   Go to Abstract  View video

Abstract: Gossip protocols are programs that can be used by a group of agents to synchronize what they know. Namely, assuming each agent holds a secret, the goal of a protocol is to reach a situation in which all agents know all secrets. Distributed epistemic gossip protocols use epistemic formulas in the component programs for the agents. In this paper, we solve open problems regarding one of the simplest classes of gossip protocols: propositional gossip protocols, in which whether an agent wants to make a call depends only on his currently known set of secrets. Specifically, we show that all correct propositional gossip protocols, i.e., ones that always terminate in a situation where all agents know all secrets, require the communication graph to be complete and at least 2n-3 calls to be made in the worst case. We also show that checking correctness of a given propositional gossip protocol is a coNP-complete problem. Finally we report on implementing such a check with model checker nuXmv.

Kyrill Winkler, Ulrich Schmid and Thomas Nowak
Valency-based Consensus under Message Adversaries without Limit-Closure   Go to Abstract  View video

Abstract: We introduce a novel two-step approach for developing a distributed consensus algorithm, which does not require the designer to identify and exploit intricacies of the underlying system model explicitly. In a first step, which is done off-line only once, labels representing valid decision values (valencies) are assigned to suitable prefixes of all possible runs. The challenge here is to assign them consistently for indistinguishable runs. The second step consists in deploying a simple generic distributed consensus algorithm, which just uses the pre-computed labeling. If it observes that all runs that may lead to a local state that is indistinguishable from the current local state have the same label, it decides on this label, otherwise it has to keep on checking. We demonstate the power of our approach by developing a new and asymptotically optimal algorithm for eventually stabilizing message adversaries for arbitrary system sizes.

Kristoffer Arnsfelt Hansen and Troels Bjerre Lund
Computational Complexity of Computing a Quasi-Proper Equilibrium   Go to Abstract  View video

Abstract: We study the computational complexity of computing or approximating a quasi-proper equilibrium for a given finite extensive form game of perfect recall. We show that the task of computing a symbolic quasi-proper equilibrium is PPAD-complete for two-player games. For the case of zero-sum games we obtain a polynomial time algorithm based on Linear Programming. For general n-player games we show that computing an approximation of a quasi-proper equilibrium is FIXPₐ-complete. Towards our results for two-player games we devise a new perturbation of the strategy space of an extensive form game which in particular gives a new proof of existence of quasi-proper equilibria for general n-player games.

15:30-16:30 Long Break
16:30-17:50 Session 6 [Graph (Algorithms) I] (chair: Ralf Klasing)

Alessio Conte, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis and Giulia Punzi
Beyond the BEST Theorem: Fast Assessment of Eulerian Trails   Go to Abstract  View video

Abstract: Given a directed multigraph G=(V,E), with |V|=n nodes and |E|=m edges, and an integer z, we are asked to assess whether the number #ET(G) of node-distinct Eulerian trails of G is at least z; two trails are called node-distinct if their node sequences are different. This problem has been formalized by Bernardini et al.~[ALENEX 2020] as it is the core computational problem in several string processing applications. It can be solved in O(n^{\omega}) arithmetic operations by applying the well-known BEST theorem, where \omega<2.373 denotes the matrix multiplication exponent. The algorithmic challenge is: Can we solve this problem faster for certain values of m and z? Namely, we want to design a combinatorial algorithm for assessing whether #ET(G)>= z, which does not resort to the BEST theorem and has a predictably bounded cost as a function of m and z. We address this challenge by providing an algorithm requiring O(m min{z, #ET(G)}) time. This bound is time-optimal for z=O(1) or for #ET(G)=O(1). The impact of our result on real-world graphs is striking: a simple implementation of our algorithm takes tens of seconds to assess #ET(G) >= z, whereas a highly-optimized implementation of the BEST theorem requires more than 12 hours.

Nicolas Bousquet and Alice Joffard
TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs   Go to Abstract  View video

Abstract: We study the dominating set reconfiguration problem with the token sliding rule. It consists, given a graph $G=(V,E)$ and two dominating sets $D_s$ and $D_t$ of $G$, in determining if there exists a sequence $S=\langle D_1:=D_s,...,D_{\ell}:=D_t\rangle$ of dominating sets of $G$ such that for any two consecutive dominating sets $D_r$ and $D_{r+1}$ with $r \le t$, $D_{r+1}=(D_r\setminus u) \cup v$, where $uv\in E$. In a recent paper, Bonamy et al. studied this problem and raised the following questions: what is the complexity of this problem on circular arc graphs? On circle graphs? In this paper, we answer both questions by proving that the problem is polynomial on circular-arc graphs and PSPACE-complete on circle graphs.

Allen Ibiapina and Ana Silva
Mengerian Temporal Graphs Revisited   Go to Abstract  View video

Abstract: A temporal graph G is a graph that changes with time. More specifically, it is a pair (G, λ) where G is a graph and λ is a function on the edges of G that describes when each edge e ∈ E(G) is active. Given vertices s,t ∈ V(G), a temporal s,t-path is a path in G that traverses edges in non-decreasing time; and if s,t are non-adjacent, then a vertex temporal s,t-cut is a subset S ⊆ V(G) whose removal destroys all temporal s,t-paths. It is known that Menger’s Theorem does not hold on this context, i.e., that the maximum number of vertex disjoint temporal s,t-paths is not necessarilly equal to the minimum size of a vertex temporal s,t-cut. In a seminal paper, Kempe, Kleinberg and Kumar (STOC’2000) defined a graph G to be Mengerian if equality holds on (G, λ) for every function λ. They then proved that, if each edge is allowed to be active only once in (G, λ), then G is Mengerian if and only if G has no gem as topological minor. In this paper, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We also provide a polynomial time recognition algorithm.

Svein Høgemo, Benjamin Bergougnoux, Ulrik Brandes, Christophe Paul and Jan Arne Telle
On Dasgupta’s hierarchical clustering objective and its relation to other graph parameter   Go to Abstract  View video

Abstract: The minimum height of vertex and edge partition trees are well-studied graph parameters known as, for instance, vertex and edge ranking number. While they are NP-hard to determine in general, linear-time algorithms exist for trees. Motivated by a correspondence with Dasgupta's objective for hierarchical clustering we consider the total rather than maximum depth of vertices as an alternative objective for minimization. For vertex partition trees this leads to a new parameter with a natural interpretation as a measure of robustness against vertex removal. As tools for the study of this family of parameters we show that they have similar recursive expressions and prove a binary tree rotation lemma. The new parameter is related to trivially perfect graph completion and therefore intractable like the other three are known to be. We give polynomial-time algorithms for both total-depth variants on caterpillars and on trees with a bounded number of leaf neighbors. For general trees, we obtain a 2-approximation algorithm.

17:50-18:00 Break
18:00-19:00 Business Meeting
19:15-20:00 Social Programme

Wednesday, September 15

12:00-13:00 Plenary Talk IV (chair: Evripidis Bampis)

Claire Mathieu
Stable matchings beyond worst case   View details  View video

13:00-13:15 Break
13:15-14:35 Session 7 [Graph (Algorithms) II] (chair: Thanasis Lianeas)

Sanjana Dey, Anil Maheshwari and Subhas Nandy
Minimum Consistent Subset of Trees   Go to Abstract  View video

Abstract: In the minimum consistent subset (MCS) problem, a connected simple undirected graph $G=(V, E)$ is given whose each node is colored by one of the colors $\{c_1,c_2,\ldots, c_k\}$; the objective is to compute a subset ${\cal C} \subseteq V$ such that for each node $v \in V$, one of its nearest neighbors in ${\cal C}$ (with respect to the hop-distance) is of the same color as of $v$. The decision version of the MCS problem is NP-complete even for planar graphs. We propose a polynomial-time algorithm when the graph $G$ is a bichromatic tree.

Christophe Crespelle
Linear-Time Minimal Cograph Editing   Go to Abstract  View video

Abstract: We present an algorithm for computing a minimal editing of an arbitrary graph G into a cograph, i.e. a set of edits (additions and deletions of edges) that turns G into a cograph and that is minimal for inclusion. Our algorithm runs in linear time in the size of the input graph, that is O(n+m) time where n and m are the number of vertices and the number of edges of G, respectively.

Max Bender, Jacob Gilbert, Kirk Pruhs
A Poly-Log Competitive Posted-Price Algorithm for Online Metrical Matching on a Spider   Go to Abstract  View video

Abstract: Motivated by demand-responsive parking pricing systems we consider posted-price algorithms for the online metrical matching problem. Our main result is a poly-log competitive posted-price algorithm in the case that the metric space is a spider.

Jesper Jansson and Wing Lik Lee
Fast Algorithms for the Rooted Triplet Distance Between Caterpillars   Go to Abstract  View video

Abstract: The rooted triplet distance measures the structural dissimilarity between two rooted phylogenetic trees (unordered trees with distinct leaf labels and no outdegree-1 nodes) having the same leaf label set. It is defined as the number of 3-subsets of the leaf label set that induce two different subtrees in the two trees. The fastest currently known algorithm for computing the rooted triplet distance was designed by Brodal et al. (SODA 2013). It runs in O(n log n) time, where n is the number of leaf labels in the input trees, and a long-standing open question is whether this is optimal or not. In this paper, we present two new o(n log n)-time algorithms for the special case of caterpillars (rooted phylogenetic trees in which every node has at most one non-leaf child), thus breaking the O(n log n)-time bound for a fundamental class of trees. Our first algorithm makes use of a dynamic rank-select data structure by Raman et al. (WADS 2001) and runs in O(n log n / loglog n) time. Our second algorithm relies on an efficient algorithm for orthogonal range counting invented by Chan and Patrascu (SODA 2010) and runs in O(n sqrt{log n}) time.

14:35-15:15 Long Break
15:15-16:15 Session 8 [Complexity and Randomness] (chair: Nikos Leonardos)

Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl and Michaela Seifrtová
Computational Complexity of Covering Disconnected Multigraphs   Go to Abstract  View video

Abstract: The notion of graph covers is a discretization of covering spaces introduced and deeply studied in topology. In discrete mathematics and theoretical computer science, they have attained a lot of attention from both the structural and complexity perspectives. Nonetheless, disconnected graphs were usually omitted from the considerations with the explanation that it is sufficient to understand coverings of the connected components of the target graph by components of the source one. However, different (but equivalent) versions of the definition of covers of connected graphs generalize to nonequivalent definitions of disconnected graphs. The aim of this paper is to summarize this issue and to compare three different approaches to covers of disconnected graphs: 1) locally bijective homomorphisms, 2) globally surjective locally bijective homomorphisms (which we call \emph{surjective covers}), and 3) locally bijective homomorphisms which cover every vertex the same number of times (which we call \emph{equitable covers}). The standpoint of our comparison is the complexity of deciding if an input graph covers a fixed target graph. We show that both surjective and equitable covers satisfy what certainly is a natural and welcome property: covering a disconnected graph is polynomial time decidable if such it is for every connected component of the graph, and it is NP-complete if it is NP-complete for at least one of its components. Despite of this, we argue that the third variant, equitable covers, is the right one, when considering covers of colored (multi)graphs. Moreover, the complexity of surjective and equitable covers differ from the fixed parameter complexity point of view. We conclude the paper by a complete characterization of the complexity of covering 2-vertex colored multigraphs with semi-edges. We present the results in the utmost generality and strength. In accord with the current trends we consider (multi)graphs with semi-edges, and, on the other hand, we aim at proving the NP-completeness results for simple input graphs.

Piotr Borowiecki, Dariusz Dereniowski and Dorota Osula
The Complexity of Bicriteria Tree-depth   Go to Abstract  View video

Abstract: The tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph $G$. We introduce a bicriteria generalization in which additionally the \emph{width} of the elimination tree needs to be bounded by some input integer $b$. We are interested in the case when $G$ is the line graph of a tree, proving that the problem is $\NP$-hard and obtaining a polynomial-time additive $2b$-approximation algorithm. This particular class of graphs received significant attention, mainly due to a number of potential applications, e.g. in parallel assembly of modular products, or parallel query processing in relational databases, as well as purely combinatorial applications, e.g. searching in tree-like partial orders (which generalizes binary search on sorted data).

Maciej Skorski
Concentration of Collision Estimator   Go to Abstract  View video

Abstract: This paper analyzes in detail the concentration properties of the collision estimator inspired by the birthday-paradox.

16:15-16:30 Break
16:30-18:00 Session 9 [Best Papers]

Best Student Paper I
Ashwin Jacob, Diptapriyo Majumdar and Venkatesh Raman
Faster FPT Algorithms for Deletion to Pairs of Graph Classes   Go to Abstract  View video

Abstract: Let $\Pi$ be a hereditary graph class. The problem of deletion to $\Pi$, takes as input a graph $G$ and asks for a minimum number (or a fixed integer $k$) of vertices to be deleted from $G$ so that the resulting graph belongs to $\Pi$. This is a well-studied problem in paradigms including approximation and parameterized complexity. This problem, for example, covers {\sc vertex cover}, {\sc feedback vertex set}, {\sc cluster vertex deletion}, {\sc perfect deletion} to name a few. The study of this problem in parameterized complexity has resulted in several powerful algorithmic techniques including iterative compression and important separators. It has long been known that the problem is fixed-parameter tractable (FPT) as long as $\Pi$ has a finite forbidden set. When $\Pi$ has an infinite forbidden set (for example, when $\Pi$ is the class of forests or perfect graphs), both hardness and FPT results are known for specific graph classes. Recently (IPEC 2020, arxiv.org/abs/2105.04660), the study of a natural extension of the problem was initiated. In that problem, we are given a finite set of hereditary graph classes, and the input is an undirected graph. The goal is to determine whether $k$ vertices can be deleted from the given graph, so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem has been shown to be FPT as long as the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph class can be expressible in the counting monodic second order (CMSO) logic. While this was shown using some black box theorems, faster algorithms were shown when each of the hereditary graph classes has a finite forbidden set. In this paper, we do a deep dive on pairs of specific graph classes ($\Pi_1, \Pi_2$) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. We design two general algorithms for pairs of graph classes (possibly having infinite forbidden sets) satisfying certain conditions on their forbidden sets. Our first general method covers pairs of graph classes including (Interval, Trees), (Proper Interval, Trees) and (Chordal, Bipartite Permutation) and the second covers (Clique, Planar) and (Clique, Bounded Treewidth) for ($\Pi_1$, $\Pi_2$). Our algorithms make non-trivial use of the branching technique and as black box, FPT algorithms for deletion to individual graph classes.

Best Student Paper II
Nicolas Maack, Hendrik Molter, Rolf Niedermeier and Malte Renken
On Finding Separators in Temporal Split and Permutation Graphs   Go to Abstract  View video

Abstract: Removing all connections between two vertices s and z in a graph by removing a minimum number of vertices is a fundamental problem in algorithmic graph theory. This (s,z)-separation problem is well-known to be polynomial solvable and serves as an important primitive in many applications related to network connectivity. We study the NP-hard temporal (s,z)-separation problem on temporal graphs, which are graphs with fixed vertex sets but edge sets that change over discrete time steps. We tackle this problem by restricting the layers (i.e., graphs characterized by edges that are present at a certain point in time) to specific graph classes. We restrict the layers of the temporal graphs to be either all split graphs or all permutation graphs (both being perfect graph classes) and provide both intractability and tractability results. In particular, we show that in general the problem remains NP-hard both on temporal split and temporal permutation graphs, but we also spot promising islands of fixed-parameter tractability particularly based on parameterizations that measure the amount of "change over time".

Best Paper
Marc Neveling, Jörg Rothe and Robin Weishaupt
The Possible Winner Problem with Uncertain Weights Revisited   Go to Abstract  View video

Abstract: Baumeister et al. [7] introduced the possible winner with uncertain weights problem which, given a weighted election with the weights of some voters as yet unspecified, asks whether one can assign weights to these voters such that a distinguished candidate wins. Solving all questions they specifically left open for nonnegative integer weights, we show that two variants of this problem for 3-approval and four variants for plurality with runoff can be solved efficiently. In addition, we study variants of this problem for Borda, k-veto, and veto with runoff in terms of their computational complexity. Finally, we also prove that the problem of constructive control by adding voters in succinct representation belongs to P for plurality with runoff and veto with runoff.

18:00-18:30 Closing-Farewell