Discrete Mathematics Papers

Positional Identifiability from Pairwise Collision Data Yun-Han Li, Ilan Shomorony, Olgica Milenkovic arxiv.org/abs/2605.23073 [𝚌𝚜.𝙳𝙼]

On weighted partial triangulations of convex polygons Antonio Blanca, Alexandre Stauffer, Izabella Stuhl arxiv.org/abs/2605.21921 [𝚌𝚜.𝙳𝙼 𝚖𝚊𝚝𝚑.𝙲𝙾]

Minimum Sum Set Cover: Structures and Algorithm Zhongyi Zhang, Yixin Cao arxiv.org/abs/2605.21920 [𝚌𝚜.𝙳𝙼 𝚌𝚜.𝙳𝚂]

On the Complexity of Hop Domination and 2-Step Domination in Graph Classes Sandip Das, Sweta Das, Sk Samim Islam arxiv.org/abs/2605.20970 [𝚌𝚜.𝙳𝙼 𝚖𝚊𝚝𝚑.𝙲𝙾]

Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen, Victor Lagerkvist, Magnus Wahlström arxiv.org/abs/2605.19055 [𝚌𝚜.𝙳𝙼 𝚌𝚜.𝙻𝙾 𝚖𝚊𝚝𝚑.𝙲𝙾]

Clique-width and induced topological minors Paweł Rafał Bieliński, Jadwiga Czyżewska, Martin Milanič, Amir Nikabadi, Paweł Rzążewski arxiv.org/abs/2605.15453 [𝚌𝚜.𝙳𝙼 𝚖𝚊𝚝𝚑.𝙲𝙾]

The Gallai Vertex Problem is Θ₂ᵖ-Complete Amir Nikabadi, Eva Rotenberg, Lasse Wulf arxiv.org/abs/2605.13488 [𝚌𝚜.𝙳𝙼]

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds Samuel German arxiv.org/abs/2605.13299 [𝚌𝚜.𝙳𝙼 𝚌𝚜.𝙳𝚂] 💬Accepted to COCOON 2026

Binary constraints on one additional variable can create exponential ascents David A. Cohen, Peter G. Jeavons, Artem Kaznatcheev, Sofia Vazquez Alferez arxiv.org/abs/2605.12425 [𝚌𝚜.𝙳𝙼]

The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction Samuel German arxiv.org/abs/2605.10836 [𝚌𝚜.𝙳𝙼] 💬Accepted to COCOON 2026, proceedings version to appear in Springer LNCS

Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer arxiv.org/abs/2605.07468 [𝚌𝚜.𝙳𝙼 𝚖𝚊𝚝𝚑.𝙲𝙾]

Mutation-Guided Differentiable Quadratic Combinatorial Optimization Yongliang Sun, Ismail Alkhouri, Cheng-Han Huang, Alvaro Velasquez, Susmit Jha, Rongrong Wang arxiv.org/abs/2605.06921 [𝚌𝚜.𝙳𝙼]

Adjacency labelling for proper minor-closed graph classes Vida Dujmović, Gwenaël Joret, Cyril Gavoille, Piotr Micek, Pat Morin, David R. Wood arxiv.org/abs/2605.06616 [𝚌𝚜.𝙳𝙼 𝚖𝚊𝚝𝚑.𝙲𝙾]

Sampling Simultaneous Edge-Colorings Ezra Furtado-Tiwari, Eric Vigoda arxiv.org/abs/2605.05046 [𝚌𝚜.𝙳𝙼 𝚖𝚊𝚝𝚑.𝙿𝚁]

Inferring Phylogenetic Networks from Allowed and Forbidden LCA-Constraints Patricia A. Ebert, Marc Hellmuth arxiv.org/abs/2605.03827 [𝚌𝚜.𝙳𝙼 𝚚-𝚋𝚒𝚘.𝙿𝙴]

An Identity for Catalan Numbers via Restricted Dyck Paths Antonio Bernini, Stefano Bilotta, Elisa Pergola arxiv.org/abs/2605.03567 [𝚌𝚜.𝙳𝙼]

Improving SAT Solvers on Orthogonal Latin Square Problems Aaron Barnoff, Curtis Bright arxiv.org/abs/2605.02132 [𝚌𝚜.𝙳𝙼 𝚖𝚊𝚝𝚑.𝙲𝙾]

Efficient Reconstruction of Arboreal Networks Katharina T. Huber, Katherine St. John arxiv.org/abs/2605.01044 [𝚌𝚜.𝙳𝙼]

Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery Hanno von Bergen, Larissa Fastenau, Enna Gerhard, Nicola Lorenz, Stephanie Maaz, Amer E. Mouawad, Roman Rabinovich, … arxiv.org/abs/2604.27802 [𝚌𝚜.𝙳𝙼 𝚌𝚜.𝙳𝚂 𝚖𝚊𝚝𝚑.𝙲𝙾]

Approximating the Network Design Problem for Potential-Based Flows Max Klimm, Marc E. Pfetsch, Martin Skutella, Lea Strubberg arxiv.org/abs/2604.26882 [𝚌𝚜.𝙳𝙼 𝚖𝚊𝚝𝚑.𝙲𝙾]