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

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