Excluding Single-Crossing Matching Minors in Bipartite Graphs

DOI10.1137/1.9781611977554.CH81MaRDI QIDQ6420941zbMATH OpenOpenAlexFDO

Authors Archontia C. Giannopoulou, Dimitrios M. Thilikos, Sebastian Wiederrecht

Publication date 19 December 2022

Full work available at URL https://doi.org/10.1137/1.9781611977554.ch81

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: oindent By a seminal result of Valiant, computing the permanent of $(0,1)$-matrices is, in general, $$-hard. In 1913 P'olya asked for which $(0,1)$-matrices $A$ it is possible to change some signs such that the permanent of $A$ equals the determinant of the resulting matrix. In 1975, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding $K_{3,3}$ as a {matching minor}. This was turned into a polynomial time algorithm by McCuaig, Robertson, Seymour, and Thomas in 1999. However, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond $K_{3,3}.$ Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the {permanent} of the corresponding $(0,1)$-matrices can be computed efficiently. In this paper we unify the two results above into a single, more general result in the style of the celebrated structure theorem for single-crossing-minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and $K_{3,3}$ which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover, we show that the evaluation of the permanent remains $$-hard on bipartite graphs which exclude $K_{5,5}$ as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes.

This page was built for publication: Excluding Single-Crossing Matching Minors in Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6420941)