Fundamentals of Computation Theory: 23rd International Symposium, FCT 2021, Athens, Greece, September 12–15, 2021, Proceedings (Lecture Notes in Computer Science, 12867)

This book constitutes the proceedings of the 23rd International Symposium on Fundamentals of Computation Theory, FCT 2021, held in Athens, Greece, in September 2021. The 30 full papers included in this volume were carefully reviewed and selected from 94 submissions. In addition, the book contains 2 invited talks. The papers cover topics of all aspects of theoretical computer science, in particular algorithms, complexity, formal and logical methods. Preface Organization Plenary Talks Min-Max Optimization: From von Neumann to Deep Learning Plenary Talks Tight Complexity Results for Algorithms Using Tree Decompositions The Complexity of Counting Problems (Tutorial) Contents Invited Papers Two-Sided Matching Markets with Strongly Correlated Preferences 1 Introduction 1.1 Definitions and Main Theorems 1.2 Related Work 2 Strongly Correlated Preferences: Proof of Theorem 1 2.1 Separators and Blocks 2.2 Conditioning on the Man Optimal Stable Matching When Preferences Are Random 2.3 Analyzing the Number x of Men from Other Blocks 2.4 Analyzing the Block Size 2.5 Putting Everything Together 3 Unique Stable Partner: Proof of Theorem 2 References Communicating Finite State Machines and an Extensible Toolchain for Multiparty Session Types 1 Introduction 1.1 Communicating Finite State Machines and Session Types 1.2 Scr: An Extensible Toolchain for Multiparty Session Types 2 Multiparty Session Types (MPST) 3 Scr: An Extensible Implementation of Multiparty Session Types in OCaml 4 Extending Scr 5 Related and Future Work References II Contributed Papers First-Order Logic and Its *Infinitary Quantifier Extensions over *Countable Words 1 Introduction 2 Preliminaries 3 Small Fragments of FO 3.1 FO with Single Variable 3.2 Boolean Closure of Existential 4 First Order Logic with *infinitary quantifiers 4.1 with single variable 4.2 The General logic 5 No Finite Basis Theorems 6 Conclusion References From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization 1 Introduction 1.1 Motivation 1.2 Our Results 1.3 Related Work 2 Preliminaries 3 Generalized Christofides Algorithm 4 Generalized Tree Doubling Algorithm 5 Trading Approximation Quality for Runtime 5.1 Relaxed Generalized Christofides Algorithm 5.2 Relaxed Generalized Tree Doubling Algorithm 6 Experimental Results 6.1 Implementation Details 6.2 Experiments 6.3 Evaluation References A Poly-log Competitive Posted-Price Algorithm for Online Metrical Matching on a Spider 1 Introduction 1.1 Motivation and Problem Statement 1.2 Past Work 1.3 Our Contribution 2 Intuitive Overview on a Simple Instance 3 Notation and Terminology 4 The Spider-Match Algorithm Design 5 Analysis of the Spider-Match Algorithm 6 Conclusion References Computational Complexity of Covering Disconnected Multigraphs 1 Introduction 2 Covers of Connected Graphs 2.1 Covers of Connected Graphs 2.2 A Special Relation Regarding Covers 3 What is a Cover of a Disconnected Graph? 4 Complexity Results 4.1 Locally Bijective Homomorphisms 4.2 Surjective Covers 4.3 Equitable Covers 5 Covering Colored Two-Vertex Graphs 5.1 Covers of Colored Graphs 5.2 Two-Vertex Graphs 6 Conclusion References The Complexity of Bicriteria Tree-Depth 1 Introduction 2 Preliminaries 3 NP-completeness of BTD 4 The Approximation Algorithm References TS-Reconfiguration of Dominating Sets in Circle and Circular-Arc Graphs 1 Introduction 2 Preliminaries 3 A Polynomial Time Algorithm for Circular-Arc Graphs 4 PSPACE-Hardness for Circle Graphs 4.1 The Reduction 4.2 Basic Properties of GF 4.3 Safeness of the Reduction 5 Open Questions A Appendix A.1 Proofs of Section3 A.2 Proofs of Section4 A.3 Detailed Construction of GF References Bipartite 3-Regular Counting Problems with Mixed Signs 1 Introduction 2 Preliminaries 3 Main Theorem References The Satisfiability Problem for a Quantitative Fragment of PCTL 1 Introduction 2 Preliminaries 3 Results 3.1 Progress Measure 3.2 Progressive PCTL Fragments 4 Conclusions References Beyond the BEST Theorem: Fast Assessment of Eulerian Trails 1 Introduction 2 Definitions and Notation 3 Structure and Properties of Directed Eulerian Graphs 4 Assessment Algorithm for #ET(G) 5 Improved Assessment Algorithm 5.1 Introducing Function BranchingSource 5.2 Linear-Time Computation of BranchingSource References Linear-Time Minimal Cograph Editing 1 Introduction 2 Preliminaries 3 Characterisation of Minimal Cograph Editings of G+x 4 An O(n+m)-time Algorithm for Minimal Cograph Editing 4.1 Determining Diff-Above 4.2 Final Stage of the Algorithm and Overall Complexity 5 Conclusion and Perspectives References Regular Model Checking with Regular Relations 1 Introduction 2 Regular Relations for Infinite Strings 2.1 MSO Definable Relations 2.2 Nondeterministic Streaming String Transducers 3 Equivalence of -NMSOT and -NSST 4 MSO-Definable Regular Model Checking 5 Conclusion References Minimum Consistent Subset Problem for Trees 1 Introduction 2 Preliminaries 3 Computing MCS of a Tree Rooted at an Anchor 3.1 Computation of C(Tz) 4 Analysis of Algorithm 5 Conclusion References Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes 1 Introduction 1.1 Our Contributions 1.2 Other Related Work 2 Preliminaries 3 Tractability Results 4 Hardness from Strong Products 4.1 Hardness from Strong Products with Cliques 4.2 Hardness from Joins with Cliques 5 Conclusion References The Space Complexity of Sum Labelling 1 Introduction 2 Definitions and Main Result 3 Labelling a Disjoint Collection of Edges 4 Storing Graphs Using Sum Labelling 5 A Novel Algorithm for Sum Labelling 6 Discussions References On Minimizing Regular Expressions Without Kleene Star 1 Introduction 2 Preliminaries 3 Inapproximability 4 Approximability 5 Minimizing Nondeterministic Finite Automata 6 Conclusion References Computational Complexity of Computing a Quasi-Proper Equilibrium 1 Introduction 1.1 Contributions 1.2 Relation to Previous Work 2 Preliminaries 2.1 Extensive Form Games 2.2 Strategic Form Games 2.3 Complexity Classes 3 Two-Player Games 4 Multi-player Games References Computational Complexity of Synchronization Under Sparse Regular Constraints 1 Introduction 2 Preliminaries and Definitions 3 Sparse and Bounded Regular Languages 4 Letter-Bounded Constraint Languages 5 Constraints from Strongly Self-synchronizing Codes 6 Conclusion and Discussion References On Dasgupta's Hierarchical Clustering Objective and Its Relation to Other Graph Parameters 1 Introduction 2 Preliminaries 3 Four Related Problems 4 VPT-sum and EPT-sum of Trees References Mengerian Temporal Graphs Revisited 1 Introduction 2 Preliminaries 3 Outline of the Proof of Necessity of Theorem 2 4 Outline of the Proof of Sufficiency of Theorem 2 5 Mengerian Graphs Recognition 6 Conclusion References Faster FPT Algorithms for Deletion to Pairs of Graph Classes 1 Introduction 2 Forbidden Characterization for 1 or 2 Deletion 3 1 or 2 Deletion with a Constant Number of Forbidden Pairs 3.1 Interval or Trees 3.2 Algorithm for Special Infinite-(1, 2)-Deletion 4 1 or 2 Deletion When F2 is Infinite and Pi is Forbidden in 1 4.1 Clique or Planar Graphs 4.2 Algorithm for 5 Conclusion References Fast Algorithms for the Rooted Triplet Distance Between Caterpillars 1 Introduction 1.1 Problem Definitions 1.2 Previous Results 1.3 New Results and Organization of Paper 2 Preliminaries 3 The First Algorithm 3.1 Algorithm Description 3.2 Computing 4 The Second Algorithm 4.1 Mapping Leaves to the Grid 4.2 Counting Good Triplets 5 Conclusion References Deciding Top-Down Determinism of Regular Tree Languages 1 Introduction 2 Preliminaries 3 Decidability of Top-Down Determinism 4 Finite Unions of Deterministic Top-Down Tree Languages References Propositional Gossip Protocols 1 Introduction 2 Gossiping Logic 3 Required Communication Graph 4 Minimal Number of Calls 5 Decision Problems for Propositional Protocols 6 Conclusions References Complexity of Word Problems for HNN-Extensions 1 Introduction 2 Groups 2.1 Compressed Words and the Compressed Word Problem 3 The Compressed Power Problem 4 HNN-extensions with Cyclic Associated Subgroups 5 Future Work References On Finding Separators in Temporal Split and Permutation Graphs 1 Introduction 2 Split Graphs 2.1 Hardness Results 2.2 Fixed-Parameter Tractability Results 3 Permutation Graphs 3.1 Hardness Results 3.2 Fixed-Parameter Tractability Results 4 Conclusion References The Possible Winner Problem with Uncertain Weights Revisited 1 Introduction 2 Preliminaries 3 3-Approval 4 Plurality with Runoff 5 Veto with Runoff 6 k-Veto 7 Borda 8 Conclusions and Open Questions References Streaming Deletion Problems Parameterized by Vertex Cover 1 Introduction 2 Adapting Existing Kernels 3 A Direct FPT Approach 3.1 P3-free Deletion 3.2 H-free Deletion 3.3 Towards -free Deletion 3.4 Odd Cycle Transversal 4 Lower Bounds 5 Conclusion References On the Hardness of the Determinant: Sum of Regular Set-Multilinear Circuits 1 Introduction 1.1 Our Results 2 Preliminaries 2.1 Determinant and Permanent 2.2 Erdös-Szekeres Theorem 3 Hardness of the Determinant: Sum of Two Regular Set-Multilinear Circuits 4 Hardness of the Determinant: Sum of Constantly-Many Regular Set-Multilinear Circuits 5 Discussion References Concentration of the Collision Estimator 1 Introduction 1.1 Background 1.2 Main Result 1.3 Related Work 1.4 Organization 2 Preliminaries 2.1 Negative Dependence 2.2 Symmetrization and Decoupling 3 Proofs 3.1 Proof of Theorem 1 4 Conclusion References Valency-Based Consensus Under Message Adversaries Without Limit-Closure 1 Introduction 2 Model and Notations 3 A Generic Consensus Algorithm 4 Computing Delta for the Eventually Stable Message Adversary 5 Conclusions References Author Index Invited papers -- Two sided matching markets with strongly correlated random preferences -- Communicating Finite state machines and an extensible toolchain for multiparty session types -- Contributed papers -- First-Order logic and its Infinitary Quantifier Extensions over Countable Words -- From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization -- A Poly-Log Competitive Posted-Price Algorithm for Online Metrical Matching on a Spider -- Computational Complexity of Covering Disconnected Multigraphs -- The Complexity of Bicriteria Tree-depth -- TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs -- Bipartite 3-Regular Counting Problems with Mixed Signs -- The Satisfiability Problem for a Quantitative Fragment of PCTL -- Beyond the BEST Theorem: Fast Assessment of Eulerian Trails -- Regular Model Checking with Regular Relations -- Minimum Consistent Subset of Trees -- Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes -- The Space Complexity of Sum Labelling -- On Minimizing Regular Expressions Without Kleene Star -- Computational Complexity of Computing a Quasi-Proper Equilibrium -- Computational Complexity of Synchronization under Sparse Regular Constraints -- On Dasgupta's hierarchical clustering objective and its relation to other graph parameter -- Mengerian Temporal Graphs Revisited -- Faster FPT Algorithms for Deletion to Pairs of Graph Classes -- Fast Algorithms for the Rooted Triplet Distance Between Caterpillars -- Deciding Top-Down Determinism of Regular Tree Languages -- Propositional Gossip Protocols -- Complexity of word problems for HNN-extensions -- On Finding Separators in Temporal Split and Permutation Graphs -- The Possible Winner Problem with Uncertain Weights Revisited -- Streaming Deletion Problems Parameterized by Vertex Cover -- On the Hardness of the Determinant: Sum of Regular Set-Multilinear Circuits -- Concentration of Collision Estimator -- Valency-based Consensus under Message Adversaries without Limit-Closure.