FCT 2021

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

FCT 2021 Accepted Papers

FCT 2021 Accepted Papers (in submission order)

Jin-Yi Cai, Austen Fan and Yin Liu. Bipartite 3-Regular Counting Problems with Mixed Signs
Bharat Adsul, Saptarshi Sarkar and A V Sreejith. First-Order logic and its Infinitary Quantifier Extensions over Countable Words
Alessio Conte, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis and Giulia Punzi. Beyond the BEST Theorem: Fast Assessment of Eulerian Trails
Markus Lohrey. Complexity of word problems for HNN-extensions
Kyrill Winkler, Ulrich Schmid and Thomas Nowak. Valency-based Consensus under Message Adversaries without Limit-Closure
Hermann Gruber, Markus Holzer and Simon Wolfsteiner. On Minimizing Regular Expressions Without Kleene Star
Jelle Oostveen and Erik Jan van Leeuwen. Streaming Deletion Problems Parameterized by Vertex Cover
Christophe Crespelle. Linear-Time Minimal Cograph Editing
Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl and Michaela Seifrtová. Computational Complexity of Covering Disconnected Multigraphs
Peter Leupold and Sebastian Maneth. Deciding Top-Down Determinism of Regular Tree Languages
Jesper Jansson and Wing Lik Lee. Fast Algorithms for the Rooted Triplet Distance Between Caterpillars
Marc Neveling, Jörg Rothe and Robin Weishaupt. The Possible Winner Problem with Uncertain Weights Revisited
Piotr Borowiecki, Dariusz Dereniowski and Dorota Osula. The Complexity of Bicriteria Tree-depth
David Eppstein, Siddharth Gupta and Haleh Havvaei. Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes
Henning Fernau and Kshitij Gajjar. The Space Complexity of Sum Labelling
Sanjana Dey, Anil Maheshwari and Subhas Nandy. Minimum Consistent Subset of Trees
Allen Ibiapina and Ana Silva. Mengerian Temporal Graphs Revisited
Nicolas Maack, Hendrik Molter, Rolf Niedermeier and Malte Renken. On Finding Separators in Temporal Split and Permutation Graphs
Max Bender, Kirk Pruhs and Jacob Gilbert. A Poly-Log Competitive Posted-Price Algorithm for Online Metrical Matching on a Spider
Stefan Hoffmann. Computational Complexity of Synchronization under Sparse Regular Constraints
Taylor Dohmen, Ashutosh Trivedi, Krishna S and Vrunda Dave. Regular Model Checking with Regular Relations
Nicolas Bousquet and Alice Joffard. TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs
Ashwin Jacob, Diptapriyo Majumdar and Venkatesh Raman. Faster FPT Algorithms for Deletion to Pairs of Graph Classes
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
Svein Høgemo, Benjamin Bergougnoux, Ulrik Brandes, Christophe Paul and Jan Arne Telle. On Dasgupta’s hierarchical clustering objectiveand its relation to other graph parameter
Kristoffer Arnsfelt Hansen and Troels Bjerre Lund. Computational Complexity of Computing a Quasi-Proper Equilibrium
Miroslav Chodil and Antonin Kucera. The Satisfiability Problem for a Quantitave Fragment of PCTL
S Raja and G. V. Sumukha Bharadwaj. On the Hardness of the Determinant: Sum of Regular Set-Multilinear Circuits
Maciej Skorski. Concentration of Collision Estimator
Joseph Livesey and Dominik Wojtczak. Propositional Gossip Protocols