Network Conduciveness with Application to the Graph-Coloring and Independent-Set Optimization Transitions

Background: Given an undirected graph, we consider the two problems of combinatorial optimization, which ask that its chromatic and independence numbers be found. Although both problems are NP-hard, when either one is solved on the incrementally denser graphs of a random sequence, at certain critical values of the number of edges, it happens that the transition to the next value causes optimal solutions to be obtainable substantially more easily than right before it. Methodology/Principal Findings: We introduce the notion of a network's conduciveness, a probabilistically interpretable measure of how the network's structure allows it to be conducive to roaming agents, in certain conditions, from one portion of the network to another. We demonstrate that the performance jumps of graph coloring and independent sets at the critical-value transitions in the number of edges can be understood by resorting to the network that represents the solution space of the problems for each graph and examining its conduciveness between the non-optimal solutions and the optimal ones. Right past each transition, this network becomes strikingly more conducive in the direction of the optimal solutions than it was just before it, while at the same time becoming less conducive in the opposite direction. Conclusions/Significance: Network conduciveness provides a useful conceptual framework for explaining the performance jumps associated with graph coloring and independent sets. We believe it may also become instrumental in helping clarify further issues related to NP-hardness that remain poorly understood. Additionally, it may become useful also in other areas in which network theory has a role to play.