1 citations · 2 across the 5 of their papers we have counts for
4 papers · 1 filter
Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
Nicolas El Maalouly, Kostas Lakis
The Exact Matching (EM) problem asks whether there exists a perfect matching which uses a prescribed number of red edges in a red/blue edge-colored graph. While there exists a rand…
Counting Perfect Matchings in Dense Graphs Is Hard
Nicolas El Maalouly, Yanheng Wang
We show that the problem of counting perfect matchings remains #P-complete even if we restrict the input to very dense graphs, proving the conjecture in [5]. Here "dense graphs" re…
Exact Matching and the Top-k Perfect Matching Problem
Nicolas El Maalouly, Lasse Wulf
The aim of this note is to provide a reduction of the Exact Matching problem to the Top- Perfect Matching Problem. Together with earlier work by El Maalouly, this shows that the…
Exact Matching: Correct Parity and FPT Parameterized by Independence Number
Nicolas {El Maalouly}, Raphael Steiner, Lasse Wulf
Given an integer and a graph where every edge is colored either red or blue, the goal of the exact matching problem is to find a perfect matching with the property that exactly…