Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation

We consider a matching problem in which the cost of each edge is a vector with k components. The cost of a matching is the sum of the bottlenecks over all components, and we ask whether there is a perfect matching of cost at most some value Z. This type of matching has applications in heavily synchronized job-shop scheduling problems and in reconfiguration problems, where movement is restricted to a single direction per step. In this paper, we analyze the problem from a parameterized complexity perspective and provide various results including FPT-membership for parameters k and Z combined, as well as W[P]-membership and W[SAT]-hardness for each of the two parameters individually. The reduction also implies para-NP-hardness parameterized by either maximum degree or treewidth. We further show hardness of approximation within a super-logarithmic factor for the optimization variant and provide a $k/d$-approximation algorithm for any constant d ≤ k as well as an efficient approximation scheme parameterized by k. With parameter Z, we show that no FPT-time $F(Z)$-approximation algorithm is possible for any computable function F, unless W[1] = FPT.