WALCOM: Algorithms and Computation : 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023, Proceedings

This book constitutes the proceedings of the 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023, which took place in Hsinchu, Taiwan, in March 2023. The 30 full papers presented together with 2 invited papers were carefully reviewed and selected from 75 submissions. They cover topics such as: computational geometry; string algorithm; optimization; graph algorithm; approximation algorithm; and parameterized complexity. Preface Organization Contents Invited Talks Graph Covers: Where Topology Meets Computer Science, and Simple Means Difficult 1 Definitions 2 Negami's Conjecture 3 Locally Constrained Graph Homomorphisms 4 List Covering 5 Strong Dichotomy 6 Disconnected Graphs 7 Look Who is Stronger, and Mind Generalized Snarks References The Family of Fan-Planar Graphs 1 The Origins 2 The First Generation 3 The Relatives 4 The Second Generation 4.1 Thickness 4.2 Non-simple Fan-Planar Graphs 4.3 Insights on Configuration III 5 An Outlook to the Future References Computational Geometry Minimum Ply Covering of Points with Unit Squares 1 Introduction 2 Minimum Ply Covering with Unit Squares 3 Conclusion References Overlapping Edge Unfoldings for Archimedean Solids and (Anti)prisms 1 Introduction 2 Preliminaries 3 Rotational Unfolding 4 Archimedean Solids 5 Archimedean Prisms 6 Archimedean Anti-prisms References Flipping Plane Spanning Paths 1 Introduction 2 A Sufficient Condition 3 Flip Connectivity for Wheel Sets 4 Flip Connectivity for Generalized Double Circles 5 Conclusion References Away from Each Other 1 Introduction 2 k-Dispersion in a Polygon 3 More Problems 4 Conclusion References Piercing Diametral Disks Induced by Edges of Maximum Spanning Trees 1 Introduction 1.1 Related Works 1.2 Our Contribution 2 Preliminaries 3 Proof of Theorem 1 4 Conclusion References Reflective Guarding a Gallery 1 Introduction 1.1 Our Settings 2 Expanding VP(q) by Exactly k Units of Area 2.1 NP-Hardness for Specular Reflections 2.2 Properties of the Reduction Polygon 2.3 NP-Hardness for Diffuse Reflections 3 Expanding at Least k Units of Area 4 Regular Visibility vs Reflection 5 Conclusion References Improved and Generalized Algorithms for Burning a Planar Point Set 1 Introduction 2 Burning Number in One Dimension 2.1 PTAS for Anywhere Burning 2.2 PTAS for Point Burning 3 Burning Number in Two Dimensions 3.1 Anywhere Burning 3.2 Point Burning 4 Generalizations for Point Burning 4.1 Point Burning with Non-uniform Rates 4.2 k-Burning with Non-uniform Rates 5 NP-Hardness 5.1 Burning Maximum Number of Points 6 Conclusion References On the Longest Flip Sequence to Untangle Segments in the Plane 1 Introduction 1.1 Related Reconfiguration Problems 1.2 Definitions 2 Reductions 3 Near Convex Sets 4 Distinct Flips 5 Conclusion and Open Problems References String Algorithm Inferring Strings from Position Heaps in Linear Time 1 Introduction 2 Preliminaries 2.1 Graphs 2.2 Position Heaps 2.3 Problem Definitions 3 Proposed Algorithms 3.1 Inferring Source Texts from Node-Numbered Edge-Labeled Trees 3.2 Inferring Source Texts from Node-Numbered Trees 3.3 Inferring Source Texts from Edge-Labeled Trees 3.4 Inferring Source Texts from Trees with Links 4 Conclusion References Internal Longest Palindrome Queries in Optimal Time 1 Introduction 2 Preliminaries 2.1 Strings and Palindromes 2.2 Tools 3 Internal Longest Palindrome Queries 3.1 Palindromic Suffixes and Prefixes 3.2 Palindromic Infixes References Finding the Cyclic Covers of a String 1 Introduction 2 Preliminaries 2.1 Basic Definitions 2.2 The IPM Data Structure 3 Cyclic Covers 3.1 Find Regions in X Covered by Cyclic Shifts of W with the Constraint that W[i] Aligns to X[j] 3.2 Finding Regions in X that are Cyclically Covered by a Highly-Periodic Factor W 3.3 Finding Regions in X that Are Cyclically Covered by a Non-highly-periodic Factor W 4 Concluding Remarks References Efficient Non-isomorphic Graph Enumeration Algorithms for Subclasses of Perfect Graphs 1 Introduction 2 Preliminary 3 Algorithms 3.1 Proper Interval Graphs and Cochain Graphs 3.2 Bipartite Permutation Graphs and Chain Graphs 3.3 Threshold Graphs References Optimization Better Hardness Results for the Minimum Spanning Tree Congestion Problem 1 Introduction 2 Preliminaries 3 NP-Completeness Proof of K-STC for K 5 References Energy Efficient Sorting, Selection and Searching 1 Introduction 2 Model 3 Sorting 3.1 Two-Level Algorithm 3.2 Multi-level Algorithm 4 Finding the Minimum Element 5 Conclusion References Reconfiguration of Vertex-Disjoint Shortest Paths on Graphs 1 Introduction 1.1 Our Problems and Related Results 1.2 Our Contribution 2 Preliminaries 3 Reachability Variant 3.1 Characterization of Reachability 3.2 Proof of Theorem 2 4 Shortest Variant 4.1 Polynomial-Time Solvable Cases 4.2 NP-Completeness 5 Conclusion References k-Transmitter Watchman Routes 1 Introduction 2 Notation and Preliminaries 3 Special Observations for k-Transmitters 4 Computational Complexity 5 Approximation Algorithm for k-TrWRP(S,P,s) 6 Conclusion References Graph Algorithm Splitting Plane Graphs to Outerplanarity 1 Introduction 2 Face-Vertex Incidence Graph 3 NP-Completeness 4 Feedback Vertex Set Approach 5 Lower and Upper Bounds 5.1 Upper Bounds 5.2 Lower Bounds 6 Open Problems References Certifying Induced Subgraphs in Large Graphs 1 Introduction 1.1 Previous Work 1.2 Our Results 2 Preliminaries and Notation 3 Certifying Graph Classes in External Memory 3.1 Certifying Split Graphs in External Memory 3.2 Certifying Threshold Graphs in External Memory 3.3 Certifying Trivially Perfect Graphs in External Memory 3.4 Certifying Bipartite Chain Graphs in External Memory 4 Experimental Evaluation 5 Conclusions References Some Algorithmic Results for Eternal Vertex Cover Problem in Graphs 1 Introduction 2 Preliminaries 2.1 Definitions and Notations 2.2 Existing Results Used in This Paper 2.3 Eternal Vertex Cover Number for Some Subclasses of Bipartite Graph 3 A Polynomial Time Algorithm for Chain Graphs 3.1 For Chain Graphs Where only Y Can Have Pendant Vertices 3.2 For Chain Graphs with Pendant Vertices in X or in X,Y both 4 A Linear Time Algorithm for Split Graphs 5 A Polynomial Time Algorithm for Cographs 6 Conclusion and Future Aspects References On the Complexity of Distance-d Independent Set Reconfiguration 1 Introduction 2 Preliminaries 3 Observations 3.1 Graphs and Their Powers 3.2 Graphs with Bounded Diameter Components 4 Chordal Graphs and Split Graphs 5 A Reduction Under TJ on General Graphs 6 Extending Some Known Results for d = 2 6.1 General Graphs 6.2 Perfect Graphs 6.3 Planar Graphs 7 Open Problem: Trees References On Star-Multi-interval Pairwise Compatibility Graphs 1 Introduction 2 Preliminaries 3 Circular Graphs 4 Grid Graphs 5 Conclusions and Open Problems References Parameterized Complexity of Optimizing List Vertex-Coloring Through Reconfiguration 1 Introduction 1.1 Our Problem 1.2 Related Results 1.3 Our Results 2 Preliminaries 2.1 Graph Parameters 3 NP-Hardness 4 PSPACE-Completeness 5 Fixed Parameter Algorithms 5.1 Graphs of Pathwidth One 5.2 Vertex Cover Number 6 Conclusion References Parameterized Complexity of Path Set Packing 1 Introduction 1.1 Related Work 1.2 Our Results 2 Preliminaries 3 Hardness with Respect to Vertex Cover + Maximum Path Length 4 Hardness with Respect to Pathwidth + Maximum Degree + Solution Size 5 FPT Parameterized by Feedback Vertex Number + Maximum Degree 5.1 Preliminaries: Defining Structures and Nice Solutions 5.2 Guessing and Extending the Solution 6 FPT When Combining Three Parameters References Approximation Algorithm Interweaving Real-Time Jobs with Energy Harvesting to Maximize Throughput 1 Introduction 1.1 Motivation 1.2 Our Results 1.3 Prior Work 1.4 Preliminaries 2 An Optimal Algorithm for EAS When All Jobs Have Identical Release Times and Due Dates 3 A Greedy 12-Approximation for EAS 4 An FPTAS for WEAS When All Jobs Have Identical Release Times and Due Dates 5 Hardness Results 5.1 Unweighted Setting 5.2 Weighted Setting 6 Conclusions and Open Problems References Recognizing When a Preference System is Close to Admitting a Master List 1 Introduction 2 Preliminaries 3 Problem Definition and Initial Results 4 Computing the Distance from Admitting a Master List 4.1 Strict Preferences 4.2 Weakly Ordered Preferences 5 Applications 5.1 Optimization over Stable Matchings 5.2 Maximum-Utility Popular Matchings with Instability Costs 6 Summary and Further Research References Groups Burning: Analyzing Spreading Processes in Community-Based Networks 1 Introduction 2 Related Works 3 Burning with Groups: The General Case 3.1 Hardness Results for Burning with Groups 3.2 Approximation Algorithms for Burning with Groups 4 Burning with O(1) Groups 5 Burning Max Groups with Unitary Requirements References Roman k-Domination: Hardness, Approximation and Parameterized Results 1 Introduction 2 Roman k-Domination on Split Graphs 2.1 Roman k-Domination on Split Graphs Is NP-Complete 3 Roman k-Domination on Some Subclasses of Bipartite Graphs 3.1 Roman k-Domination on Star-Convex Bipartite Graphs 3.2 Roman k-Domination on Comb-Convex Bipartite Graphs 3.3 Roman k-Domination on Bipartite Chain Graphs 4 W-Hardness Results for Roman Domination on Split Graphs 5 Approximation Hardness for RKDF References Parameterized Complexity On the Parameterized Complexity of Compact Set Packing 1 Introduction 1.1 Our Results 1.2 Our Contributions and Comparison to Existing Work 1.3 Overview of Techniques 1.4 Open Problems 2 Preliminaries 2.1 Notations 2.2 Problem Definitions 3 Dichotomy of PSP 3.1 Compatible Intersecting Set System Pair 3.2 Hardness of Compact PSP References Structural Parameterization of Cluster Deletion 1 Introduction 2 Preliminaries 3 Algorithmic Results for weighted Cluster Deletion 3.1 Vertex Cover 4 An Application on Twin Cover 5 Cluster Deletion and Neighborhood Diversity References Parity Permutation Pattern Matching 1 Introduction 2 Preliminaries 3 Parameterized Complexity 3.1 Parameterized Hardness for Alternating Permutations 3.2 Parameterized Hardness for 4321-Avoiding Patterns 3.3 Parameterized Algorithm for Fixed Pattern Avoiding Text 4 Classical Complexity 4.1 Hardness 4.2 Polynomial-Time Solvable Cases References Author Index