Algorithms and Complexity: 13th International Conference, CIAC 2023, Larnaca, Cyprus, June 13–16, 2023, Proceedings

Description

This book constitutes the refereed proceedings of the 13th International Conference on Algorithms and Complexity, CIAC 2023, which took place in Larnaca, Cyprus, during June 13–16, 2023.  The 25 full papers included in this book were carefully reviewed and selected from 49 submissions. They cover all important areas of research on algorithms and complexity such as algorithm design and analysis; sequential, parallel and distributed algorithms; data structures; computational and structural complexity; lower bounds and limitations of algorithms; randomized and approximation algorithms; parameterized algorithms and parameterized complexity classes; smoothed analysis of algorithms; alternatives to the worst-case analysis of algorithms (e.g., algorithms with predictions), on-line computation and competitive analysis, streaming algorithms, quantum algorithms and complexity, algorithms in algebra, geometry, number theory and combinatorics, computational geometry, algorithmic game theory and mechanism design, algorithmic economics (including auctions and contests), computational learning theory, computational biology and bioinformatics, algorithmic issues in communication networks, algorithms for discrete optimization (including convex optimization) and algorithm engineering. Preface Organization Contents Selected Combinatorial Problems Through the Prism of Random Intersection Graphs Models 1 Introduction and Motivation 2 Maximum Cliques in Random Intersection Graphs 3 Maximum Cut and Discrepancy in Random Set Systems References Unifying Gathering Protocols for Swarms of Mobile Robots 1 Introduction 2 Robot Formation Protocols 3 Continuous Time Gathering 3.1 Contracting Protocols 3.2 Results 3.3 An Exemplary Contracting Protocol 4 Discrete Time Gathering 4.1 -Contracting Protocols 4.2 Results 4.3 An Exemplary -Contracting Protocol 5 Outlook References The Complexity of Secure RAMs References The Power of the Binary Value Principle 1 Introduction 2 Preliminaries 2.1 Algebraic Proof Systems 2.2 A Semialgebraic Proof System 3 Circuit and Equational Representations 4 Explicit BIT Definition and Basic Lemmas 5 Polynomial Simulations 6 eBVP Cannot be Used to Prove CNF Lower Bounds 7 Further Research References Independent Set Under a Change Constraint from an Initial Solution 1 Introduction 2 Preliminaries 3 NP-Hardness of BD-MaxIS on Bipartite Graphs 4 Polynomial-Time Solvable Graph Subclasses of BD-MaxIS 4.1 Co-comparability Graphs 4.2 Interval Graphs 4.3 Convex Bipartite Graphs 4.4 Chordal Graphs 5 Concluding Remarks References Asynchronous Fully-Decentralized SGD in the Cluster-Based Model 1 Introduction 2 Preliminaries 2.1 Model of Computation 2.2 Stochastic Gradient Descent 3 Strongly-Convex Cost Functions 4 Non-Convex Cost Functions 5 Cluster-Based MDAA 6 Impossibility of Asynchronous SGD with System Partitions 7 Summary References Non-crossing Shortest Paths Lengths in Planar Graphs in Linear Time 1 Introduction 2 Preliminaries 2.1 Definitions and Notations 2.2 Paths and Non-crossing Paths 2.3 Genealogy Tree 3 Shortcuts 4 Computing Lengths in Linear Time 5 Listing Paths 6 Conclusions References How Vulnerable is an Undirected Planar Graph with Respect to Max Flow 1 Introduction 2 Max Flow in Planar Graphs 2.1 Itai and Shiloach's Approach/decomposition 3 Preliminary Results 3.1 Effects on G* and D of Deleting an Edge or a Vertex of G 3.2 Vitality vs. Distances in D 4 Slicing Graph D Preserving Approximated Distances 5 Computing Edge Vitality 6 Conclusions and Open Problems References Maximum Flows in Parametric Graph Templates 1 Introduction 1.1 Parametric Graph Templates 1.2 Related Work 1.3 Problem Statement 1.4 Our Results 2 Preliminaries 3 Templates of Parallel Loop Programs 3.1 Syntax 3.2 Semantics 3.3 Applications of Flows and Cuts 4 Template Maximum Flows 4.1 Edge-Reweighting 4.2 Source and Sink Belong to the Root Template 4.3 Instance Merging 4.4 Maximum All-s-t Flow 4.5 Partial Instantiation 4.6 Maximum Single-s-t Flow 5 Allowing Edges Between Sibling Templates 6 Conclusion References Dynamic Coloring on Restricted Graph Classes 1 Introduction 2 Preliminaries 3 Chordal Graphs 4 Bipartite Permutation Graphs 5 Biconvex Graphs 6 Hardness Results on Sub-classes of Bipartite Graphs 7 Parameterization by Neighborhood Diversity 8 Parameterizations by Twin-Cover and Clique-Width 9 Conclusion References Enumeration of Minimal Tropical Connected Sets 1 Introduction 2 Preliminaries 3 General Graphs 4 Chordal Graphs 5 Interval Graphs References Dynamic Flows with Time-Dependent Capacities 1 Introduction 2 Preliminaries 3 Computational Complexity 4 The Complexity of Maximum Flows and Minimum Cuts 4.1 Exponentially Complex Flows and Cuts 4.2 Complex Flows and Simple Cuts (and Vice Versa) References On One-Sided Testing Affine Subspaces 1 Introduction 2 Overview of the Testers and the Lower Bounds 2.1 The Algorithm for Functions that Describe Linear Subspace 2.2 Comparison with Goldreich and Ron Algorithm 2.3 The Algorithm for Functions that Describe Affine Subspace 2.4 The Algorithm for Functions that Describe Axis-Parallel Affine Subspace 2.5 Lower Bound for Testing Classes with Fixed/Bounded Dimension 3 Definitions and Preliminary Results 4 Three Testers 5 A Tester for AS 6 Lower Bounds References Stable Scheduling in Transactional Memory 1 Introduction 2 Technical Preliminaries 3 A Lower Bound 4 A Centralized Scheduler 5 A Distributed Scheduler 6 Conclusion References Parameterizing Path Partitions 1 Introduction 2 Definitions 3 NP-Hardness Results 4 W[1]-Hardness Results 5 XP Algorithms 6 Neighborhood Diversity Parameterization 7 Duals and Distance to Triviality 8 Conclusion References Maintaining Triconnected Components Under Node Expansion 1 Introduction 2 Preliminaries 3 Skeleton Decompositions 4 Extended Skeleton Decompositions 5 Node Expansion in Extended Skeleton Decompositions 5.1 Maintaining Planarity and Vertex Rotations 6 Application to Synchronized Planarity References Approximating Power Node-Deletion Problems 1 Introduction 1.1 Known Results on VC, PartVC, BDD, and FVS 1.2 Notation and Definitions 2 Power Node-Deletion and Submodular Set Cover 2.1 Submodular Set Cover Formulation 3 Power (Partial) Vertex Cover 4 Power Bounded Degree Deletion 4.1 Combination of Greedy and Local Ratio 5 Power Feedback Vertex Set References Phase Transition in Count Approximation by Count-Min Sketch with Conservative Updates 1 Introduction 2 Count-Min and Conservative Update 3 Hash Hypergraphs and CU Process 4 Phase Transition of the Relative Error 4.1 Main Results 4.2 Simulations 5 Proofs of the Main Results 5.1 Sketch of Proof of Theorem 2 5.2 Proof of Theorem 3 6 Analysis for Some Non-peelable Hypergraphs 7 Non-uniform Distributions 8 Concluding Remarks References Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane 1 Introduction 2 Preliminaries 3 The Main Algorithm 3.1 Stage I 3.2 Stage II 4 Analysis 5 Extensions References Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond 1 Introduction 1.1 Definition and Motivation 1.2 Related Work 1.3 Our Contributions 2 Preliminaries 2.1 r-Grouped Dominating Set 3 Basic Results 4 Fast Algorithms Parameterized by Vertex Cover Number and by Twin Cover Number 4.1 Algorithms Parameterized by Vertex Cover Number 4.2 Algorithms Parameterized by Twin Cover Number 5 Beyond Vertex Cover and Twin Cover 5.1 Results Based on Algorithmic Meta-theorems and Related Results References Broadcasting in Split Graphs 1 Introduction 2 An Approximation Algorithm for Broadcasting in Split Graphs 2.1 Finding a Proper Star-Matching with Minimum Maxdegree 2.2 Broadcasting from a Vertex in the Clique 2.3 Broadcasting from a Vertex in the Independent Set 2.4 Tightness of Approximation 3 Analysis of an Optimal Broadcast Scheme 3.1 Split Graphs Achieving the Lower Bound of the Broadcast Time 4 Conclusion and Future Work References Partitioning Subclasses of Chordal Graphs with Few Deletions 1 Introduction 2 Preliminaries 3 Sub-exponential FPT Algorithm on Chordal Graphs 4 Polynomial Time Algorithmic Results 4.1 Interval Graphs 4.2 Proper Interval Graphs 4.3 Circular-Arc Graphs 4.4 Permutation Graphs References Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision 1 Introduction 1.1 Symmetric Tensor Decomposition 1.2 Approximate Tensor Decomposition 1.3 Model of Computation 1.4 Our Results 1.5 Related Work and Discussion 1.6 The Algorithm 2 Slices After a Change of Basis 3 Diagonalisation Algorithm for Diagonalisable Matrices 4 Probability Analysis of Condition Numbers and Gap References Improved Deterministic Leader Election in Diameter-Two Networks 1 Introduction 1.1 Our Results 2 Model and Definition 3 Related Work 4 Deterministic Leader Election in Diameter-Two Networks 4.1 Algorithm 4.2 Broadcast Tree Formation 5 Conclusion and Future Work References Fast Cauchy Sum Algorithms for Polynomial Zeros and Matrix Eigenvalues 1 Introduction 1.1 The Classical Problem of Univariate Polynomial Root-Finding 1.2 Black Box Polynomial Root-Finding: The Problem 1.3 Black Box Polynomial Root-Finding: The State of the Art 1.4 Our Results 1.5 Classical Subdivision 1.6 Soft Exclusion/Inclusion Tests 1.7 The Known e/i Tests 1.8 New Progress 1.9 Cauchy-Based e/i Tests: Outline and an Extension 1.10 Organization of the Paper 2 Definitions and Basic Properties 3 The Power Sums of the Roots and Cauchy Sums 3.1 The Power Sums of the Roots and Cauchy Sums in the Unit Disc 3.2 Approximation Errors and Root-Counting in the Unit Disc 3.3 Extension to Any Disc 4 Deterministic -Test Under No Isolation Assumption 5 Randomized Root-Counting and -Tests 5.1 Solution with a Crude Bound on Error Probability 5.2 Refining the Bound on Error Probability 6 Precision of Computing in Our Root-Finders 7 Conclusions References On the Parameterized Complexity of the Structure of Lineal Topologies (Depth-First Spanning Trees) of Finite Graphs: The Number of Leaves 1 Introduction 1.1 Our Results 2 Preliminaries 2.1 Lineal Topology 2.2 Parameterized Complexity 2.3 Problem Definitions 2.4 Logic of Graphs 3 Complexity Analysis 3.1 Hardness Results 3.2 MSO Formulations 3.3 FPT Algorithms for Dual Min-LLT and Dual Max-LLT 4 Conclusion References Efficiently Enumerating All Spanning Trees of a Plane 3-Tree 1 Introduction 2 Preliminaries 3 On Spanning Trees of a Plane 3-Tree 4 Inductive Algorithm for Spanning Tree Enumeration 5 DP Algorithm for Spanning Tree Enumeration 6 Conclusions References Communication-Efficient Distributed Graph Clustering and Sparsification Under Duplication Models 1 Introduction 2 Definitions and Notations 3 Distributed Graph Clustering 4 Spanner Constructions in the Blackboard Model 5 Conclusions and Future Work References Author Index