MFCS 2019 is organized in cooperation with EATCS




Preliminary Conference Program
Program Overview

Monday 
Tuesday 
Wednesday 
Thursday 
Friday 
time 
(August 26th) 
(August 27th) 
(August 28th) 
(August 29th) 
(August 30th) 
08:2008:50 
Registration 
Registration & Refreshments 
08:5009:00 
Opening 
09:0010:00 
Invited Talk: Kurt Mehlhorn 
Invited Talk: Alexandra Silva 
Invited Talk: Daniel Lokshtanov 
Invited Talk: Kavitha Telikepalli 
Invited Talk: Jérôme Leroux 
10:0010:40 
Coffee Break 
10:4012:00 
Session 1A/1B 
Session 4A/4B 
Session 7A/7B 
Session 9A/9B 
Session 12A/12B 
Closing 
12:0014:00 
Lunch 
14:0015:40 
Session 2A/2B 
Session 5A/5B 
Session 8A/8B 
Session 10A/10B 
Workshops: ARDA 2019 Fri. 14:00  19:00 Structural Sparseness Fri. 14:00  19:00 Sat. 9:00  16:00 
15:4016:10 
Coffee Break 
16:1017:30 
Session 3A/3B 
Session 6A/6B 
16:30 Social Program & Conference Dinner 
Session 11A/11B 

17:30 Welcome reception 

Monday, August 26th 
08:20  08:50 
Registration & Refreshments 
08:50  09:00 
Opening 
09:00  10:00 
Invited Talk: Kurt Mehlhorn Trustworthy Graph Algorithms 
10:00  10:40 
Coffee Break 
10:40  12:00 
1A  Online Algorithms 
1B  Games 

M. Bieńkowski, H. Liu An Improved Online Algorithm for Traveling Repairperson Problem on a Line 
P. Bouyer, N. Thomasset Nash equilibria in games over graphs equipped with a communication mechanism 

M. de Lima, M. Halldórsson QueryCompetitive Sorting with Uncertainty 
P. Parys Parity Games: Zielonka's Algorithm in QuasiPolynomial Time 

M. Bieńkowski, J. Byrka, M. Chrobak, C. Coester, Ł. Jeż, E. Koutsoupias Better Bounds for Online Line Chasing 
G. Avni, T. Henzinger, D. Žikelić Bidding Mechanisms in Graph Games 
12:00  14:00 
Lunch 
14:00  15:40 
2A  Graph Algorithms 
2B  FirstOrder Logic 

A. Konstantinidis, C. Papadopoulos Cluster Deletion on Interval Graphs and Split Related Graphs 
E. Kieroński Onedimensional guarded fragments 

H. Le, V. Bang Le Constrained representations of map graphs and halfsquares 
D. Danielski, E. Kieroński Finite Satisfiability of Unary Negation Fragment with Transitivity 

B. Martin, D. Paulusma, S. Smith Colouring Hfree Graphs of Bounded Diameter 
L. Tendera, I. PrattHartmann Fluted Fragment with Transitivity 

V. Chepoi, A. Labourel, S. Ratel Distance labeling schemes for cubefree median graphs 
A. Haak, J. Kontinen, F. Müller, H. Vollmer, F. Yang Counting of Teams in FirstOrder Team Logics 
15:40  16:10 
Coffee Break 
16:10  17:30 
3A  Approximation Algorithms 
3B  Algebraic and Differential Equations 

Z. Nutov, G. Kortsarz, E. Shalom Approximating activation edgecover and facility location problems 
O. Bournez, A. Durand Recursion schemes, discrete differential equations and characterization of polynomial time computation 

C. Konrad, V. Zamaraev Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs 
M. Boreale On the coalgebra of partial differential equations 

E. Bampis, B. Escoffier, A. Teiller Multistage Knapsack 
Z. Gao, S. Jain, B. Khoussainov, W. Li, A. Melnikov, K. Seidel, F. Stephan Random subgroups of rationals 
17:30 
Welcome Reception 

