论文标题
多对比赛
Diverse Pairs of Matchings
论文作者
论文摘要
我们启动了对图$ g $和整数$ k $的各种（最大/完美）匹配问题的研究，询问$ g $是否具有两个（最大/完美）的匹配，其对称差异至少为$ k $。如果$ k $是输入的一部分，则多种匹配（要求两次不一定是最大或完美的匹配）在一般图表上是NP的完整，我们考虑了两个受限制的变体。首先，我们表明，在两分图上，问题是多项式时间可溶剂，其次，我们证明了各种最大匹配对$ k $的参数化。我们通过表明各种匹配对$ \ Mathcal {o}（k^2）$ Vertices上有一个内核来解决这项工作。
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph $G$ and an integer $k$, ask whether $G$ has two (maximum/perfect) matchings whose symmetric difference is at least $k$. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if $k$ is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by $k$. We round off the work by showing that Diverse Pair of Matchings has a kernel on $\mathcal{O}(k^2)$ vertices.
