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:

IGraphM/IGraphM/LibraryResources/Source/IG.h

Lines 3331 to 3381 in 8de23ab

	bool perfectQ() { /* TODO: re-add const once ladSubisomoprhic could be made const */
	// bipartite graphs and chordal graphs are perfect
	if (bipartiteQ() || chordalQ())
	return true;
	// possibly more optimizations found here: http://www.or.uni-bonn.de/~hougardy/paper/ClassesOfPerfectGraphs.pdf
	IG comp;
	comp.complement(*this);
	// weak perfect graph theorem:
	// a graph is perfect iff its complement is perfect
	if (comp.bipartiteQ() || comp.chordalQ())
	return true;
	mint g = girth();
	if (g > 3 && g % 2 == 1)
	return false;
	mint cg = comp.girth();
	if (cg > 3 && cg % 2 == 1)
	return false;
	// since bipartiteQ() also catches trees, at this point g and cg are both at least 3.
	// for trees, their value would have been 0
	// strong perfect graph theorem:
	// a graph is perfect iff neither it or its complement contains an induced odd cycle of length >= 5
	mint vcount = vertexCount();
	mint start = std::min(g, cg);
	start = start % 2 == 0 ? start+1 : start+2;
	IG cycle;
	for (mint s = start; s <= vcount; s += 2) {
	igVector edges(2*s);
	for (int i=0; i < s; ++i) {
	edges[2*i] = i;
	edges[2*i + 1] = i+1 < s ? i+1 : 0;
	}
	cycle.fromEdgeList(edges, s, false);
	if (s > g && ladSubisomorphic(cycle, /* induced = */ true))
	return false;
	if (s > cg && comp.ladSubisomorphic(cycle, /* induced = */ true))
	return false;
	mma::check_abort();
	}
	return true;
	}

• 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 .