42 citations · 204 across the 38 of their papers we have counts for
4 papers · 1 filter
The Exact Bipartite Matching Polytope Has Exponential Extension Complexity
Xinrui Jia, Ola Svensson, Weiqiang Yuan
Given a graph with edges colored red or blue and an integer , the exact perfect matching problem asks if there exists a perfect matching with exactly red edges. There exists…
The Matching Problem in General Graphs is in Quasi-NC
Ola Svensson, Jakub Tarnawski
We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in time on $n^{O(\log^2 n)}…
No Small Linear Program Approximates Vertex Cover within a Factor
Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta +1
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev (2003) proved that the problem is NP-hard to appro…
Hardness of Vertex Deletion and Project Scheduling
Ola Svensson
Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer and arbitrary…