Graphs and Combinatorial Optimization: from Theory to Applications: CTW 2023, Garmisch-Partenkirchen, Germany, June 20–22 (AIRO Springer Series, 13)

This book contains the proceedings of the 19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, held during June 20-22, 2023, in Garmisch-Partenkirchen, Germany. This successful series of international workshops is known to attract high-quality research on the theory and application of discrete algorithms, graphs, and combinatorial optimization in a wide sense. The papers collected in this book represent cutting-edge research by leading researchers and attract a broad readership in academia worldwide. The book is addressed to researchers and advanced students, but also to professionals in industry concerned with algorithm design and optimization problems in different areas of application. CTW 2023 Program Committee Preface Contents The Algorithmic Complexity of the Paired Matching Problem 1 Introduction 2 Classical Complexity 3 Solving Large Instances with Few Task Vertices 4 Conclusion and Discussion References Edge Contraction and Forbidden Induced Subgraphs 1 Introduction 1.1 The H-Split Graphs 1.2 Critically H-Exist Graphs 2 Special Graph Classes 2.1 The 2 upper K 22K2-Free Graphs 2.2 The upper C 4C4-Free Graphs 2.3 The upper C 5C5-Free Graphs 2.4 Split Graphs References Exact Approaches for the Connected Vertex Cover Problem 1 Introduction 1.1 Preliminaries 2 Mixed-Integer Programming Formulations 2.1 A Smaller Mixed-Integer Formulation 3 A Branch & Bound Algorithm 4 Numerical Results 5 Conclusion References Rigidity of Frameworks on Spheres 1 Introduction 2 Rigidity on Non-concentric Spheres 3 Rigidity of Nearly Monochrome Graphs 4 Concluding remarks References Managing Time Expanded Networks: The Strong Lift Problem 1 Introduction 2 A Reference TEN Relocation Model 2.1 A TEN Relocation Commodity Flow Model 2.2 The Projected IRP Model 3 The Strong Lift Issue 3.1 The Strong Lift Model 3.2 A Necessary Condition for the Feasibility of the Strong Lift Problem: Enhancing the PIRP Model 4 A MILP Formulation of the Strong Lift Problem 4.1 Solving the Strong Lift Problem in an Exact Way 4.2 Numerical Experiments References kk-Slow Burning: Complexity and Upper Bounds 1 Introduction 2 Complexity 2.1 Connecting the Paths 2.2 kk-Slow Burning is Harder Than Graph Burning 2.3 Checking Burning Sequences 3 Upper Bounds 4 Concluding Remarks References Discrepancies of Subtrees 1 Introduction 2 Multicolour Discrepancy 3 Oriented Discrepancy 4 High Dimensional Discrepancy References Handling Sub-symmetry in Integer Programming using Activation Handlers 1 Introduction 2 Sub-symmetry in Integer Programming 3 Activation Handler 4 Application 4.1 Multiple Knapsack Problem 4.2 Unit Commitment Problem 5 Experimental Results 6 Conclusion References A Multivariate Complexity Analysis of the Generalized Noah's Ark Problem 1 Introduction 2 Preliminaries 2.1 Problem Definitions, Parameters, and Results Overview 2.2 Observations for GNAP 3 Multiple-Choice Knapsack 4 The Generalized Noah's Ark Problem 5 Restriction to Two Projects per Taxon 6 Discussion References Comparing Ad-Hoc and MIP-Based Algorithms for the Online Facility Location Problem 1 Introduction 2 Problem Statement and Background 3 Ad-Hoc OFLP Algorithms 4 MIP-Based Algorithms for BOFLP 4.1 Follow The Uniformly Perturbed Leader 4.2 Follow The Clustered Leader 5 Experimental Setting and Results 5.1 Experimental Test Bed 5.2 Evaluation of the Algorithms 6 Conclusions References Data-Driven Feasibility for the Resource Constrained Shortest Path Problem 1 Introduction 2 Problem Definition 3 Feature Engineering 4 Computational Experiments 5 Conclusions References Monte-Carlo Integration on a Union of Polytopes 1 Introduction 2 Preliminaries 3 Monte-Carlo Integration on a Union of Polytopes 3.1 Extending Markov Chain Monte Carlo 3.2 Extending Multiphase Monte Carlo 4 Evaluation 5 Conclusion References Achieving Long-Term Fairness in Submodular Maximization Through Randomization 1 Introduction 2 Preliminaries and Problem Statement 3 Near Feasible Deterministic Algorithms 3.1 Algorithm Design 3.2 Performance Analysis 3.3 A Fast Greedy Algorithm 4 A Feasible left parenthesis 1 minus 1 divided by e right parenthesis(1-1/e)-Approximation Randomized Algorithm References On Syntactical Graphs-of-Words 1 Introduction 1.1 Ranking Functions for Text 1.2 Graph-of-Words 1.3 Syntax Trees 2 Graph-of-Words Construction Algorithms 2.1 Proximity Gows 2.2 Dependency 2.3 Constituency 3 Computational Experiments 3.1 The Literary Dataset 3.2 The Technical Dataset 4 Conclusion References On the Optimality Gap of Full Airport Slot Assignments: Capacity-Limited Packing with Pareto Optimality Constraints 1 Introduction 2 Notation, Preliminaries, and Main Results 3 Computational Complexity 4 Gap Potential at the German Level 3 Airports 5 Final Remarks References Author Index