1 citations · 2 across the 5 of their papers we have counts for
6 papers
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…
On the Exact Matching Problem in Dense Graphs
Nicolas El Maalouly, Sebastian Haslebacher, Lasse Wulf
In the Exact Matching problem, we are given a graph whose edges are colored red or blue and the task is to decide for a given integer k, if there is a perfect matching with exactly…
The Complexity of Recognizing Geometric Hypergraphs
Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist +2
As set systems, hypergraphs are omnipresent and have various representations ranging from Euler and Venn diagrams to contact representations. In a geometric representation of a hyp…
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…