CS Paper Radar

Pfaffian Recognition is in $\mathsf{coRP}$

Priyanshu Pant, Ranveer Singh

cs.CC cs.DM ·submitted 2026-10-21 14:41 UTC · v2

Abstract

An orientation of a graph is called Pfaffian if all perfect matchings occur with the same sign in its Pfaffian expansion. A graph is Pfaffian if it admits such an orientation. Given a Pfaffian orientation, the number of perfect matchings can be computed in polynomial time. In 1963, Kasteleyn showed that every planar graph is Pfaffian. In 1989, Vazirani and Yannakakis showed that deciding whether a graph is Pfaffian is polynomial time equivalent to testing whether a given orientation is Pfaffian. For bipartite graphs, polynomial time recognition algorithms were obtained by Robertson, Seymour, and Thomas in 1999, and independently by McCuaig in 2004. Whether a deterministic polynomial time algorithm exists for general graphs remains open. In this paper, we first construct a polynomial that is identically zero if and only if a given orientation is Pfaffian, and show that this polynomial can be evaluated in polynomial time. Combined with the reduction of Vazirani and Yannakakis, this gives a randomized polynomial time algorithm for deciding whether a general graph is Pfaffian, placing the problem in $\mathsf{coRP}$. We also prove that an orientation of a matching covered graph is non-Pfaffian if and only if reversing the edges of some cut makes it strongly connected. Although deciding whether such a cut exists is NP-complete for general digraphs, our characterization yields a randomized polynomial time algorithm for matching covered graphs and deterministic polynomial time algorithms for bipartite and planar matching covered graphs.

Comment
Major revision with a new structural characterization of Pfaffian orientations and its consequences

Closest papers

Nearest neighbours by meaning across the whole index.

Generalized Graph Search Trees

cs.DM cs.DS ·2026-09-08 ·Florian Krowiorz, Robert Scheffler
similarity 0.63
Abstract

Graph search algorithms and their corresponding graph search trees are commonly used in algorithmic graph theory. In recent years, the recognition problem of these graph search trees has received significant attention. So far, the research has focused on two types of search trees: first-in trees that behave like BFS-trees and last-in trees that behave like DFS-trees. The search tree paradigms differ from each other by the parent a vertex is connected to. In first-in trees, it is the first visited neighbor, while in last-in trees it is the last neighbor visited before that vertex. Here, we will generalize these concepts of graph search trees by allowing every preceding neighbor of a vertex to be the parent. We study the complexity of the recognition problem of these generalized graph search trees. We present NP-completeness proofs for most searches. We also show that the problem is trivial for Generic Search and polynomial-time solvable for several searches on bipartite graphs and chordal graphs. We also study the question how fixing the start vertex influences the complexity of the problem.

0.19

A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs

cs.DS cs.CCmath.CO ·2026-10-07 ·Zhiqiang Xu
similarity 0.63
Abstract · 20 pages. We have improved the presentation and clarified some details of the arguments

We give a deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs. For every finite simple bipartite graph of maximum degree at most an integer $Δ\ge3$, the algorithm assigns signs to its edges so that the signed adjacency matrix has operator norm strictly less than $2\sqrt{Δ-1}$. Our algorithm builds on the randomized recursive repair framework of Jadbabaie, Saberi, and Sra~\cite{JSS26}, with deterministic rules for sign selection and vertex deletion.

0.37

An Odd Pfaffian Number

cs.DM math.CO ·2026-09-19 ·Priyanshu Pant, Ranveer Singh
similarity 0.62
Abstract

The Pfaffian number of a graph is the minimum number of Pfaffians needed to obtain its perfect-matching polynomial by linear combination. In 2009, Norine conjectured that every Pfaffian number is a power of four. Miranda and Lucchesi disproved this conjecture in 2011 by constructing a graph of Pfaffian number six, and conjectured instead that every nontrivial Pfaffian number is even. We disprove their conjecture by proving that the Pfaffian number of $K_{3,3}\sqcup K_{3,3}$ is 13. We also construct a connected cubic bipartite matching-covered graph with Pfaffian number 13.

0.18

Degree Realization with Maximum Matching

cs.DM cs.DS ·2026-10-30 ·Amotz Bar-Noy, Igor Kalinichev, David Peleg, Dror Rawitz
similarity 0.62
Abstract

The Maximum Matching Degree Realization problem requires, for a sequence $d$ of $n$ positive integers, to compute a realizing graph(whose degree sequence corresponds to $d$) with the maximum possible matching. We present a polynomial-time algorithm for this problem. The decision version of this problem requires to determine whether a sequence $d$ admits a realization with a matching of size $ν$ (without computing such a realization). Recently, it was shown that it can be done by verifying a series of inequalities. We improve the existing characterization by reducing the number of inequalities.

0.56

Graph Matching in Random Geometric Graphs I: Efficient Algorithms

