Small edge sets block nested matchings in ordered graphs
Minimum blockers for nonnested perfect matchings
Discrete Mathematics
Summary
The paper studies a way to block special pairings called nonnested perfect matchings in a set of ordered points connected by edges. It finds the smallest number of edges needed to block all such matchings and groups these blockers into three clear families. The authors also present an efficient algorithm to find these blockers or a matching that avoids them. Beyond perfect matchings, they construct graphs that avoid certain types of matchings altogether under specific conditions.
What this means in practice
- •For network engineers: Identify minimal edge sets that disrupt certain ordered pairings to design resilient network topologies or fault-tolerance measures.
- •For software developers in combinatorial optimization: Use the deterministic algorithm to efficiently test or generate minimal blockers for structured matching problems in ordered data.
A theory result. No direct application yet.
Authors
Pedro M. M. de Castro
Abstract
A perfect matching in an ordered graph is nonnested if no edge lies strictly inside another. We classify the smallest edge sets meeting every nonnested perfect matching on $2k$ ordered vertices. For $k\ge2$, these blockers have $k$ edges and belong to three explicit families, with $2^k+k-2$ members in total. The proof uses a minimum spanning tree of an auxiliary interval cut; its equality case also classifies the minimum blockers for concatenations of crossing matchings. The argument gives a deterministic algorithm that, from at most $k$ deleted edges, returns a minimum blocker description or an avoiding nonnested perfect matching in $O(k^2)$ word operations and $O(k)$ auxiliary words. We also give an injection from one of the blocker families into minimum blockers of $123$-avoiding permutation matrices. Beyond the perfect case, an explicit construction gives graphs with $(k-1)n+1$ edges and no nonnested $k$-matching for every $k\ge5$ and $n\ge2k+1$.