Towards Controllability Analysis of Dynamic Networks Using Minimum Dominating Set

Finding a minimum dominating set is a classic NP-hard problem from graph theory. Given a finite, simple, undirected graph, it seeks a smallest set of vertices with the property that every vertex in the graph is either in or adjacent to at least one member of that set. In recent years, it has found increased application, particularly when used as the basis for classifying nodes of biological networks. Sample networks include those derived from metabolic, noncoding RNA and protein-protein interaction data. Classification schemes employed to date, however, have typically been limited by the need to solve multiple problem instances, which naturally constrains the size of amenable networks. Moreover, analytical methods based on minimum dominating set have thus far generally been limited to static graphs. In this paper, work in progress is described that improves upon these algorithms and applies them to dynamic streaming graphs in order to capture control structures as they evolve over time. Results demonstrate the effectiveness of these techniques at reducing computational overhead. A systematic experimental setup and a description of testbed construction is also provided.