文章基本信息

标题：Diverse Pairs of Matchings
本地全文：下载
作者：Fedor V. Fomin ; Petr A. Golovach ; Lars Jaffke 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：181
页码：1-12
DOI：10.4230/LIPIcs.ISAAC.2020.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 ð'ª(kÂ²) vertices.
关键词：Matching; Solution Diversity; Fixed-Parameter Tractability