Tuesday, August 27th 
08:20  09:00 
Registration & Refreshments 
09:00  10:00 
Invited Talk: Alexandra Silva Guarded Kleene Algebra with Tests: Verification of Uninterpreted Programs in Nearly Linear Time 
10:00  10:40 
Coffee Break 
10:40  12:00 
4A  Parameterized Algorithms I 
4B  Logic I 

J. Dörfler, M. Roth, J. Schmitt, P. Wellnitz Counting Induced Subgraphs: An Algebraic Approach to #W[1]hardness 
D. Figueira, V. Ramanathan, P. Weil The Quantifier Alternation Hierarchy of Synchronous Relations 

S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, M. Zehavi Packing ArcDisjoint Cycles in Tournaments 
A. Padmanabha, R. Ramanujam Two variable fragment of Term Modal Logic 

J. Madathil, R. Sharma, M. Zehavi A Subexponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs 
E. Grädel, S. Schalthöfer Choiceless Logarithmic Space 
12:00  14:00 
Lunch 
14:00  15:40 
5A  Parameterized Algorithms II 
5B  Logic II + Approximation 

R. Červený, O. Suchy Faster FPT Algorithm for 5Path Vertex Cover 
V. Lagerkvist, G. Nordh On the Strength of Uniqueness Quantification in Primitive Positive Formulas 

D. Knop, T. Masařík, T. Toufar Parameterized Complexity of Fair Vertex Evaluation Problems 
M. Garlík Resolution Lower Bounds for Refutation Statements 

L. Jaffke, P. Thome de Lima A Complexity Dichotomy for Critical Values of the bChromatic Number of Graphs 
E. Fluck Tangles and Single Linkage Hierarchical Clustering 

A. Agrawal, P. Jain, L. Kanesh, S. Saurabh Parameterized Complexity of ConflictFree Matchings and Paths 
I. Haviv Approximating the Orthogonality Dimension of Graphs and Hypergraphs 
15:40  16:10 
Coffee Break 
16:10  17:30 
6A  Parameterized Algorithms III 
6B  Graphs, Groups and Words 

C. Einarson, F. Reidl Domination above rindependence: Does sparseness help? 
M. Lohrey, A. Weiß The power word problem 

E. Galby, P. Thome de Lima, B. Ries Reducing the domination number of graphs via edge contractions 
J. Day, F. Manea, D. Nowotka Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations 

E. Eiben, R. Ganian, T. Hamm, O. Kwon Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth 
S. Kiefer, D. Neuen The Power of the WeisfeilerLeman Algorithm to Decompose Graphs 

Wednesday, August 28th 
08:20  09:00 
Registration & Refreshments 
09:00  10:00 
Invited Talk: Daniel Lokshtanov Picking Random Vertices 
10:00  10:40 
Coffee Break 
10:40  12:00 
7A  Complexity & Decidability I 
7B  Expressability 

N. Aubrun, S. Barbieri, E. Moutot The Domino Problem is Undecidable on Surface Groups 
N. Galesi, D. Itsykson, A. Riazanov, A. Sofronova Boundeddepth Frege complexity of Tseitin formulas for all graphs 

T. Dose POptimal Proof Systems for Each NPSet but no Complete Disjoint NPpairs Relative to an Oracle 
P. Clairambault, A. Murawski On the expressivity of linear recursion schemes 

M. Hoyrup, D. Stull Semicomputable points in Euclidean spaces 
F. Koechlin, C. Nicaud, P. Rotondo Uniform Random Expressions Lack Expressivity 
12:00  14:00 
Lunch 
14:00  15:20 
8A  Complexity & Decidability II 
8B  Temporal, Geometric and Quantum Algorithms 

C. Ramya, R. Rao B V Lower bounds for multilinear orderrestricted ABPs 
T. Carette, D. Horsman, S. Perdrix SZXcalculus: Scalable Graphical Quantum Reasoning 

N. Gupta, C. Saha On the symmetries of and equivalence test for design polynomials 
K. Chen, A. Dumitrescu, W. Mulzer, C. Toth On the Stretch Factor of Polygonal Chains 

J. Böker, Y. Chen, M. Grohe, G. Rattan The Complexity of Homomorphism Indistinguishability 
J. Enright, K. Meeks, G. Mertzios, V. Zamaraev Deleting edges to restrict the size of an epidemic in temporal networks 
15:20  16:15 
Coffee Break 
16:15  22:00 
Social Event & Conference Dinner 

