Let $0 < A < 1$ and $G$ be connected d-regular graph with degree $d=[A n]$. The density of $G$ is about $A$.
Q1 Are there constraints on $A$ such that finding maximum independent set of $G$ is polynomial?
Q2 In case there is artificial construction for NP-hardness, assume $G$ is random graph.
Arguments that this may be possible for $A \ge \frac12$.
Assume that $A \ge \frac12$ and you have guessed vertex $v_0$ in MIS. From $G$ delete $v_0$ and all $[A n]$ neighbors of $v_0$. The resulting graph $G'$ is of order $n' \le [(1-A)n] \le \frac12 n$. So a single guess reduces the number of vertices by factor of at least $\frac12$. After about $\log_2{n}$ guesses we get an independent set. If the guess is wrong, try another vertex.
We got experimental support for random graphs in sagemath.
The algorithm cliquer solved $A=\frac12$ and $n=10^3$ in 5 minutes and $n=500$ in 3 seconds.
Our toy implementation works in seconds for $n=50$.
Q3 How to explain the experimental results?
toy sage implementation:
def denseis(G):
"""
Computes maximum independent set in a dense graph
"""
if G.is_independent_set(): return G.order()
m=0
if not G.is_connected():
return max([denseis(i) for i in G.connected_components_subgraphs()])
for v in G.vertices():
F=G.copy()
nei=[v]+F.neighbors(v)
F.delete_vertices(nei)
m=max(m,1+denseis(F))
return m
#Compute maximum independent set
sage: set_random_seed(1);n=80;A=2/3;G=graphs.RandomRegular(round(A*n),n)
sage: time denseis(G)
CPU times: user 2.63 s, sys: 0 ns, total: 2.63 s
Wall time: 2.63 s
6
