Cover Image

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gupta, Chetan, Tewari, Raghunath, Sharma, Vimal Raj
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Lossy Catalytic Computation
by: Gupta, Chetan, et al.
Published: (2024)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
by: de Rezende, Susanna F., et al.
Published: (2019)

On Minimum Maximal Distance-k Matchings
by: Kartynnik, Yury, et al.
Published: (2016)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
by: Jain, Rahul, et al.
Published: (2019)

Thin Tree Verification is coNP-Complete
by: Moayyedi, Alice
Published: (2025)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
by: Kiatchaipipat, Nattapol, et al.
Published: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
by: Fritsch, Timo, et al.
Published: (2026)

Fast Simulation of Cellular Automata by Self-Composition
by: Natal, Joseph, et al.
Published: (2024)

A Polynomial Time Algorithm for 3SAT
by: Quigley, Robert
Published: (2024)

Graph Threading with Turn Costs
by: Demaine, Erik D., et al.
Published: (2024)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
by: Kowaluk, Miroslaw, et al.
Published: (2025)

Direct Sums for Parity Decision Trees
by: Besselman, Tyler, et al.
Published: (2024)

Complexity of Firefighting on Graphs
by: Althoetmar, Julius, et al.
Published: (2025)

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
by: Knop, Dušan, et al.
Published: (2017)

The Complexity of Graph Exploration Games
by: Fuchs, Janosch, et al.
Published: (2023)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
by: Krithika, R., et al.
Published: (2023)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
by: Wulf, Lasse
Published: (2025)

A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property
by: Bartlett, Celina Janet
Published: (2025)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
by: Lagerkvist, Victor, et al.
Published: (2025)

The complexity of finding coset-generating polymorphisms and the promise metaproblem
by: Bodirsky, Manuel, et al.
Published: (2026)

Liquid Amortization: Proving Amortized Complexity with LiquidHaskell (Functional Pearl)
by: van Brügge, Jan
Published: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
by: Dvořák, Pavel, et al.
Published: (2017)

Realizing temporal graphs from fastest travel times
by: Klobas, Nina, et al.
Published: (2023)

A Piecewise Approach for the Analysis of Exact Algorithms
by: Clinch, Katie, et al.
Published: (2024)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

Proving Unsatisfiability with Hitting Formulas
by: Filmus, Yuval, et al.
Published: (2023)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
by: Lingas, Andrzej
Published: (2026)

A Decomposition Approach to the Weighted $k$-server Problem
by: Ayyadevara, Nikhil, et al.
Published: (2024)

On Finding Randomly Planted Cliques in Arbitrary Graphs
by: Agrimonti, Francesco, et al.
Published: (2025)

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

Identity Testing for Circuits with Exponentiation Gates
by: Li, Jiatu, et al.
Published: (2025)

On the difficulty of order constrained pattern matching with applications to feature matching based malware detection
by: Liyanage, Adiesha, et al.
Published: (2025)

Towards universally optimal sorting algorithms
by: Sen, Sandeep
Published: (2025)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

Spanning Trees Minimizing Branching Costs
by: Gargano, Luisa, et al.
Published: (2024)

An Algorithm for a Variation of the Shortest Common Superstring Problem
by: Gilfanov, Arthur
Published: (2024)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)