On the Computational Complexity of Finding Bipartite Graphs with a Small Number of Short Cycles and Large Girth 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 lowdensity paritycheck (LDPC) codes. In this paper, we prove that for a given set of integers alpha, beta, and gamma, and degree sequences pi and pixe2x80x99, the problem of determining whether there exists a simple bipartite graph with degree sequences (pi, piu0027) that has at most alpha (beta and gamma) cycles of length four (six and eight, respectively) is NPcomplete. This is proved by a twostep polynomialtime reduction from the 3Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence pi, 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 pi and has a girth of at least six.

Complexity of finding maximum regular induced subgraphs with prescribed degree We study the problem of finding a maximum vertexsubset S of a given graph G such that the subgraph GS induced by S is rregular for a prescribed degree ru003e0. We also consider a variant of the problem which requires GS to be rregular and connected. Both problems are known to be NPhard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NPhard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having treelike structures, as follows. We give lineartime algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs.