I would like to find a maximum weight independent set in a finite section of a King's graph.
For an $m\times n$ King's graph where $n \ll m$, we can use an $O(2^{2n} m)$ bitmask dynamic programming solution. We proceed row by row, and on each row, we try all possible ways to select cells.
On the other hand, it is not obvious to me whether this problem is NP-hard. Just like how the problem on a grid graph may be solved by bipartite matching, I suspect that there may exist some sort of blossom algorithm or similar which would admit a polynomial time solution to the King's graph case.
