We study the notion of local treewidth in sparse random graphs: the maximum treewidth over all $k$-vertex subgraphs of an $n$-vertex graph. When $k$ is not too large, we give nearly tight bounds for this local treewidth parameter; we also derive tight bounds for the local treewidth of noisy trees, trees where every non-edge is added independently with small probability. We apply our upper bounds on the local treewidth to obtain fixed parameter tractable algorithms (on random graphs and noisy trees) for edge-removal problems centered around containing a contagious process evolving over a network. In these problems, our main parameter of study is $k$, the number of initially ``infected'' vertices in the network. For the random graph models we consider and a certain range of parameters the running time of our algorithms on $n$-vertex graphs is $2^{o(k)}\textrm{poly}(n)$, improving upon the $2^{Ω(k)}\textrm{poly}(n)$ performance of the best-known algorithms designed for worst-case instances of these edge deletion problems.

We study the independent set problem in a semi-random model proposed by Feige and Kilian. This model selects a graph with a planted independent set of size k and then allows an adversary to modify a large fraction of edges: the subgraph induced by the complement of the independent set can be modified arbitrarily, and the adversary may add (but not delete) edges from the independent set to its complement. In particular, the adversary can create a graph in which the initial planted independent set is not the largest independent set. Feige and Kilian presented a randomized algorithm, which with high probability recovers an independent set of size at least k (which may not be the planted one) when k = an where a is a constant, and the probability of a random edge p > (1 + ϵ) ln n/αn. We give a new deterministic algorithm in the Feige-Kilian model that finds an independent set of size at least .99k provided that the planted set has size k = Ω(n2/3/p1/3), and finds a list of independent sets, one of which is the planted one provided that k = Ω(n2/3/p). This improves on the algorithm of Feige and Kilian by working for smaller k if p = Ω(1/n1/3), and improves on an algorithm of Steinhardt by working for slightly smaller k and by working against a stronger adversarial model. The ability to find a good approximation of the largest independent set is new when p < ln n/k.