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.

images

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

images

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

images

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

Get Analysis of Complex Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.