2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If I don't misread your post, your graphs have at most 4^15 vertices and therefore any problem can be solved in constant time... ?! $\endgroup$
    – monkeymaths
    Commented Dec 28, 2015 at 13:12
  • $\begingroup$ I have 14 graphs, each has 16, 64, ..., $4^{15}$ vertices. N<15 because practically I don't need to calculate for so large a graph, but theoretically you can construct one with larger N. $\endgroup$
    – Wei Feng
    Commented Dec 28, 2015 at 13:37

4 Answers 4

Reset to default
2
$\begingroup$

I dare say that you are looking at your problem from the wrong side. Load your graph in a graph library (like Sage) and see how the independent set algorithms perform. Sage, for instance, uses Linear Programming or Cliquer, depending on what you ask it.

Going through theoretical knowledge may give you the wrong impression that your problem is very hard, while it may be easy to solve in practice. If all you care about is find those independent set you should start with the code and look at the theory if they fail you.

Nathann

P.S.: Given that the properties of your graphs seem very "artificial", I expect that you generated your graphs in some way. Thus they may have a large automorphism group, and you can definitely use this kind of information to simplify the computations.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your answer. You are right. The graphs are generated to solve a bioinformatic problem, and are quite symmetry. I haven't figure out how to utilize the symmetry property. However, following your guidance, I have got the maximum independent set for $N \in \{2,3,4\}$ using the python module networkx, and somehow found some interesting features. Possibly the solution is around the corner. Thank you again for your help! $\endgroup$
    – Wei Feng
    Commented Dec 28, 2015 at 13:51
2
$\begingroup$

http://graphclasses.org contains large database of graph classes and complexity of problems.

Polynomial independent set is: http://graphclasses.org/classes/problem_Independent_set.html

A lot of classes are defined by forbidden induced subgraphs.

If you are lucky, your graph might be in a polynomial class.

Improve this answer
$\endgroup$
1
$\begingroup$

Graphs of bounded (constant) treewidth are one such class.

I believe the original citation for this is Arnborg and Proskurowski, "Linear time algorithms for NP-hard problems restricted to partial k-tree", but by now it is almost the standard example of an NP-complete problem becoming polynomial time on graphs of bounded treewidth.

These notes by Daniel Marx are a friendly introduction, discussing Independent Set right at the beginning.

Improve this answer
$\endgroup$
0
$\begingroup$

Considering your graphs seem to be defined sequentially (for numbers $N$ in $[2,15]$), if your graphs are constructed in a way that the graph at $N$ can be constructed from operations that duplicate (possibly 4?) copies of the graph at $N-1$, then independent sets could possibly be constructed for large graphs by combining solutions in the smaller graphs (depending on what the actual definition of these graphs are). Mere properties about degrees won't be enough to advise on an ideal algorithm.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .