Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/networkx/algorithms/perfect_graph.py: 89%

1import itertools 

2 

3import networkx as nx 

4from networkx.utils.decorators import not_implemented_for 

5 

6__all__ = ["is_perfect_graph"] 

7 

8 

9@nx._dispatchable 

10@not_implemented_for("directed") 

11@not_implemented_for("multigraph") 

12def is_perfect_graph(G): 

13 r"""Return True if G is a perfect graph, else False. 

14 

15 A graph G is perfect if, for every induced subgraph H of G, the chromatic 

16 number of H equals the size of the largest clique in H. 

17 

18 According to the **Strong Perfect Graph Theorem (SPGT)**: 

19 A graph is perfect if and only if neither the graph G nor its complement 

20 :math:`\overline{G}` contains an **induced odd hole** — an induced cycle of 

21 odd length at least five without chords. 

22 

23 Parameters 

24 ---------- 

25 G : NetworkX Graph 

26 The graph to check. Must be a finite, simple, undirected graph. 

27 

28 Returns 

29 ------- 

30 bool 

31 True if G is a perfect graph, else False. 

32 

33 Notes 

34 ----- 

35 This function uses a direct approach: cycle enumeration to detect 

36 chordless odd cycles in G and :math:`\overline{G}`. This implementation 

37 runs in exponential time in the worst case, since the number of chordless 

38 cycles can grow exponentially. 

39 

40 The perfect-graph recognition problem is theoretically solvable in 

41 polynomial time. Chudnovsky *et al.* (2006) proved it can be solved in 

42 :math:`O(n^9)` time via a complex structural decomposition [1]_, [2]_. 

43 This implementation opts for a direct, transparent check rather than 

44 implementing that high-degree polynomial-time decomposition algorithm. 

45 

46 See Also 

47 -------- 

48 is_chordal, is_bipartite : 

49 Related checks for specific categories of perfect graphs, such as chordal 

50 graphs, and bipartite graphs. 

51 chordless_cycles : 

52 Used to detect "holes" in the graph 

53 

54 References 

55 ---------- 

56 .. [1] M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, 

57 *The Strong Perfect Graph Theorem*, 

58 Annals of Mathematics, vol. 164, no. 1, pp. 51–229, 2006. 

59 https://doi.org/10.4007/annals.2006.164.51 

60 .. [2] M. Chudnovsky, G. Cornuéjols, X. Liu, P. Seymour, and K. Vušković, 

61 *Recognizing Berge Graphs*, 

62 Combinatorica 25(2): 143–186, 2005. 

63 DOI: 10.1007/s00493-005-0003-8 

64 Preprint available at: 

65 https://web.math.princeton.edu/~pds/papers/algexp/Bergealg.pdf 

66 """ 

67 

68 return not any( 

69 (len(c) >= 5) and (len(c) % 2 == 1) 

70 for c in itertools.chain( 

71 nx.chordless_cycles(G), nx.chordless_cycles(nx.complement(G)) 

72 ) 

73 )