O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required