Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (Lecture Notes in Computer Science, 12808)

Preface
Organization
Abstracts of Invited Talks
Adjacency Labelling of Planar Graphs (and Beyond)
Algorithms for Explainable Clustering
Contents
On the Spanning and Routing Ratios of the Directed 6-Graph
	1 Introduction
		1.1 Our Contributions
	2 Preliminaries
		2.1 The Routing Model
	3 Upper Bound on the Spanning Ratio
	4 Routing Algorithm and Upper Bound on Routing Ratio
	5 Conclusions
	References
The Minimum Moving Spanning Tree Problem
	1 Introduction
	2 Preliminaries
		2.1 Definitions
		2.2 Convexity
	3 Minimum Bottleneck Moving Spanning Tree
	4 Minimum Moving Spanning Tree
		4.1 A 2-approximation Algorithm
		4.2 An O(n logn)-time (2+)-approximation Algorithm
		4.3 NP-hardness of MMST
	References
Scheduling with Testing on Multiple Identical Parallel Machines
	1 Introduction
		1.1 Related Work
		1.2 Contribution
		1.3 Preliminary Definitions
	2 Non-preemptive Setting
		2.1 Lower Bound and Greedy Algorithm
		2.2 SBS Algorithm
		2.3 An Improved Algorithm for the Uniform Case
	3 Results with Preemption
	4 Conclusion
	References
Online Makespan Minimization with Budgeted Uncertainty
	1 Introduction
	2 Problem Definition
	3 Graham's Greedy Strategy
		3.1 Upper Bound
		3.2 Lower Bound
	4 An Improved Deterministic Algorithm
		4.1 Deterministic Lower Bounds
	References
Pattern Matching in Doubling Spaces
	1 Introduction
	2 Notation and Preliminary
	3 Reduction from k-Clique
	4 Approximation Algorithm for the -Distortion Problem
	References
Reachability Problems for Transmission Graphs
	1 Introduction
	2 Improved Algorithm for Computing a t-Spanner
		2.1 Theta Graphs and t-Spanners of Transmission Graphs
		2.2 Efficient Algorithm for Computing the t-Spanner
	3 Reachability Oracle for Unbounded Radius Ratio
		3.1 Chain
		3.2 Separation Tree of R
		3.3 Chain Indices
		3.4 Reachability Oracles
	4 Continuous Reachability Oracle
	References
On Minimum Generalized Manhattan Connections
	1 Introduction
		1.1 Our Contributions
		1.2 Overview of Techniques
		1.3 Outlook and Open Problems
	2 Model and Preliminaries
	3 NP-Hardness
	4 An Approximation Algorithm for s-Thin Instances
	5 A Sublogarithmic Approximation Algorithm
	References
HalftimeHash: Modern Hashing Without 64-Bit Multipliers or Finite Fields
	1 Introduction
		1.1 Portability
		1.2 Prior Almost-Universal Families
		1.3 Outline
	2 Notations and Conventions
	3 Prior Work
		3.1 Tree Hash
		3.2 NH
		3.3 Encode, Hash, Combine
	4 Generalized EHC
	5 Implementation
		5.1 EHC
		5.2 Tree Hash
	6 Performance
		6.1 Analysis
		6.2 Cumulative Analysis
		6.3 Benchmarks
	7 Future Work
	References
Generalized Disk Graphs
	1 Introduction
	2 Geometric Representation
	3 Approximation Scheme for Weighted Independent Sets
	4 Structural Properties
	5 One-Dimensional Case
	6 Conclusion and Open Questions
	References
A 4-Approximation of the 23-MST
	1 Introduction
	2 Preliminaries
	3 Replacing an Arbitrary Path by a 23-Tree
		3.1 Phase I
		3.2 Phase II
		3.3 Phase III
		3.4 Correctness
	4 Conclusion
	References
Dynamic Dictionaries for Multisets and Counting Filters with Constant Time Operations
	1 Introduction
		1.1 Results
		1.2 Related Work
		1.3 Paper Organization
	2 Preliminaries
		2.1 The Model
	3 Dictionary for Multisets via Key-Value Dictionaries (Sparse Case)
	4 Dictionary for Multisets (Dense Case)
		4.1 Parametrization
		4.2 Hash Functions
		4.3 The First Level of the Multiset Dictionary
		4.4 The Spare
		4.5 Overflow Analysis
		4.6 Space Analysis
	References
