Weak Modular Product of Bipartite Graphs, Bicliques and Isomorphism

Danial Dervovic, Simone Severini

TL;DR

This paper explores a novel approach to graph isomorphism for bipartite graphs by leveraging the "weak modular product" and the concept of bicliques. The authors introduce an algorithm, Isomorphism via Biclique Enumeration (IvBE), which offers polynomial-time solutions for specific classes of bipartite graphs and quasi-polynomial time for others, providing a new combinatorial perspective on a fundamental computational problem.

What Problem Does This Paper Address?

The core problem this paper tackles is graph isomorphism (GI), specifically for bipartite graphs. Graph isomorphism asks whether two graphs are structurally identical, meaning there's a way to relabel the vertices of one graph to perfectly match the other. While GI is known to be in NP, its exact complexity class remains an open question. For general graphs, checking isomorphism is computationally challenging. This paper focuses on bipartite graphs, a significant subclass where GI is still NP-complete. The authors build upon Kozen's 1978 theorem, which connects graph isomorphism to the existence of a clique of a specific size in the "weak modular product" of two graphs. They aim to make this connection more computationally tractable for bipartite graphs by focusing on bicliques (complete bipartite subgraphs) within this product.

Methods

The paper introduces several key methodological contributions:

  • Weak Modular Product (WMP): The authors utilize the WMP, a graph product that incorporates information about both adjacency and non-adjacency of the factor graphs.
  • Isomorphism via Biclique Enumeration (IvBE): This is the central algorithmic contribution. IvBE leverages Kozen's theorem by searching for specific types of bicliques (those of size $n$ in the WMP of two $n$-vertex graphs) to determine isomorphism.
  • Very Weak Modular Product (VWMP): A new graph product is defined specifically for balanced bipartite graphs. This product is used to analyze conditions under which the WMP is "perfect" (a graph property related to clique and chromatic numbers).
  • Biclique Analysis: The paper extensively studies bicliques in bipartite graphs, including their enumeration and properties, which are crucial for the IvBE algorithm.
  • Combinatorial Approach: The research emphasizes a combinatorial approach to GI, contrasting with more modern group-theoretic methods.

Datasets

Not discussed in the paper. The paper focuses on theoretical graph properties and algorithmic development rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bicliques as Analogues to Cliques: For bipartite graphs, bicliques in the weak modular product play a role analogous to cliques in general graphs, serving as indicators of isomorphism.
  • Tractability for Specific Bipartite Classes: The IvBE algorithm demonstrates polynomial-time solvability for bipartite $2K_2$-free graphs and quasi-polynomial time for families with slowly growing induced matchings and crown graphs. This highlights that GI can be efficiently solved for certain structured subclasses of bipartite graphs.
  • Perfection and Isomorphism: The paper connects the property of the weak modular product being "perfect" to polynomial-time isomorphism testing. However, they show this is only true in trivial cases for balanced bipartite graphs, suggesting limitations of this specific approach for general bipartite graphs.
  • New Graph Product (VWMP): The introduction of the very weak modular product provides a tool to analyze the perfection property of the weak modular product in the context of balanced bipartite graphs.

Key Results

  • IvBE Algorithm: An algorithm is proposed for bipartite graph isomorphism.
  • Polynomial Time for $2K_2$-free Bipartite Graphs: IvBE runs in polynomial time for bipartite graphs that do not contain an induced $2K_2$.
  • Quasi-Polynomial Time: IvBE runs in quasi-polynomial time for bipartite graph families where the largest induced matching and crown graph grow polylogarithmically.
  • Perfect WMP Implies Polynomial Isomorphism: A straightforward corollary of Kozen's theorem and Lovász's sandwich theorem is that if the weak modular product of two graphs is perfect, then checking isomorphism is polynomial.
  • Trivial Cases for Perfect WMP in Balanced Bipartite Graphs: For balanced bipartite graphs, the weak modular product is perfect only in a few trivial cases (e.g., both graphs are complete bipartite graphs $K_{n,n}$ or empty graphs).
  • Characterization of Maximal Bicliques: The paper provides bounds and characterizations for the number of maximal bicliques in certain classes of bipartite graphs, including extremal cases and random bipartite graphs.

Limitations and Future Work

  • Limited Scope of Perfect WMP: The paper shows that the condition of the weak modular product being perfect only leads to polynomial isomorphism testing in a few trivial cases for balanced bipartite graphs. This suggests that this specific avenue might not be a universal solution for bipartite graph isomorphism.
  • Open Questions: The authors identify several open questions:
  • Extending the characterization of perfect weak modular products to general graphs and other graph subclasses.
  • Investigating approximation schemes for the clique number in conjunction with the weak modular product for graph isomorphism.
  • Exploring modifications of existing algorithms for dual problems (like finding independence numbers) for potential applications to the very weak modular product.
  • Future Work: The paper suggests that the results on bicliques in bipartite graphs may be of independent interest and could be a starting point for further research. The IvBE algorithm's efficiency for specific classes also opens avenues for exploring its applicability to other graph subclasses.

Summary updated

Abstract

A 1978 theorem of Kozen states that two graphs on $n$ vertices are isomorphic if and only if there is a clique of size $n$ in the weak modular product between the two graphs. Restricting to bipartite graphs and considering complete bipartite subgraphs (bicliques) therein, we study the combinatorics of the weak modular product. We identify cases where isomorphism is tractable using this approach, which we call Isomorphism via Biclique Enumeration (IvBE). We find that IvBE is polynomial for bipartite $2K_2$-free graphs and quasi-polynomial for families of bipartite graphs, where the largest induced matching and largest induced crown graph grows slowly in $n$, that is, $O(\mathrm{polylog }\, n)$. Furthermore, as expected a straightforward corollary of Kozen's theorem and Lovász's sandwich theorem is if the weak modular product between two graphs is perfect, then checking if the graphs are isomorphic is polynomial in $n$. However, we show that for balanced, bipartite graphs this is only true in a few trivial cases. In doing so we define a new graph product on bipartite graphs, the very weak modular product. The results pertaining to bicliques in bipartite graphs proved here may be of independent interest.
BibTeX
@misc{dervovic2017weak,
  author = {Danial Dervovic and Simone Severini},
  title = {{Weak Modular Product of Bipartite Graphs, Bicliques and Isomorphism}},
  year = {2017},
  eprint = {1707.05179},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.05179},
}

Loading related content...

Figure