Paper Info
Title
On the Computational Complexity of Finding Bipartite Graphs with a Small Number of Short Cycles and Large Girth
Abstract
The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for a given set of integers α, β, and γ, and degree sequences π and π', the problem of determining whether there exists a simple bipartite graph with degree sequences (π, π') that has at most α (β and γ) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence π, a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is π and has a girth of at least six.
Year
DOI
Venue
2019
10.1109/ITW44776.2019.8989134
2019 IEEE Information Theory Workshop (ITW)
Keywords
Field
DocType
linear hypergraphs,NP-complete,LDPC codes,3-partition problem,two-step polynomial-time reduction,simple bipartite graph,low-density parity-check codes,computational complexity,polynomial time algorithm,degree sequence
Integer,Small number,Discrete mathematics,Computer science,Low-density parity-check code,Bipartite graph,Constraint graph,Degree (graph theory),Time complexity,Computational complexity theory
Conference
ISSN
ISBN
Citations 
2475-420X
978-1-5386-6901-3
0
PageRank 
References 
Authors
0.34
8
2
Name
Order
Citations
PageRank
Ali Dehghan100.68
Amir H. Banihashemi249054.61