The Neighborhood Polynomial of Chordal Graphs
	1 Introduction
	2 Preliminaries
	3 Algorithm for Chordal Graphs
	4 Complexity of the Anchor Width
	5 Discussion
	References
Incomplete Directed Perfect Phylogeny in Linear Time
	1 Introduction
	2 Preliminaries
		2.1 Preliminary Results
	3 (N,N)-DC in O(N2logN) Total Update Time and O(N) Time per Query
	4 (N,N)-DC in O(N2) Total Update Time and O(N) Time per Query
	References
Euclidean Maximum Matchings in the Plane—Local to Global
	1 Introduction
		1.1 Our Contributions
		1.2 Some Related Works
	2 A Lower Bound for k-Local Maximum Matchings
	3 Better Lower Bound for 3-Local Maximum Matchings
	4 Better Lower Bound for 2-Local Maximum Matchings
	5 Pairwise-Crossing Matchings are Globally Maximum
	6 Discussion
	References
Solving Problems on Generalized Convex Graphs via Mim-Width
	1 Introduction
	2 The Proof of Theorem 1
	3 The Proof of Theorem 2
	4 The Proof of Theorem 3
	5 A Refined Parameter Analysis and Final Remarks
	References
Improved Bounds on the Spanning Ratio of the Theta-5-Graph
	1 Introduction
	2 Preliminaries
	3 Analysis
	4 Proving a Spanning Ratio of 5.70
		4.1 Proof of Lemma 13
		4.2 Proof of Lemma 15
	References
Computing Weighted Subset Transversals in H-Free Graphs
	1 Introduction
	2 Preliminaries
	3 General Framework of the Polynomial Algorithms
	4 Applying Our Framework on (3P1+P2)-Free Graphs
	5 Conclusions
	References
Computing the Fréchet Distance Between Uncertain Curves in One Dimension
	1 Introduction
	2 Preliminaries
	3 Lower Bound Fréchet Distance in One Dimension
	4 Upper Bound Fréchet Distance
	5 Weak Fréchet Distance
		5.1 Algorithm for Continuous Setting
		5.2 Hardness of Discrete Setting
	References
Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
	1 Introduction
	2 Preliminaries
	3 Previous Geometric Observations
	4 New Algorithm
		4.1 Interaction Between Two Standard Lists
		4.2 Interaction Between a Standard List and a Hereditary List
		4.3 Putting Things Together
	References
Planar Drawings with Few Slopes of Halin Graphs and Nested Pseudotrees
	1 Introduction
	2 Preliminaries
	3 Cycle-Trees and Proof of Theorem 1
		3.1 3-Connected Instances
		3.2 2-Connected and 1-Connected Instances
	4 Nested Pseudotrees
	5 Conclusions and Open Problems
	References
An APTAS for Bin Packing with Clique-Graph Conflicts
	1 Introduction
		1.1 Contribution and Techniques
		1.2 Related Work
	2 Preliminaries: Scheduling with Bag Constraints
	3 An APTAS for GBP
		3.1 Rounding of Large and Medium Items
		3.2 Large and Medium Items
		3.3 Small Items
		3.4 Putting It All Together
	References
Fast Deterministic Algorithms for Computing All Eccentricities in (Hyperbolic) Helly Graphs
	1 Introduction
	2 Helly Graphs and Their Hyperbolicity
	3 All Eccentricities in Helly Graphs
	4 Eccentricities in Helly Graphs with Small Hyperbolicity
		4.1 Proof of Lemma 6
	References
