Find criteria for determining that a graph is not a perfect graph

[lichengzhang1]

Crossed post in https://mathematica.stackexchange.com/questions/tagged/graphs-and-networks

What is the feature or improvement you would like to see? Find criteria for determining that a graph is not a perfect graph

A graph is perfect if the clique number and the chromatic number is the same for every induced subgraph of the graph. A polynomial-time algorithm exists for determining if a graph is perfect. (Cornuéjols G, Liu X, Vuskovic K. A polynomial algorithm for recognizing perfect graphs[C]//44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE, 2003: 20-27.)

IGraphM includes a function called IGperfectQ. According to its documentation, IGperfectQ utilizes the strong perfect graph theorem: it checks that neither the graph nor its complement contains an odd-length hole. However, the documentation does not provide further justification or additional details, such as identifying an odd hole or an odd antihole if one exists.

G1 = Graph[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
    18, 19, 20, 21, 22, 23, 24}, {Null, 
   SparseArray[Automatic, {24, 24}, 
    0, {1, {{0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 
       60, 64, 68, 72, 76, 80, 84, 88, 92, 
       96}, {{2}, {3}, {4}, {5}, {1}, {5}, {6}, {7}, {1}, {7}, {8}, \
{9}, {1}, {9}, {10}, {11}, {1}, {2}, {11}, {12}, {2}, {12}, {13}, \
{14}, {2}, {3}, {8}, {14}, {3}, {7}, {15}, {16}, {3}, {4}, {16}, \
{17}, {4}, {11}, {17}, {18}, {4}, {5}, {10}, {19}, {5}, {6}, {13}, \
{19}, {6}, {12}, {20}, {21}, {6}, {7}, {15}, {21}, {8}, {14}, {21}, \
{22}, {8}, {9}, {17}, {22}, {9}, {10}, {16}, {23}, {10}, {19}, {20}, \
{23}, {11}, {12}, {18}, {20}, {13}, {18}, {19}, {24}, {13}, {14}, \
{15}, {24}, {15}, {16}, {23}, {24}, {17}, {18}, {22}, {24}, {20}, \
{21}, {22}, {23}}}, Pattern}]}, {FormatType -> TraditionalForm, 
   GraphLayout -> {"Dimension" -> 2}, ImageSize -> {100, 100}, 
   PlotRange -> All, PlotTheme -> "Monochrome", 
   VertexCoordinates -> {{0.7071067811865475, -0.7071067811865475}, \
{0.3743506488634663, -0.23570226039551573}, {0.7071067811865475, 
      0.7071067811865475}, {-0.7071067811865475, \
-0.7071067811865475}, {0.23570226039551578, -0.3743506488634662}, \
{0.18024290500833565, -0.09705387192756525}, {0.37435064886346636, 
      0.23570226039551584}, {0.23570226039551584, 
      0.3743506488634663}, {-0.7071067811865475, 
      0.7071067811865475}, {-0.37435064886346625, \
-0.23570226039551576}, {-0.23570226039551578, -0.37435064886346625}, \
{0.09705387192756534, -0.18024290500833556}, {0.06932419423397529, \
-0.06932419423397518}, {0.18024290500833567, 
      0.09705387192756536}, {0.09705387192756541, 
      0.18024290500833562}, {-0.2357022603955157, 
      0.37435064886346625}, {-0.37435064886346625, 
      0.23570226039551578}, {-0.18024290500833556, \
-0.0970538719275653}, {-0.0970538719275653, -0.18024290500833556}, \
{-0.06932419423397519, -0.06932419423397518}, {0.0693241942339753, 
      0.06932419423397525}, {-0.09705387192756523, 
      0.18024290500833556}, {-0.18024290500833554, 
      0.09705387192756532}, {-0.06932419423397516, 
      0.06932419423397523}}, VertexSize -> {{0.01, 0.01}}, 
   VertexStyle -> {GrayLevel[0.6]}}]
IGPerfectQ[G1]

[szhorvat]

Is this a feature request to implement the algorithm you cite? If so, can you re-post it at https://github.com/igraph/igraph/ ?

As for how it works now in IGraph/M:

https://github.com/szhorvat/IGraphM/blob/8de23ab6b2dcab448ba13bffe4c3a864c54927e7/IGraphM/LibraryResources/Source/IG.h#L3331-L3381

• check for bipartiteness
• check for chordality
• see if the girth of the graph or its complement is odd
• otherwise look for odd induced cycles of increasing size in the graph and its complement using LAD; this is inefficient, hence the more efficient tests at the start

This was ported to the C core here: https://github.com/igraph/igraph/blob/master/src/properties/perfect.c

[lichengzhang1]

Thank you, I thought the algorithm implemented by igraph was polynomial. It seems it isn't as you said. I will report this feature request .