Abstract
In this paper we enumerate the necessary and sufficient conditions for the weak modular product of two simple graphs to be perfect. The weak modular product differs from the direct product by also encoding non-adjacencies of the factor graphs in its edges. This work is motivated by the following: 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. Furthermore, 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$. Interesting cases include complete multipartite graphs and disjoint unions of cliques. All perfect weak modular products have factors that fall into classes of graphs for which testing isomorphism is already known to be polynomial in the number of vertices.
Introduction: The Graph Isomorphism Challenge
The Graph Isomorphism (GI) problem—determining if two graphs are structurally identical—occupies a unique space in computational complexity. While not proven to be NP-complete, it has long resisted a general polynomial-time solution. A significant theoretical bridge was built in 1978 when Dexter Kozen demonstrated that two graphs with $n$ vertices are isomorphic if and only if their weak modular product contains a clique of size $n$.
However, finding the maximum clique in a general graph is NP-hard. This research explores a specific bypass: perfect graphs. In perfect graphs, the clique number equals the chromatic number for every induced subgraph, allowing the maximum clique to be found in polynomial time via Lovász’s "sandwich theorem." By characterizing when a weak modular product is perfect, we identify cases where GI is guaranteed to be solvable in polynomial time.
Methodology: Forbidden Subgraphs and SPGT
The study employs a combinatorial approach centered on the Strong Perfect Graph Theorem (SPGT). According to the SPGT, a graph is perfect if and only if it contains no induced odd cycles of length five or greater (odd holes) or their complements (odd antiholes).
The author systematically analyzes various graph families—including paths, cycles, and complete multipartite graphs—to identify which combinations yield perfect products. A critical part of this process involves a "forbidden subgraph search." By identifying specific induced structures within the product graph that violate the SPGT, the author can rule out pairs of graphs.
Key Results: The 10 Scenarios
The core contribution of this work is Theorem 1, which provides an exhaustive list of 10 necessary and sufficient conditions for a weak modular product to be perfect. These scenarios range from simple cases where one graph is extremely small to more complex structures like disjoint unions of cliques or complete multipartite graphs.
From a complexity perspective, the results are illuminating but restrictive. While the perfection of the product graph does indeed ensure a polynomial-time GI algorithm, the author observes that all 10 identified classes already had known efficient GI solutions. For instance:
- Cographs (appearing in several cases) have well-established linear-time GI algorithms.
- Disjoint unions of cliques or stars are trivial to compare by sorting component sizes.
Conclusion and Future Directions
The primary limitation of this approach is that the "perfection" constraint is highly restrictive. It effectively captures graph classes that are already computationally "simple," failing to uncover new territories where GI might be polynomial.
Future research may look toward "near-perfect" products or alternative graph products that might maintain the link to isomorphism while producing more diverse and complex structures. Investigating extensions to directed graphs or hypergraphs also remains an open area for exploration.
Summary updated