LATIN 2022: Theoretical Informatics: 15th Latin American Symposium, Guanajuato, Mexico, November 7–11, 2022, Proceedings (Lecture Notes in Computer Science)

This book constitutes the proceedings of the 15th Latin American Symposium on Theoretical Informatics, LATIN 2022, which took place in Guanajuato, Mexico, in November 2022. The 46 papers presented in this volume were carefully reviewed and selected from 114 submissions. They were organized in topical sections as follows: Algorithms and Data Structures; Approximation Algorithms; Cryptography; Social Choice Theory; Theoretical Machine Learning; Automata Theory and Formal Languages; Combinatorics and Graph Theory; Complexity Theory; Computational Geometry. Chapter “Klee’s Measure Problem Made Oblivious” is available open access under a CC BY 4.0 license. Preface The Imre Simon Test-of-Time Award Organization Contents Algorithms and Data Structures Cutting a Tree with Subgraph Complementation is Hard, Except for Some Small Trees 1 Introduction 2 Preliminaries 3 Reductions for General Graphs 4 Trees 5 Polynomial-Time Algorithm 6 Concluding Remarks References Elastic-Degenerate String Matching with 1 Error 1 Introduction 2 Preliminaries 3 1-Error EDSM 3.1 Easy Case 3.2 Anchor Case 3.3 Prefix Case 3.4 Shaving Logs Using Special Cases of Geometric Problems 3.5 Wrapping-up 4 Open Questions References Median and Hybrid Median K-Dimensional Trees 1 Introduction 2 Median K-d Trees 2.1 Internal Path Length 2.2 Random Partial Match 3 Hybrid Median K-d Trees 3.1 Internal Path Length 3.2 Random Partial Match 4 Conclusions and Final Remarks References Weighted Connected Matchings 1 Introduction 2 Chordal Graphs 2.1 Starlike Graphs 2.2 Chordal Graphs for Non-negative Weights 3 Bipartite Graphs 4 Planar Graphs 4.1 Planar Bipartite Graphs 4.2 Subcubic Planar Graphs 5 Polynomial-Time Algorithms 5.1 Graphs Having Degree at Most 2 5.2 Bounded Treewidth Graphs 6 Kernelization 7 Conclusions and Future Work References Space-Efficient Data Structure for Next/Previous Larger/Smaller Value Queries 1 Introduction 2 Preliminaries 3 Data Structure on Arrays with No Consecutive Equal Elements 4 Data Structure on General Arrays 5 Lower Bounds 6 Conclusion References Near-Optimal Search Time in -Optimal Space 1 Introduction 2 Notation and Basic Concepts 3 A New -Bounded RLSLP 3.1 Restricted Block Compression 3.2 Grammar Size Analysis 4 Local Consistency Properties 5 Indexing with Our Grammar 5.1 Finding the Primary Occurrences 5.2 Parsing the Pattern 5.3 Secondary Occurrences and Short Patterns 6 Conclusions and Future Work References Computing and Listing Avoidable Vertices and Paths 1 Introduction 2 Preliminaries 3 A Lower Bound For Recognizing an Avoidable Vertex 4 Avoidable Vertices in Sparse or Dense Graphs 5 Computing Avoidable Vertices Directly From G 5.1 A Fast Algorithm For Listing Avoidable Vertices 6 Avoidable Vertices via Contractions 7 Recognizing Avoidable Edges and Paths 8 Concluding Remarks References Klee's Measure Problem Made Oblivious 1 Introduction 2 Warm-Up: Shaving Off a loglogn Factor 2.1 Original Algorithm 2.2 High Dimensions 2.3 Oblivious Box Representation 2.4 Simplification in One Sub-domain 2.5 Oblivious Algorithm 3 Improved Processing Using Oblivious Data Structures 3.1 Oblivious Data Structures 3.2 Simplification in m Sub-domains 3.3 Putting Everything Together 4 General Technique 5 Conclusion and Future Work References Approximation Algorithms A Parameterized Approximation Algorithm for the Multiple Allocation k-Hub Center 1 Introduction 2 Preliminaries 2.1 Approximate Addition Trees 2.2 Preprocessing 3 Hardness 4 The Algorithm 5 Analysis 6 Final Remarks References Theoretical Analysis of git bisect 1 Introduction 1.1 Formal Definitions 1.2 Description of git bisect 2 Worst-Case Number of Queries 2.1 The Comb Construction 2.2 A Pathological Example for git bisect 3 Approximation Ratio for Binary DAGs 4 A New Algorithm with a Better Approximation Ratio for Binary DAGs 4.1 Description of golden bisect 4.2 Results for golden bisect on Binary DAGs 5 Conclusion References Pathlength of Outerplanar Graphs 1 Introduction 2 Preliminaries 3 Pathlength of Trees and Cycles 4 Outerplanar Graphs 4.1 Cases When Recursion or Greedy Algorithm are Possible 4.2 Case When x and y Belong to a Same Face 4.3 Polynomial-Time +1 Approximation 5 Further Work References Approximations for the Steiner Multicycle Problem 1 Introduction 2 Metric Steiner Multicycle Problem 2.1 A 3-Approximation Algorithm 2.2 Matchings, T-Joins, and Steiner Forests 3 {1,2}-Steiner Multicycle Problem 3.1 Joining Cycles 3.2 Approximation Ratio 4 Final Remarks References Approximation Schemes for Packing Problems with p-norm Diversity Constraints 1 Introduction 1.1 Our Results 1.2 Related Work 1.3 Organization of the Article 2 Preliminaries 2.1 Algorithmic Approach: Efficient Search of Candidate Solutions 3 Approximation Schemes 3.1 Approximation Scheme with Small Capacity Violation 3.2 Approximation Scheme with Small Norm Violation 3.3 Improved Algorithm for the Case of k=1 4 Packing Problems Under Hill Diversity Constraints References Obtaining Approximately Optimal and Diverse Solutions via Dispersion 1 Introduction 1.1 Our Contributions 1.2 Dispersion 1.3 Reduction to Budget Constrained Optimization 2 Related Work 3 Diversity Computational Problem (DCP) 4 The Reduction: Enter Dispersion and Biobjective Optimization 4.1 Dispersion Problem 4.2 Reduction to Budget Constrained Optimization 4.3 Relaxed BCOs and Self-avoidance 5 Application 1: Diverse Spanning Trees 6 Application 2: Diverse Approximate Shortest Paths 7 Application 3: Diverse Approximate Maximum Matchings, and Global Min-Cut 8 Application 4: Diverse Minimum Weight Matroid Bases and Minimum Spanning Trees References Cryptography On APN Functions Whose Graphs are Maximal Sidon Sets 1 Introduction 2 Preliminaries 3 Characterizations 4 Relation with the Problem of the (Non)existence of Pairs of APN Functions at Distance 1 from Each Others 5 The Case of Plateaued APN Functions 5.1 An Interesting Particular Case 6 Candidate APN Functions for Having Non-optimal Graphs as Sidon Sets References On the Subfield Codes of a Subclass of Optimal Cyclic Codes and Their Covering Structures 1 Introduction 2 Notation, Definitions and Known Results 3 Preliminary Results 4 The Subfield Codes of a Subclass of Optimal Cyclic Codes 5 The Covering Structure of the Subfield Codes 6 Conclusions References Social Choice Theory Multidimensional Manhattan Preferences 1 Introduction 2 Preliminaries 3 Manhattan Preferences: Positive Results 4 Manhattan Preferences: Negative Results 4.1 Technical Results 4.2 The Case with 3 Voters and 6 Alternatives 4.3 The Case with 4 Voters and 5 Alternatives 4.4 The Case with 5 Voters and 4 Alternatives 5 [2] Embeddings 6 Conclusion References Theoretical Machine Learning Exact Learning of Multitrees and Almost-Trees Using Path Queries 1 Introduction 2 Preliminaries 3 Learning Multitrees 4 Parallel Learning of Almost-Trees References Almost Optimal Proper Learning and Testing Polynomials 1 Introduction 1.1 Learning 1.2 Property Testing 2 Techniques 2.1 Upper Bound 2.2 Lower Bound 2.3 Upper Bound for Testing 3 Definitions and Preliminary Results 4 The Learning Algorithm 4.1 The Reduction Algorithms 4.2 The Algorithm for ¶m,d,s 4.3 The Algorithm 5 Lower Bounds References Estimating the Clustering Coefficient Using Sample Complexity Analysis 1 Introduction 1.1 Related Work 1.2 Our Results 2 Preliminaries 2.1 Graphs and Local Clustering Coefficient 2.2 Sample Complexity and VC Dimension 3 Estimation for the Local Clustering Coefficient 3.1 Range Space and VC Dimension Results 3.2 Algorithm 4 Conclusion References Automata Theory and Formal Languages Binary Completely Reachable Automata 1 Introduction 2 Preliminaries 3 A Necessary Condition 4 Rystsov's Graph of a Binary DFA 5 Subgroup Sequences for Standardized DFAs 6 Conclusion References Conelikes and Ranker Comparisons 1 Introduction 2 Preliminaries 2.1 Words and Monoids 2.2 Logic 2.3 Ramsey Numbers 2.4 Hierarchies Inside DA 3 Conelikes and the Covering Problem 4 A Framework for Ranker Comparisons 5 The Ranker Comparison Hierarchy 6 Saturations for Fragments of FO2 References The Net Automaton of a Rational Expression 1 Introduction 2 Definitions and Notation: The Quantitative Perspective 2.1 Weighted Automata 2.2 Weighted Rational Expressions 2.3 The Position Automaton of an Expression 3 The Nailed Expression Tree Automaton 3.1 The Thompson Automaton 3.2 The Nailed Expression Tree Automata 3.3 The Common Properties of the Thompson and the Net Automata 4 From the Expression Syntactic Tree to the Net Automaton 5 An Automaton Interpretation of the Star Normal Form 5.1 The Star Normal Form 5.2 The SNF Automaton 6 Conclusion References Embedding Arbitrary Boolean Circuits into Fungal Automata 1 Introduction 1.1 Boolean Circuits and the CVP 1.2 Challenges 1.3 Overview of the Construction 2 Layer 0: The Fungal Automaton 3 Layer 1: Coarse Graining Space and Time 4 Layer 2: Polarized Components 4.1 Polarized Signals and Wires 4.2 Diodes 4.3 Duplicating, Merging, and Crossing Wires 4.4 Switches 4.5 Delays and Retarders 5 Layer 3: Working with Bits 5.1 Representation of Bits 5.2 Bit Duplication 5.3 Nand Gates 5.4 Cable Crossings 6 Layer 4: Layout of a Whole Circuit 6.1 Arranging the Circuit in Tiles 6.2 Layout for Tile i 6.3 Choosing Suitable Delays for All Gates 6.4 Constructor 7 Summary References How Many Times Do You Need to Go Back to the Future in Unary Temporal Logic? 1 Introduction 2 Preliminaries 3 Future/Past Hierarchies of Unary Temporal Logic 3.1 Definition 3.2 Tools 4 Characterization By Deterministic Hierarchies 4.1 Polynomial Closure 4.2 Deterministic Variants 4.3 Characterization of Future/Past Hierarchies 5 Intermediary Levels 6 Conclusion References String Attractors and Infinite Words 1 Introduction 2 Preliminaries 3 String Attractor Profile Function, Factor Complexity and Recurrence 4 String Attractor Profile Function on Purely Morphic Words 5 New String Attractor-Based Complexities 6 Words with Constant Span Complexity 7 Conclusions References Combinatorics and Graph Theory On the Zero-Sum Ramsey Problem over Z2d 1 Introduction 2 Forests 2.1 Lower Bounds 2.2 Upper Bound 2.3 Stars 3 Cycles 4 Bicliques 5 Further Questions References On -Diperfect Digraphs with Stability Number Two 1 Introduction 2 Related Results 3 Properties of Obstructions 4 New Obstructions 5 Characterization of a Special Class 6 Final Remarks References Percolation and Epidemic Processes in One-Dimensional Small-World Networks 1 Introduction and Related Works 2 Our Contribution 2.1 Tight Thresholds for Bond Percolation 2.2 Applications to Epidemic Processes 2.3 Extensions of Our Results for Epidemic Models 3 Further Related Work 4 Overview of Our Analysis 4.1 Analysis of Bond Percolation in the Model References A Combinatorial Link Between Labelled Graphs and Increasingly Labelled Schröder Trees 1 Introduction 2 The Model and Its Enumeration 3 Iteration Steps and Asymptotic Enumeration 4 Analysis of Typical Parameters 4.1 Quantitative Analysis of the Number of Internal Nodes 4.2 Quantitative Analysis of the Number of Distinct Labels 4.3 Quantitative Analysis of the Height of the Trees 4.4 Quantitative Analysis of the Depth of the Leftmost Leaf 5 Correspondence with Labelled Graphs 6 Uniform Random Sampling References Min Orderings and List Homomorphism Dichotomies for Signed and Unsigned Graphs 1 Introduction 2 Min Orderings of Bipartite Graphs 3 Min Orderings of Weakly Balanced Bipartite Signed Graphs 4 A Polynomial Time Algorithm for the Bipartite Case References On the Zombie Number of Various Graph Classes 1 Introduction 1.1 Contributions 2 Graph Products 2.1 Cartesian Products 2.2 Strong Products 3 Capped Products and Cop-Win Spanning Trees 3.1 General Results on Capped Products 4 Decision Algorithm 4.1 Algorithm 5 Conclusion References Patterns in Ordered (random) Matchings 1 Introduction 2 Unavoidable Sub-matchings 3 Twins 4 Final Remarks References Tree 3-Spanners on Generalized Prisms of Graphs 1 Introduction 2 Preliminaries 3 Tree 3-spanner on Prisms of Graphs 4 Generalized Prisms 5 Concluding Remarks and Future Work References A General Approach to Ammann Bars for Aperiodic Tilings 1 Introduction 2 Settings 2.1 Canonical Cut and Project Tilings 2.2 Local Rules 2.3 Subperiods 3 Cyrenaic Tilings and Ammann Bars 3.1 Good Projections 3.2 Finding Good Projections 3.3 Defining the Prototiles 4 Tiling with the Tileset C References Complexity Theory List Homomorphism: Beyond the Known Boundaries 1 Introduction 2 Preliminaries 3 XP Algorithms: Proofs of Theorems 1 and 2 4 Hardness: Proof of Theorem 3 5 Conclusion References On the Closures of Monotone Algebraic Classes and Variants of the Determinant 1 Introduction 2 Preliminaries 2.1 Border Complexity 2.2 Monotone Complexity 2.3 Monotone Border Complexity 3 Closures of Monotone Algebraic Classes 3.1 Step 1 of Theorem1 3.2 Step 2 of Theorem1 3.3 mVNP and mVF 4 Complexity of Det=kn(X) 4.1 Gadget Construction Hk and Its Properties 4.2 Rosette Construction R(, I) 4.3 Construction of Graph Tm from fn(X) VNP 4.4 Proof of VNP Hardness of Det=kn(X) for k2 References MCSP is Hard for Read-Once Nondeterministic Branching Programs 1 Introduction 1.1 Results and Techniques 1.2 Related Work 1.3 Organization 2 Preliminaries 2.1 Bipartite Permutation Independent Set Problem 3 1-NBP Lower Bound for Bipartite Permutation Independent Set Problem 4 Tight Bound on the Size of 1-NBP for MCSP with Linear Size Parameter 5 Proof of Theorem 1 6 Future Work References Bounds on Oblivious Multiparty Quantum Communication Complexity 1 Introduction 1.1 Background 1.2 Our Contributions 2 Models of Quantum Communication 2.1 Quantum Multiparty Communication Model 2.2 Coordinator Model 2.3 Protocol for Computing a Function 2.4 Symmetric Functions 3 Lower Bounds 4 Applications 5 Matching Upper Bounds 5.1 Optimal Protocol for DISJn, k 5.2 Symmetric Functions 5.3 Optimal Protocol for Equalityn, k References Improved Parallel Algorithms for Generalized Baumslag Groups 1 Introduction 1.1 Notation and Preliminaries 2 Compact Representations 3 Power Circuits 3.1 Operations on Reduced Power Circuits 4 The Word Problem of G1,q 4.1 Conditions for Britton-Reductions in G1,q 4.2 The Algorithm for G1,q 4.3 Conjugacy References Computational Geometry Piercing Pairwise Intersecting Convex Shapes in the Plane 1 Introduction 1.1 Preliminaries 1.2 Our Contributions 1.3 Previous Results 2 General Convex Shapes 2.1 Piercing a Set of Fat Shapes 2.2 Implications 2.3 Piercing Fat Rectangles 3 Refined Results for Specific Shapes 3.1 Homothets of a Convex Shape 3.2 Hexagons 4 Conclusion References Local Routing Algorithms on Euclidean Spanners with Small Diameter 1 Introduction 2 Preliminaries 3 The Hierarchical Construction 4 The k-Hierarchical Graph 5 The TD-Delaunay-Hierarchical Graph 6 Conclusion References On r-Guarding SCOTs – A New Family of Orthogonal Polygons 1 Introduction 1.1 Preliminaries 2 Guarding Simple SCOTs 3 Guarding r-independent SCOTs 3.1 Super-Corridors 3.2 Algorithm for Vertex-Guards 3.3 Algorithm for Point-Guards 4 NP-Completeness with Point-Guards 5 Conclusion References Complexity Results on Untangling Red-Blue Matchings 1 Introduction 2 NP-Hardness 3 Upper Bound on d(n) 4 Upper Bound on D(n) 5 Lower Bounds 5.1 Lower Bound on D(n) 5.2 Lower Bound on d(n) 6 Concluding Remarks References On Vertex Guarding Staircase Polygons 1 Introduction 1.1 Our Results 2 Preliminaries 3 Approximation Algorithm 3.1 Algorithm Correctness 3.2 Approximation Ratio 4 NP-hardness 4.1 Transforming Any X-Monotone Polygon into One that Is X-Monotone and Y-Monotone 4.2 Our Reduction 4.3 Correctness References On the Complexity of Half-Guarding Monotone Polygons 1 Introduction 1.1 Previous Work 1.2 Definitions 1.3 Our Contribution 2 8-Approximation for Point Guarding a Monotone Polygon with Half-Guards 2.1 Sliding Analysis 2.2 Approximation Analysis 3 NP-Hardness for Point Guarding a Monotone Polygon with Half-Guards 3.1 Hardness Details 4 Conclusion and Future Work References Author Index