ANN for Time Series Under the Fréchet Distance
	1 Introduction
		1.1 Previous Work
		1.2 Known Techniques
		1.3 Preliminaries
		1.4 Our Contributions
		1.5 Signatures
	2 A Constant-Factor Approximation for Time Series
	3 Improving the Approximation Factor to (2+)
	4 An `3́9`42`"̇613A``45`47`"603AO(k)-ANN Data Structure with Near-Linear Space
	5 A Lower Bound in the Cell-Probe Model
	6 Conclusions
	References
Strictly In-Place Algorithms for Permuting and Inverting Permutations
	1 Introduction
	2 Preliminaries
	3 Leader Election in Smaller Space
	4 Inverting Permutations in Smaller Space
	References
A Stronger Lower Bound on Parametric Minimum Spanning Trees
	1 Introduction
	2 Background and Preliminaries
	3 Replacing Edges by Triangles
	4 Weighted 2-Trees
	5 Packing into Dense Graphs
	6 Conclusions
	References
Online Bin Packing of Squares and Cubes
	1 Introduction
	2 Algorithm Extended Harmonic (EH)
	3 Weighting Functions and Results
		3.1 Upper Bounds on the Asymptotic Competitive Ratio
	References
Exploration of k-Edge-Deficient Temporal Graphs
	1 Introduction
	2 Preliminaries
	3 O(kn logn)-Time Exploration of k-Edge-Deficient Temporal Graphs
	4 Linear-Time Exploration of 1-Edge-Deficient Temporal Graphs
	5 Lower Bound
	6 Conclusion
	References
Parameterized Complexity of Categorical Clustering with Size Constraints
	1 Introduction
	2 Preliminaries
	3 FPT  Algorithm for Parameterization by B
	4 Clustering with Size Constraints
	5 Conclusion
	References
Graph Pricing with Limited Supply
	1 Introduction
		1.1 Our Results
		1.2 Related Work
		1.3 Organization
	2 Preliminaries
	3 Local-Search Algorithms
		3.1 Single-Swap Analysis
		3.2 An Improved Multi-swap Algorithm for Bounded Capacities
		3.3 Proof of Theorem 5
	4 LP-Based Approximations
		4.1 Proof Sketch for Theorem 4
	A Reduction to L-Pricing
	References
Fair Correlation Clustering with Global and Local Guarantees
	1 Introduction
		1.1 Our Results
		1.2 Organization
	2 Fair Correlation Clustering
		2.1 6.18-Approximation Algorithm
		2.2 Analysis of 6.18-Approximation Algorithm
		2.3 Towards a 5.5-Approximation Algorithm
	3 Local Fair Correlation Clustering
		3.1 Analysis of Algorithm 2
	References
Better Distance Labeling for Unweighted Planar Graphs
	1 Introduction
	2 Previous Scheme
	3 Improved Scheme
	4 Efficient Decoding
	References
How to Catch Marathon Cheaters: New Approximation Algorithms for Tracking Paths
	1 Introduction
	2 Structural Properties
	3 H-Minor-Free Graphs
	4 General Graphs
	References
Algorithms for Radius-Optimally Augmenting Trees in a Metric Space
	1 Introduction
		1.1 Our Approach
	2 Preliminaries
	3 An O(nlogn) Expected Time Algorithm for the Discrete ROAT problem
		3.1 Case 1: The Center Lies on P
		3.2 Case 2: The Center Does Not Lie on P
	4 A Linear Time Algorithm for Continuous ROAT
		4.1 Simplify the ROAWP Problem
		4.2 Solve ROAMWP in Linear Time
	References
Upper and Lower Bounds for Fully Retroactive Graph Problems
	1 Introduction
	2 Preliminaries
	3 Lower Bounds
	4 Incremental Fully Retroactive Connectivity and SF
	5 Fully Retroactive Data Structures
	References
Characterization of Super-Stable Matchings
	1 Introduction
		1.1 Related Works
	2 Preliminaries
	3 Irreducible Super-Stable Matchings
	4 A Maximal Sequence of Super-Stable Matchings
		4.1 Correctness of Algorithm2
		4.2 Running Time of Algorithm2
		4.3 Rotation Poset
	5 The Super-Stable Matching Polytope
		5.1 Partial Order Preference Lists
		5.2 The Strongly Stable Matching Polytope
	References
Uniform Embeddings for Robinson Similarity Matrices
	1 Introduction
		1.1 Related Works
	2 Uniform Embeddings
	3 Bounds, Walks, and Their Concatenation
	4 A Sufficient and Necessary Condition
		4.1 Cycles and Paths
		4.2 Finding a Uniform Embedding
	5 Testing the Condition
		5.1 A Partial Order on Bounds
		5.2 Generating the Bounds
		5.3 A Combinatorial Algorithm for the Case k=2
	6 Conclusions
	References
Particle-Based Assembly Using Precise Global Control
	1 Introduction
		1.1 Our Contributions
		1.2 Related Work
	2 Preliminaries
	3 NP-Hardness of 3D-STAP
	4 Optimization Variant and Approximation
	5 Efficient Algorithms for Special Classes
		5.1 Tree Shapes
		5.2 Scaled Shapes
	6 Conclusion and Future Work
	References
Independent Sets in Semi-random Hypergraphs
	1 Introduction
		1.1 Our Models and Results
		1.2 Related Work
		1.3 Preliminaries and Notation
		1.4 Proof Overview
	2 Bounding the Contribution from the Random Hypergraph
	3 Algorithm for Computing a Large Independent Set
	References
A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs
	1 Introduction
		1.1 Graph Theory
		1.2 Query Complexity
	2 Result
		2.1 Breadth-First Search Subroutine
		2.2 Depth-First Search Subroutine
	3 Conclusion
	References
Support Optimality and Adaptive Cuckoo Filters
	1 Introduction
		1.1 Results
	2 Three Adaptive Cuckoo Filters
		2.1 ACF Parameters and Internal State
		2.2 Cuckoo Filter Operations
		2.3 Cuckooing ACF
		2.4 Cyclic ACF
		2.5 Swapping ACF
	3 Bounding the False Positive Rate by the Number of Distinct Queries
		3.1 Proof Sketch of Theorem 1
	4 Experiments
		4.1 Experimental Results
	5 Adversarial Adaptivity
		5.1 Definition
		5.2 Lower Bounds
	References
Computing the Union Join and Subset Graph of Acyclic Hypergraphs in Subquadratic Time
	1 Introduction
		1.1 Acyclic Hypergraphs
		1.2 Union Join Graph
		1.3 Subset Graph
		1.4 Our Contribution
	2 Preliminaries
	3 -Acyclic Hypergraphs
		3.1 Hardness Results
		3.2 Union Join Graph via Subset Graph
	4 Subclasses of Acyclic Hypergraphs
		4.1 -Acyclic Hypergraphs
		4.2 -Acyclic Hypergraphs
		4.3 Interval Hypergraphs
	References
Algorithms for the Line-Constrained Disk Coverage and Related Problems
	1 Introduction
		1.1 Related Work
		1.2 Our Approach
	2 Preliminaries
	3 The L and L2 Cases
		3.1 An Algorithmic Scheme for L and L2 Metrics
		3.2 The L Metric
		3.3 The L2 Metric
	References
A Universal Cycle for Strings with Fixed-Content (Which Are Also Known as Multiset Permutations)
	1 Introduction
	2 Preliminaries
		2.1 Necklaces with Fixed-Content
		2.2 Cool-Lex Order
		2.3 Necklace-Prefix Algorithm
	3 Recursive Algorithm
	4 Constructing a Shorthand Universal Cycle for Fixed-Content
		4.1 Efficiency
	References
Routing on Heavy-Path WSPD-Spanners
	1 Introduction
		1.1 Compressed Quadtrees
		1.2 The Well-Separated Pair Decomposition
	2 The Heavy Path WSPD Spanner
		2.1 Constructing a Heavy Path WSPD Spanner
	3 Local Routing in Euclidean Space
		3.1 Routing Tables
		3.2 Routing in a Heavy Path WSPD Spanner
		3.3 Analysis of the Local Routing Algorithm
	4 Conclusions
	References
Mapping Multiple Regions to the Grid with Bounded Hausdorff Distance
	1 Introduction
	2 Input Regions are Points
	3 Input Regions are Convex -fat Regions
	4 Input Regions are Convex Regions
	5 Input Regions are General Regions
		5.1 Two Regions
		5.2 Three or More Regions
	6 Conclusion
	References
Diverse Partitions of Colored Points
	1 Introduction
	2 Related Work
	3 Convex Versus Voronoi Partitions in 1D
	4 Diverse Voronoi Partition in 1D
		4.1 NP-Hardness When Richness is the Diversity Measure
		4.2 NP-Hardness When Shannon Index is the Diversity Measure
		4.3 Polynomial-Time Solution for Discrete Candidate Sites
	5 Approximation for Diverse Voronoi Partition in 1D
	6 Diverse Convex Partition is NP-Hard in 2D
	7 Conclusions
	References
Reverse Shortest Path Problem for Unit-Disk Graphs
	1 Introduction
		1.1 Related Work
		1.2 Our Approach
	2 Preliminaries
	3 The First Algorithm
		3.1 Building the Grid
		3.2 Running BFS
	4 The Second Algorithm
	5 Concluding Remarks
	References
Author Index