Diverse Pairs of Matchings

DOI10.4230/LIPICS.ISAAC.2020.26MaRDI QIDQ6065425zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, Danil Sagunov

Publication date 14 November 2023

Full work available at URL https://arxiv.org/abs/2009.04567

zbMATH Keywords

fixed-parameter tractabilitymatchingsolution diversity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: 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 $mathcalO(k^2)$ vertices.

Cites work

• A Short Proof of the Factor Theorem for Finite Graphs
• Algorithms – ESA 2004
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Beyond the Vizing's bound for at most seven colors
• Color-coding
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Faster scaling algorithms for general graph matching problems
• Handbook of Computational Social Choice
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 1947051 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Kernelization. Theory of parameterized preprocessing
• Matching theory
• Maximum matchings in general graphs through randomization
• On Representatives of Subsets
• Parameterized algorithms
• Paths, Trees, and Flowers
• The NP-Completeness of Edge-Coloring

Cited in

(5)

• Obtaining approximately optimal and diverse solutions via dispersion
• Diverse collections in matroids and graphs
• Computing diverse and nice triangulations
• On the parameterized complexity of diverse SAT
• Finding diverse minimum s-t cuts

This page was built for publication: Diverse Pairs of Matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065425)