research
∙
07/05/2023
An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs
In 1982 Papadimitriou and Yannakakis introduced the Exact Matching probl...
share
research
∙
02/27/2023
The Complexity of Recognizing Geometric Hypergraphs
As set systems, hypergraphs are omnipresent and have various representat...
research
∙
10/26/2022
Counting Perfect Matchings in Dense Graphs Is Hard
We show that the problem of counting perfect matchings remains #P-comple...
research
∙
09/17/2022
Exact Matching and the Top-k Perfect Matching Problem
The aim of this note is to provide a reduction of the Exact Matching pro...
research
∙
07/20/2022
Exact Matching: Correct Parity and FPT Parameterized by Independence Number
Given an integer k and a graph where every edge is colored either red or...
research
∙
02/24/2022
Exact Matching in Graphs of Bounded Independence Number
In the Exact Matching Problem (EM), we are given a graph equipped with a...
research
∙
08/09/2021