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(x6), CLC(x7), and CLC(x8) defined for x6 = (0, 1, 3, 3), x7 = (0, 4, 2, 3), x8 = (0, 3, 2, 4) are NP-complete. Sample instances of these three subproblems are shown in Figures 12.3 to 12.5.
In the proof of NP-completeness of each subproblem the following NP complete problem is used.