Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PERFECT MATCHING:
Reports tagged with Perfect Matching:
TR09-024 | 26th February 2009
Raghav Kulkarni

On the Power of Isolation in Planar Structures

The purpose of this paper is to study the deterministic
{\em isolation} for certain structures in directed and undirected
planar graphs.
The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and
\cite{dkr08} isolate a perfect matching in ... more >>>


TR10-201 | 21st December 2010
Samir Datta, Raghav Kulkarni, Raghunath Tewari

Perfect Matching in Bipartite Planar Graphs is in UL

Revisions: 1

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in ... more >>>


TR11-148 | 3rd November 2011
Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf

Planarizing Gadgets for Perfect Matching do not Exist

To compare the complexity of the perfect matching problem for general graphs with that for planar graphs, one might try to come up with a reduction from the perfect matching problem to the planar perfect matching problem.
The obvious way to construct such a reduction is via a {\em planarizing ... more >>>


TR14-079 | 11th June 2014
Simon Straub, Thomas Thierauf, Fabian Wagner

Counting the Number of Perfect Matchings in $K_5$-free Graphs

Counting the number of perfect matchings in arbitrary graphs is a $\#$P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for $K_{3,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>>


TR20-184 | 10th December 2020
Dmitry Itsykson, Artur Riazanov

Proof complexity of natural formulas via communication arguments

A canonical communication problem ${\rm Search}(\phi)$ is defined for every unsatisfiable CNF $\phi$: an assignment to the variables of $\phi$ is distributed among the communicating parties, they are to find a clause of $\phi$ falsified by this assignment. Lower bounds on the randomized $k$-party communication complexity of ${\rm Search}(\phi)$ in ... more >>>


TR21-021 | 18th February 2021
Per Austrin, Kilian Risse

Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree $\Omega(n/\log n)$ in the Polynomial ... more >>>




ISSN 1433-8092 | Imprint