MFCS 2019 Accepted Papers

Erhard Aichinger. Systems of equations in supernilpotent algebras
Nathalie Aubrun, Sebastián Barbieri and Etienne Moutot. The Domino Problem is Undecidable on Surface Groups
Zeev Nutov, Guy Kortsarz and Eli Shalom. Approximating activation edge-cover and facility location problems
Titus Dose. P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-pairs Relative to an Oracle
Emanuel Kieronski. One-dimensional guarded fragments
Radovan Červený and Ondrej Suchy. Faster FPT Algorithm for 5-Path Vertex Cover
Victor Lagerkvist and Gustav Nordh. On the Strength of Uniqueness Quantification in Primitive Positive Formulas
Dušan Knop, Tomáš Masařík and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems
Markus Lohrey and Armin Weiss. The power word problem
Jessica Enright, Kitty Meeks, George Mertzios and Viktor Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks
Murilo de Lima and Magnús Halldórsson. Query-Competitive Sorting with Uncertainty
Haruka Mizuta, Tatsuhiko Hatanaka, Takehiro Ito and Xiao Zhou. Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
Daniel Danielski and Emanuel Kieronski. Finite Satisfiability of Unary Negation Fragment with Transitivity
Patricia Bouyer and Nathan Thomasset. Nash equilibria in games over graphs equipped with a communication mechanism
Lidia Tendera and Ian Pratt-Hartmann. Fluted Fragment with Transitivity
Paweł Parys. Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
Nathan Lhote, Vincent Michielini and Michał Skrzypczak. Uniformisation gives the full strength of regular languages
Athanasios Konstantinidis and Charis Papadopoulos. Cluster Deletion on Interval Graphs and Split Related Graphs
Titouan Carette, Dominic Horsman and Simon Perdrix. SZX-calculus: Scalable Graphical Quantum Reasoning
Olivier Bournez and Arnaud Durand. Recursion schemes, discrete differential equations and characterization of polynomial time computation
Marcin Bienkowski and Hsiang-Hsuan Liu. An Improved Online Algorithm for Traveling Repairperson Problem on a Line
Sankardeep Chakraborty and Kunihiko Sadakane. Indexing Graph Search Trees and Applications
Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Muehlenthaler and Kunihiro Wasa. The Perfect Matching Reconfiguration Problem
Christoph Berkholz and Nicole Schweikardt. Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
Evripidis Bampis, Bruno Escoffier and Alexandre Teiller. Multistage Knapsack
Torben Hagerup. A Constant-Time Colored Choice Dictionary with Almost Robust Iteration
Ishay Haviv. Approximating the Orthogonality Dimension of Graphs and Hypergraphs
Michele Boreale. On the coalgebra of partial differential equations
Wojciech Czerwiński, Sławomir Lasota, Christof Löding and Radosław Piórkowski. New Pumping Technique for 2-dimensional VASS
Guy Avni, Thomas Henzinger and Djordje Zikelic. Bidding Mechanisms in Graph Games
Diego Figueira, Varun Ramanathan and Pascal Weil. The Quantifier Alternation Hierarchy of Synchronous Relations
Ziyuan Gao, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Alexander Melnikov, Karen Seidel and Frank Stephan. Random subgroups of rationals
Alberto Dennunzio, Enrico Formenti, Darij Grinberg and Luciano Margara. Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties
Nicola Galesi, Dmitry Itsykson, Artur Riazanov and Anastasia Sofronova. Bounded-depth Frege complexity of Tseitin formulas for all graphs
Julian Dörfler, Marc Roth, Johannes Schmitt and Philip Wellnitz. Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness
Anantha Padmanabha and R. Ramanujam. Two variable fragment of Term Modal Logic
Christian Konrad and Viktor Zamaraev. Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
Hoang-Oanh Le and Van Bang Le. Constrained representations of map graphs and half-squares
Jan Boeker, Yijia Chen, Martin Grohe and Gaurav Rattan. The Complexity of Homomorphism Indistinguishability
Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut and Meirav Zehavi. Packing Arc-Disjoint Cycles in Tournaments
Carl Einarson and Felix Reidl. Domination above $r$-independence: does sparseness help?
Anselm Haak, Juha Kontinen, Fabian Müller, Heribert Vollmer and Fan Yang. Counting of Teams in First-Order Team Logics
Pierre Clairambault and Andrzej Murawski. On the expressivity of linear recursion schemes
Jayakrishnan Madathil, Roohani Sharma and Meirav Zehavi. A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs
Esther Galby, Paloma de Lima and Bernard Ries. Reducing the domination number of graphs via edge contractions
Lars Jaffke and Paloma de Lima. A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
Charlie Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura and Alexandra Kolla. Spectral Aspects of Symmetric Matrix Signings
Nikhil Gupta and Chandan Saha. On the symmetries of and equivalence test for design polynomials
Stefan Kiefer and Cas Widdershoven. Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques
Pierre Ganty, Elena Gutiérrez and Pedro Valero. A Congruence-based Perspective on Automata Minimization Algorithms
Paul Bell and Mika Hirvensalo. Acceptance Ambiguity for Quantum Automata
Paul Bell, Igor Potapov and Pavel Semukhin. On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond
Henning Fernau, Vladimir V. Gusev, Stefan Hoffmann, Markus Holzer, Mikhail V. Volkov and Petra Wolf. Computational Complexity of Synchronization under Regular Constraints
Florent Koechlin, Cyril Nicaud and Pablo Rotondo. Uniform Random Expressions Lack Expressivity
Sougata Bose, Krishna Shankara Narayanan, Anca Muscholl, Vincent Penelle and Gabriele Puppis. On Synthesis of Resynchronizers for Transducers
Andrei Bulatov and Amirhossein Kazeminia. Counting Homomorphisms Modulo a Prime Number
Elisabet Burjons Pujol, Fabian Frei, Edith Hemaspaandra, Dennis Komm and David Wehner. Finding Optimal Solutions With Neighborly Help
Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Christian Coester, Łukasz Jeż and Elias Koutsoupias. Better Bounds for Online Line Chasing
Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer and Csaba Toth. On the Stretch Factor of Polygonal Chains
Andrei Bulatov and Stanislav Živný. Approximate counting CSP seen from the other side
Théodore Lopez, Benjamin Monmege and Jean-Marc Talbot. Determinisation of Finitely-Ambiguous Copyless Cost Register Automata
Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh and Saket Saurabh. Parameterized Complexity of Conflict-Free Matchings and Paths
Mathieu Hoyrup and Donald Stull. Semicomputable points in Euclidean spaces
Erich Grädel and Svenja Schalthöfer. Choiceless Logarithmic Space
Philip Bille and Inge Li Gørtz. From Regular Expression Matching to Parsing
Surender Baswana, Shiv Gupta and Ayush Tulsyan. Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient
Joel Day, Florin Manea and Dirk Nowotka. Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations
Alessio Conte, Roberto Grossi, Mamadou Moustapha Kanté, Andrea Marino, Takeaki Uno and Kunihiro Wasa. Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs
Barnaby Martin, Daniel Paulusma and Siani Smith. Colouring H-free Graphs of Bounded Diameter
Raphael Clifford, Paweł Gawrychowski, Tomasz Kociumaka, Daniel Martin and Przemysław Uznański. RLE edit distance in near optimal time
Eduard Eiben, Robert Ganian, Thekla Hamm and O-Joung Kwon. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
Sandra Kiefer and Daniel Neuen. The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
Serge Gaspers and Ray Li. Enumeration of Preferred Extensions in Almost Oriented Digraphs
C Ramya and Raghavendra Rao B V. Lower bounds for multilinear order-restricted ABPs
Victor Chepoi, Arnaud Labourel and Sébastien Ratel. Distance labeling schemes for cube-free median graphs
Manfred Droste and Paul Gastin. Aperiodic Weighted Automata and Weighted First-Order Logic
Michal Garlík. Resolution Lower Bounds for Refutation Statements
Eva Fluck. Tangles and Single Linkage Hierarchical Clustering