Computing and Combinatorics

This two-volume set, LNCS 15983 and 15984, constitutes the referred proceedings of the 31st International Computing and Combinatorics Conference, COCOON 2025, held in Chengdu, China, during August 15-17, 2025.

The 54 full papers were carefully reviewed and selected from 191 submissions. COCOON 2025 provided an excellent venue for researchers working in the topical sections as follows:
Part I: Approximation Algorithms, Combinatorial Optimization, Computational Complexity, Computational Geometry, Economics and Computation.
Part II: Graph Algorithms and Graph Theory, Learning and Data-Related Theory, Parameterized Algorithms, String Algorithms and Discrete Structures.

. - Graph Algorithms and Graph Theory.
. - On the Complexity of 2-Club Cluster Editing with Vertex Splitting.
. - A sufficient condition for the existence of two completely independent spanning trees.
. - Undecidability of polynomial inequalities in subset densities and additive energies.
. - Approximation algorithm for prize-collecting hypergraph vertex cover with fairness constraints.
. - Sum-of-Max Chain Partition of a Tree.
. - Reconfiguring Multiple Connected Components with Size Multiset Constraints.
. - Fault diagnosability evaluation of BCCC data center networks.
. - Testing Some First-Order Logic Properties on Sparse Graphs.
. - Massively Parallel Approximate Steiner Tree Algorithms.
. - A Multi-start Variable Neighborhood Tabu Search Algorithm for the Cyclic Bandwidth Problem.
. - Vertex-Critical (P5, W4)-Free Graphs.
. - Learning and Data-Related Theory.
. - A Dynamic Working Set Method for Compressed Sensing.
. - Data Debugging is NP-hard for Classifiers Trained with SGD.
. - Coresets for k-Median of Lines with Group Fairness Constraints.
. - Redefining Entity Integration: Theoretical Insights for GNN-based Recommender Systems.
. - Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits.
. - A Robust Distributed Minimax Learning Method against Model Poisoning Attacks.
. - Parameterized Algorithms.
. - Parameterized Complexity of Influence Maximization.
. - Improved Parameterized Algorithms for Scheduling with Precedence Constraints and Time Windows.
. - Pareto Optimal Matching with Multilayer Preferences: How Hard Can It Be? .
. - An FPT Factor-11 Approximation Algorithm for TSP.
. - From Metric to General Graphs: FPT Constant-Factor Approximation Algorithms for Three Location Problems.
. - String Algorithms and Discrete Structures.
. - Revisit the Partial Coloring Method: Prefix Spencer and Sampling.
. - A Sparse Dynamic Programming Algorithm for Solving the Coding Sequence Design Problem.
. - Improved Approximation Algorithm and Hardness Result for Sorting Unsigned Strings by Symmetric Reversals.
. - Longest Double-Bounded (k]-tuple Common Substrings.
. - Finding cycle types in permutation groups with few generators.
. - Counting overlapping pairs of words.