19. Inclusion-Exclusion

Inclusion-exclusion is a well-known technique used in combinatorics. Given a set of objects and a set of properties \(P_1, \ldots, P_n\), the goal is to count all objects that have none of the properties \(P_1, \ldots, P_n\). There exist numerous examples where it is fairly easy to count the number of objects that have at least some subset of these properties but it is hard to directly count the number of objects that have none of the properties \(P_1, \ldots, P_n\). In such cases, inclusion-exclusion provides a useful tool for counting the number of objects that do not have any of the properties \(P_1, \ldots, P_n\). What may be surprising is that inclusion-exclusion can be turned into an effective tool for solving a range of NP-hard problems.

In this chapter, we study applications of inclusion-exclusion to two classical NP-hard problems: finding a Hamiltonian cycle and graph colouring. Both problems can also be solved using dynamic programming.

In the case of finding a Hamiltonian cycle, both the dynamic programming and the inclusion-exclusion algorithms take \(O^*(2^n)\) time. The advantage of the inclusion-exclusion algorithm is that it uses only linear space while the dynamic programming algorithm uses exponential space. As pointed out before, exponential space requirements are a much greater limitation of the applicability of an algorithm than exponential running time. Thus, inclusion-exclusion algorithms are often much more useful in practice than exponential-time dynamic programming algorithms.

In the case of graph colouring, inclusion-exclusion leads to substantially faster algorithms than dynamic programming. If we are willing to use exponential space, we can find an optimal graph colouring in \(O^*(2^n)\) time using inclusion-exclusion. Using linear space, we obtain an \(O^*(3^n)\)-time algorithm. This latter algorithm uses a simple \(O^*(2^n)\)-time algorithm for counting all independent sets in a graph as a building block. By using a faster (and non-trivial) \(O^*(1.25^n)\)-time algorithm for counting independent sets instead, the running time of the graph colouring algorithm is improved to \(O^*(2.25^n)\) while maintaining the polynomial space requirements of the algorithm. All graph colouring algorithms based on dynamic programming use exponential space. For a long time, Lawler's algorithm, with running time \(O^*(2.44^n)\), was the best known graph colouring algorithm based on dynamic programming. This bound has been improved somewhat but remains well above of the \(O^*(2.25^n)\) time bound of the polynomial-space algorithm obtainable using inclusion-exclusion.