Skip to Content

Yaniv J. Ovadia

Picture of Yaniv J. Ovadia.

Thesis

Computational Feasibility of Increasing the Visibility of Vertices in Covert Networks

Advisor
Susan E. Martonosi
Second Reader(s)
Nicholas Pippenger

Abstract

Disrupting terrorist and other covert networks requires identifying and capturing key leaders. Previous research by Martonosi et al. (2009) defines a load metric on vertices of a covert network representing the amount of communication in which a vertex is expected to participate. They suggest that the visibility of a target vertex can be increased by removing other, more accessible members of the network. This report evaluates the feasibility of efficiently calculating the optimal subset of vertices to remove.

We begin by proving that the general problem of identifying the optimally load maximizing vertex set removal is NP-complete. We then consider the feasibility of more quickly computing the load maximizing single vertex removal by designing an efficient algorithm for recomputing Gomory–Hu trees. This leads to a result regarding the uniqueness of Gomory–Hu trees with implications towards the feasibility of one approach for Gomory–Hu tree reconstruction. Finally, we propose a warm start algorithm which performs this reconstruction, and analyze its runtime experimentally.

Proposal

Efficient Reconstruction of Gomory-Hu Trees

Additional Materials

Poster