I need to find the maximum independent sets of a serial of regular graphs, which is generally NP-complete.
The wikipedia told me that this problem can be solved in polynomial time if the graph is claw-free or perfect, or its complement graph is chordal. However, to my dismay, I have validated that my graphs possess none of the properties above.
Currently, all properties I know about my graphs are:
- Contain $4^N$ vertices, while $N$ is an integer in $[2,15]$;
- Undirected and simple (no vertex is connected to itself);
- Regular, i.e., each vertex is connected to the same number of other vertices;
- The degree of each vertex is $3(2^N-1)$, so the graph becomes sparse when $N$ is large.
Are there any types of graph other than claw-free or perfect whose maximum independent set can be found in polynomial time? I would check whether my graphs have such properties.