Lars Jaffke

Mr. Lars Jaffke


Research Focus & Metrics

Academic Career Length

3Years (2024-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
15 March 2024 in Algorithmica
Verified
Journal Article
Open access
PDF file
FFFedor V. Fomin
Fedor V. Fomin
PGPetr A. Golovach
Petr A. Golovach
LJLars Jaffke
Lars Jaffke
GPGeevarghese Philip
Geevarghese Philip
DSDanil Sagunov
Danil Sagunov
We initiate the study of theDiverse Pair of (Maximum/ Perfect) Matchingsproblems which given a graphGand an integerk, ask whetherGhas two (maximum/perfect) matchings whose symmetric difference is at leastk.Diverse Pair of Matchings(asking for two not necessarily maximum or perfect matchings) is $$\textsf{NP}$$NP -complete on general graphs ifkis 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 thatDiverse Pair of Maximum Matchingsis $$\textsf{FPT}$$FPT parameterized byk. We round off the work by showing thatDiverse Pair of Matchingshas a kernel on $${\mathcal {O}}(k^2)$$O(k2) vertices.