Abstract: In modern applications of graph algorithms, where the graphs of interest are large and dynamic, it is unrealistic to assume that an input representation contains the full information of a graph being studied. For example, consider a social network, where a vertex corresponds to a user and an edge corresponds to a friendship relation.
It is reasonable to assume that users do not always update new friendships on the social network, and that sometimes they do not fully disclose their friendship relations for security or privacy reasons.
This motivates the design of graph algorithms that, in spite of being given only a (large) subgraph as input, output solutions that are close to the solutions output when the whole graph is available. In this talk, I will introduce a notion of sensitivity of graph algorithms that formalizes this desirable feature. After discussing the basic properties of our sensitivity definition, I will give an overview of our main results, and present the key ideas used in the design of our algorithm with low sensitivity for the global minimum cut problem.
