Vol. 12, No. 2, 2021

Download this article
Download this article For screen
For printing
Recent Issues
Volume 12, Issue 2
Volume 12, Issue 1
Volume 11, Issue 2
Volume 11, Issue 1
The Journal
About the Journal
Editorial Board
 
Submission Guidelines
Submission Form
Policies for Authors
Ethics Statement
 
ISSN (electronic): 2693-3004
ISSN (print): 2693-2997
To Appear
 
Other MSP Journals
An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem

Éva Czabarka, László Székely, Zoltán Toroczkai and Shanise Walker

Vol. 12 (2021), No. 2, 115–124
DOI: 10.2140/astat.2021.12.115
Abstract

The graphical realization of a given degree sequence and given partition adjacency matrix simultaneously, is a relevant problem in data driven modeling of networks. Here we formulate common generalizations of this problem and the exact matching problem, and solve them with an algebraic Monte-Carlo algorithm that runs in polynomial time if the number of partition classes is bounded by a constant. We note, that no deterministic polynomial time algorithm is known for any of these problems.

Keywords
perfect matching, exact matching, degree sequence, bipartite graph, Hall's theorem, joint degree matrix, partition adjacency matrix, Monte-Carlo algorithm, computational complexity
Mathematical Subject Classification 2010
Primary: 05D15
Secondary: 05C82, 05D40, 68W20
Milestones
Received: 29 September 2019
Revised: 7 April 2021
Accepted: 7 June 2021
Published: 13 December 2021
Authors
Éva Czabarka
Department of Mathematics
University of South Carolina
Columbia, SC
United States
Visiting Professor
Department of Pure and Applied Mathematics
University of Johannesburg
South Africa
László Székely
Department of Mathematics
University of South Carolina
Columbia, SC
United States
Visiting Professor
Department of Pure and Applied Mathematics
University of Johannesburg
South Africa
Zoltán Toroczkai
Department of Physics, Department of Computer Science and Engineering
University of Notre Dame
IN
United States
Shanise Walker
Department of Mathematics
University of Wisconsin-Eau Claire
WI
United States