Abstract:
In the precedence-constrained perfect matching problem, one needs to incrementally build a matching, whereby the order in which edges join the matching is subject to precedence constraints. Given a graph G = (V, E), a precedence constraint is a pair (X, e) with e being an edge and X a set of vertices, meaning that e may only be added to the matching after covering at least one vertex in X. In this talk, I will introduce C-canonical precedence constraints, where an edge may join a matching if both end-vertices have (shortest path) distance at most C to the current matching. I will talk about the complexity of the problem for different values of C and for different graph classes and present some open questions.