## 12.5 Complexities of Eight Representatives of Class CLC(*X*)

In this section eight specific subproblems of the CLC problem belonging to class CLC(*X*) will be analyzed in light of their complexity. As will be shown, three of them are NP-complete, thereby confirming the NP-completeness of the original CLC problem. For the other five subproblems polynomial-time algorithms will be presented solving those special cases to the optimum. At first glance, the selection of these eight representatives of class CLC(*X*) seems random. But this is not the case, as we will see in Section 12.6.

### 12.5.1 **Three NP-Complete Subproblems**

In this section it will be shown that three subproblems CLC(*x*_{6}), CLC(*x*_{7}), and CLC(*x*_{8}) defined for *x*_{6} = (0, 1, 3, 3), *x*_{7} = (0, 4, 2, 3), *x*_{8} = (0, 3, 2, 4) are NP-complete. Sample instances of these three subproblems are shown in Figures 12.3 to 12.5.

**Figure 12.3** A sample instance of the CLC(0,1,3,3) problem (NP-complete).

**Figure 12.4** A sample instance of the CLC(0,4,2,3) problem (NP-complete).

**Figure 12.5** A sample instance of the CLC(0,3, 2, 4) problem (NP-complete).

In the proof of NP-completeness of each subproblem the following NP complete problem is used.

**3-SAT Problem**