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.

  • $\begingroup$ I would bet with odds 10/1 that this problem is NP-hard since the treewidth of $n\times n$ King's graph is greater than $n$ and it is not bipartite. $\endgroup$
    – John L.
    May 4, 2019 at 18:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.