cs.DS math.PRmath.ST ·2026-10-12 ·Dong Huang, Ankang Jiao, Shuangping Li, Zhangsong Li
hot direction similarity 0.62
Abstract · 62 pages, 4 figures

We study the recovery of the hidden vertex correspondence between two correlated dense random geometric graphs. Each graph is generated from $n$ latent unit vectors in $\mathbb R^d$; the vectors $u_i^A$ and $u_i^B$ of corresponding vertices satisfy $\langle u_i^A,u_i^B\rangle=ρ$, and the vertex labels of the second graph are permuted by an unknown permutation $π$. For every fixed correlation $ρ\in(0,1]$ and every edge density bounded away from zero and one, we give a randomized polynomial time algorithm that recovers $π$ exactly with probability tending to one whenever $d\ge(\log n)^L$, where $L$ depends only on the correlation and the density bounds. The algorithm assigns to each vertex a signature formed by counting decorated paths with a constant number of seeds. The number of such seeded templates grows exponentially with the path length, with an arbitrarily large constant base, so the resulting statistics amplify an arbitrarily small constant correlation. We control the dependencies created by the latent geometry in two ways: when $d$ is larger than $n/(\log n)^{L_0}$ for a suitable constant $L_0$, by comparing local moments with those of correlated Erdős--Rényi graphs; for smaller $d$, by spectral estimation of the latent geometry combined with a harmonic correction. We also provide low-degree evidence for a tradeoff between the correlation and the computational cost.

0.36

Closing the Complexity Gap for Wheeler Graph Recognition on $d$-NFAs

cs.CC cs.FL ·2026-11-08 ·Kengo Hashimoto
theory similarity 0.60
Abstract

Wheeler graph recognition asks whether a directed graph whose arcs are labeled by symbols from a totally ordered alphabet admits a Wheeler order, a total order on its vertices compatible with the labels of arcs and the order of their tails. A $d$-NFA is a nondeterministic finite automaton in which at most $d$ transitions with any given label leave each state. For Wheeler graph recognition on $d$-NFAs, Alanko et al. gave a polynomial-time algorithm for $d \leq 2$, whereas Gibney and Thankachan proved NP-completeness for every fixed $d \geq 5$. The computational complexity for $d = 3$ and $d = 4$ remained open. We resolve both open cases by extending the reduction of Gibney and Thankachan with a new encoding of clauses of Not-All-Equal 3-SAT. Specifically, we prove that recognition is NP-complete even for directed acyclic graphs over an ordered binary alphabet with a unique source reaching every vertex and total out-degree at most three at every vertex. Consequently, Wheeler graph recognition on $d$-NFAs is NP-complete for every fixed $d \geq 3$.

0.22

A Matroid Generalization of Weighted Popular Matching: Characterization and Algorithm

cs.GT cs.DS ·2026-10-13 ·Yuni Iwamasa, Yusuke Kobayashi, Ryoga Mahara, Kenjiro Takazawa
similarity 0.60
Abstract

We study a problem that unifies two major generalizations of popular matchings in the one-sided preference model. In a bipartite graph in which each vertex, or applicant, on one side has preferences over the adjacent vertices, a matching is called popular if it does not lose a head-to-head election against any other matching. Since the seminal work of Abraham, Irving, Kavitha, and Mehlhorn, who gave the first polynomial-time algorithm for finding a popular matching, numerous generalizations of the popular matching problem have been investigated. Two prominent directions are weighted popular matchings, in which each applicant is assigned a voting weight, and popularity problems under matroid constraints. The former admits a polynomial-time algorithm due to Mestre, while the most general form of the latter is the popular common independent set problem, for which a polynomial-time algorithm is given by Kavitha, Makino, Schlotter, and Yokoi. In this paper, we introduce the weighted popular common independent set problem, which simultaneously generalizes weighted popular matchings and popular common independent sets. Our main result is the first polynomial-time algorithm for this problem. A key ingredient of the algorithm is a solution-independent characterization of weighted popular common independent sets, which we establish in this paper. As consequences of our algorithmic result, we obtain polynomial-time algorithms for several previously unresolved problems, including weighted popular matchings with matroid constraints and weighted popular branchings.

0.12

On identifying codes on oriented graphs

cs.DM math.CO ·2026-08-27 ·Soura Sena Das, Sagnik Sen
similarity 0.58
Abstract

This article studies identifying codes in oriented graphs from a computational complexity perspective. We investigate the $\mathcal{F}$-Id Code problem, where given a simple graph $G$ and a vertex subset $C$, which induces a subgraph in the family $\mathcal{F}$, as inputs and ask whether it is possible to orient $G$ in such a way that $C$ becomes its oriented identifying code. Focusing on the family $\mathcal{F}_d$ of $d$-regular graphs, we establish a complete dichotomy by proving that the problem is polynomial-time solvable for $d\leq1$ and NP-complete for all $d\geq2$.

0.14