Analysis of Complex Networks

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₆), CLC(x₇), and CLC(x₈) defined for x₆ = (0, 1, 3, 3), x₇ = (0, 4, 2, 3), x₈ = (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