Thursday, August 29th 
08:20  09:00 
Registration & Refreshments 
09:00  10:00 
Invited Talk: Kavitha Telikepalli Popular Matchings: Good, Bad, and Mixed 
10:00  10:40 
Coffee Break 
10:40  12:00 
9A  Counting and Enumeration 
9B  Automata and Formal Languages I 

C. Berkholz, N. Schweikardt Constant delay enumeration with FPTpreprocessing for conjunctive queries of bounded submodular width 
N. Lhote, V. Michielini, M. Skrzypczak Uniformisation gives the full strength of regular languages 

A. Bulatov, A. Kazeminia Counting Homomorphisms Modulo a Prime Number 
W. Czerwiński, S. Lasota, C. Löding, R. Piórkowski New Pumping Technique for 2dimensional VASS 

A. Bulatov, S. Živný Approximate counting CSP seen from the other side 
H. Fernau, V. V. Gusev, S. Hoffmann, M. Holzer, M. V. Volkov, P. Wolf Computational Complexity of Synchronization under Regular Constraints 
12:00  14:00 
Lunch 
14:00  15:40 
10A  Faster Algorithms 
10B  Automata and Formal Languages II 

T. Hagerup A ConstantTime Colored Choice Dictionary with Almost Robust Iteration 
A. Dennunzio, E. Formenti, D. Grinberg, L. Margara Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties 

S. Baswana, S. Gupta, A. Tulsyan Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient 
S. Bose, K. Shankara Narayanan, A. Muscholl, V. Penelle, G. Puppis On Synthesis of Resynchronizers for Transducers 

R. Clifford, P. Gawrychowski, T. Kociumaka, D. Martin, P. Uznański RLE edit distance in near optimal time 
P. Bell, M. Hirvensalo Acceptance Ambiguity for Quantum Automata 

S. Chakraborty, K. Sadakane Indexing Graph Search Trees and Applications 
P. Bille, I. Li Gørtz From Regular Expression Matching to Parsing 
15:40  16:10 
Coffee Break 
16:10  17:30 
11A  Combinatorial Algorithms 
11B  Automata and Formal Languages III 

E. Aichinger Solving systems of equations in supernilpotent algebras 
T. Lopez, B. Monmege, J. Talbot Determinisation of FinitelyAmbiguous Copyless Cost Register Automata 

A. Conte, R. Grossi, M. Moustapha Kanté, A. Marino, T. Uno, K. Wasa Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs 
M. Droste, P. Gastin Aperiodic Weighted Automata and Weighted FirstOrder Logic 

S. Gaspers, R. Li Enumeration of Preferred Extensions in Almost Oriented Digraphs 
P. Ganty, E. Gutiérrez, P. Valero A Congruencebased Perspective on Automata Minimization Algorithms 

Friday, August 30th 
08:20  09:00 
Registration & Refreshments 
09:00  10:00 
Invited Talk: Jérôme Leroux Petri Net Reachability Problem 
10:00  10:40 
Coffee Break 
10:40  12:00 
12A  Reconfiguration problems 
12B  Matrices 

E. Burjons Pujol, F. Frei, E. Hemaspaandra, D. Komm, D. Wehner Finding Optimal Solutions With Neighborly Help 
C. Carlson, K. Chandrasekaran, H. Chang, N. Kakimura, A. Kolla Spectral Aspects of Symmetric Matrix Signings 

H. Mizuta, T. Hatanaka, T. Ito, X. Zhou Reconfiguration of Minimum Steiner Trees via Vertex Exchanges 
S. Kiefer, C. Widdershoven Efficient Analysis of Unambiguous Automata Using Matrix Semigroup Techniques 

M. Bonamy, N. Bousquet, M. Heinrich, T. Ito, Y. Kobayashi, A. Mary, M. Muehlenthaler, K. Wasa The Perfect Matching Reconfiguration Problem 
P. Bell, I. Potapov, P. Semukhin On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond 
12:00  14:00 
Lunch 
14:00  19:00 
Workshops 
