SOFSEM 2023: Theory and Practice of Computer Science : 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15–18, 2023, Proceedings

This book constitutes the conference proceedings of the 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, held in Nový Smokovec, Slovakia, during January 15–18, 2023. The 22 full papers presented together with 2 best papers and 2 best students papers in this book were carefully reviewed and selected from 43 submissions. This workshop focuses on graphs problems and optimization; graph drawing and visualization; NP-hardness and fixed parameter tractability; communication and temporal graphs; complexity and learning; and robots and strings. Preface Organization Contents Graphs Problems and Optimisation The Complexity of Finding Tangles 1 Introduction 2 Exact Algorithms 3 Complexity 4 Counterexample to Conjecture 1 References A Spectral Algorithm for Finding Maximum Cliques in Dense Random Intersection Graphs 1 Introduction 1.1 Previous Work on Maximum Cliques in Random Intersection Graphs 2 Our Contribution 3 Definitions, Notation and Useful Results 3.1 Range of Values for m,n,p 4 The Spectral Algorithm 4.1 Running Time of Our Algorithm 5 Experimental Evaluation 6 Conclusions 7 Appendix 7.1 Greedy-Clique Algorithm 7.2 Mono-Clique Algorithm 7.3 Maximum-Clique Algorithm References Solving Cut-Problems in Quadratic Time for Graphs with Bounded Treewidth 1 Introduction 2 Related Work 3 Preliminaries 4 Max-Bisection: From O(2t n3) to O(2tn2) 5 Our Framework 6 Conclusion References More Effort Towards Multiagent Knapsack 1 Introduction 2 Hardness of Median-UK 3 Algorithms for Special Cases 3.1 When = 1: Diverse Knapsack 4 Conclusion References Graph Drawing and Visualization Dominance Drawings for DAGs with Bounded Modular Width 1 Introduction 2 Preliminaries 3 The Compaction Lemma 4 Minimizing the Number of Fips 5 Minimizing the Number of Dimensions 6 Concluding Remarks References Morphing Planar Graph Drawings Through 3D 1 Introduction 2 An Upper Bound 2.1 3D Morph Operations 2.2 3D Morphs for Biconnected Planar Graphs 2.3 3D Morphs for General Planar Graphs 3 Discussion: Lower Bounds 4 Open Problems References Visualizing Multispecies Coalescent Trees: Drawing Gene Trees Inside Species Trees 1 Introduction 2 Drawing Style 3 NP-Hardness 4 Planar Instances 5 Algorithms References Parameterized Approaches to Orthogonal Compaction 1 Introduction 2 Basic Definitions 3 Number of Kitty Corners: An FPT Algorithm 4 A Polynomial Kernel for Cycle Graphs 5 Maximum Face Degree: Parameterized Hardness 6 Height of the Representation: An XP Algorithm 7 Open Problems References NP-Hardness and Fixed Parameter Tractability Hardness of Bounding Influence via Graph Modification 1 Introduction 2 Related Work 3 Preliminaries 3.1 Graph Theoretic Terminology 3.2 Centrality Measures 4 Bounding the Influence of Vertex Centrality Scores References Heuristics for Opinion Diffusion via Local Elections 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Formal Model 2.1 Opinion Graphs 2.2 Campaigning and Bribery 2.3 Diffusion Processes via Local Elections 2.4 Election Results via Global Voting Rules 2.5 Optimization Goals 3 Computing Optimal Bribery Schemes 3.1 Heuristic Methods 4 Simulations 4.1 Experimental Design 4.2 Results 5 Outlook References On the Parameterized Complexity of s-club Cluster Deletion Problems 1 Introduction 2 Preliminaries 3 Algorithm for s-Club Cluster Edge Deletion 3.1 Definition of the Records 3.2 Description of the Algorithm 4 Algorithm for s-Club Cluster Vertex Deletion 5 Discussion and Open Problems References SOFSEM 2023 Best Papers Balanced Substructures in Bicolored Graphs 1 Introduction 2 NP-hardness Results 2.1 Complexity in Split Graphs 3 Small Balanced Paths, Trees and Connected Subgraphs 4 FPT Algorithms 4.1 Randomized Algorithms 4.2 Deterministic Algorithms 5 Concluding Remarks References On the Complexity of Scheduling Problems with a Fixed Number of Parallel Identical Machines 1 Introduction 2 Preliminaries 2.1 Subset Sum and Partition 2.2 Scheduling 2.3 The Scheduling Lower Bounds by Abboud et al. 2.4 Our Results 3 Problems with One Machine 4 Problems with Multiple Machines 5 Conclusion References SOFSEM 2023 Best Student Papers On the 2-Layer Window Width Minimization Problem 1 Introduction 2 Window Width Minimization with Bottom Layer Fixed 3 Window Width Minimization with Top Layer Fixed 4 Open Problems References Sequentially Swapping Tokens: Further on Graph Classes 1 Introduction 2 Preliminaries 3 Polynomial-Time Algorithm for Block-Cactus Graphs 3.1 Reduction to a Generalized Problem on Biconnected Components 3.2 Sub-STS on cycles 3.3 Sub-STS on complete graphs 3.4 The Whole Algorithm 4 Hardness of the Few-Color and Colorful Cases 4.1 General Tools for Showing Hardness 4.2 The Few-Color Case on Grid-Like Graphs 4.3 The Colorful Case on Grid-Like Graphs 5 Concluding Remarks References Communication and Temporal Graphs On the Preservation of Properties When Changing Communication Models 1 Introduction 2 The FIFO System 3 Comparing Channel Layouts 4 Property Preservation 4.1 Reachability 4.2 Deadlock Freedom 4.3 Confluence 4.4 Summary of Results 5 Conclusion References Introduction to Routing Problems with Mandatory Transitions 1 Introduction 2 Shortest Path Problems with Mandatory Transitions 2.1 Polynomiality of SPMT 2.2 Non Approximation of Elementary SPMTand MRMT 3 Routing Problems with Mandatory Transitions 4 Conclusion References Payment Scheduling in the Interval Debt Model 1 Introduction 2 The Interval Debt Model 2.1 Formal Setting 2.2 Schedules 2.3 Problem Definitions 3 Our Results 3.1 Hardness Results 3.2 Polynomial-Time Algorithms 4 Conclusion and Open Problems References Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs 1 Introduction 2 Preliminaries 3 Temporal Extension of Graph Problems 4 Periodic Character Alignment 5 Minors and Subgraphs 5.1 Subgraphs 5.2 Minors 5.3 Further Parameterized Analysis 6 Short Traversal 7 Conclusion References Complexity and Learning Lower Bounds for Monotone q-Multilinear Boolean Circuits 1 Introduction 2 Monotone Boolean Circuits and Functions 3 Monotone q-multilinear Boolean Circuits 3.1 q-multilinearity Versus Bounded Conjunction Depth 4 Lower Bounds for q-multilinear Boolean Circuits 4.1 Lower Bound Trade-Offs for Semi-disjoint Bilinear Forms 4.2 Lower Bounds for Isolk,n References A Faster Algorithm for Determining the Linear Feasibility of Systems of BTVPI Constraints 1 Introduction 2 Statement of Problems 3 A Rewrite Version of Fourier-Motzkin Elimination 4 The BCS Linear Programming Algorithm 4.1 Analysis 5 Conclusion References Quantum Complexity for Vector Domination Problem 1 Introduction 1.1 Prior Work 1.2 Our Results 2 Preliminaries 2.1 Problem Definitions 2.2 Quantum Query Model 2.3 Techniques 3 Vector Domination 3.1 Lower Bounds 3.2 Upper Bounds 4 Minimum Inner Product 4.1 Idea 4.2 Preprocessing 4.3 Reduction 5 Open Questions References Learning Through Imitation by Using Formal Verification 1 Introduction 2 Related Work 3 Method 3.1 Q-Learning 3.2 Using a Model Checker on the Q-learning Model 4 Model Checker as an Expert—Applications 4.1 Convergence with Fewer Epochs 4.2 Help Convergence by Avoiding Sub-optimal Solutions 4.3 Explore Unseen States 5 Discussion References Robots and Strings Delivery to Safety with Two Cooperating Robots 1 Introduction 1.1 Model, Notation, and Preliminaries 1.2 Related Work 1.3 Outline and Results of the Paper 2 Optimal Offline Algorithm 3 Online Algorithm for the OneAxis Model 4 Online Algorithms for the NoAxis Model 4.1 VisibleBoundary Model 4.2 DiscoverableBoundary Model 4.3 InvisibleBoundary Model 5 Conclusion References Space-Efficient STR-IC-LCS Computation 1 Introduction 2 Preliminaries 2.1 Strings 2.2 STR-IC-LCS 3 Space-efficient Solution for STR-IC-LCS Problem 3.1 Overview of Our Solution 3.2 Space-efficient Prefix LCS 3.3 Algorithm 4 Conclusions and Future Work References The k-Centre Problem for Classes of Cyclic Words 1 Introduction 2 Preliminaries 3 The k-centre Problem for Necklaces 3.1 The Overlap Distance and the k-centre Problem 3.2 The k-centre Problem 4 Approximating the k-centre Problem for necklaces References Author Index This book constitutes the conference proceedings of the 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, held in Novy Smokovec, Slovakia, during January 1518, 2023. The 22 full papers presented together with 2 best papers and 2 best students papers in this book were carefully reviewed and selected from 43 submissions. This workshop focuses on graphs problems and optimization; graph drawing and visualization; NP-hardness and fixed parameter tractability; communication and temporal graphs; complexity and learning; and robots and strings. This book constitutes the conference proceedings of the 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, held in Novì Smokovec, Slovakia, during January 15-18, 2023.The 22 full papers presented together with 2 best papers and 2 best students papers in this book were carefully reviewed and selected from 43 submissions.This workshop focuses on graphs problems and optimization; graph drawing and visualization; NP-hardness and fixed parameter tractability; communication and temporal graphs; complexity and learning; and robots and strings