Network control refers to a very large and diverse set of problems that involve control actions over a network such as choosing optimal routes through the network or scheduling optimal actions at vertices. Another area of network control involves linear time-invariant dynamical systems evolving over time that have inputs and outputs. The network control problem in this setting is to select the appropriate input to steer the network into a desired output state. Examples of the output state include the throughput of a communications network, transcription factor concentration in a gene regulatory network, customer purchases in a marketing context subject to social influences and the amount of flux flowing through a biochemical network.
We focus on control of linear dynamical systems under the notion of structural controllability which is intimately connected to finding maximum matchings. Hence, the objective becomes of studying scalable and fast algorithms for this task. We first show the convergence of matching algorithms for different random networks and then analyze a popular, fast and practical heuristic one which is due to Karp and Sipser. The optimality of both Karp-Sipser Algorithm and a simplification of it for an extensive class of random networks will be proved as well.
