Local treewidth of random and noisy graphs with applications to stopping contagion in networks

preprint2022arXivOpen access

Abstract

We study the notion of local treewidth in sparse random graphs: the maximum treewidth over all kk-vertex subgraphs of an nn-vertex graph. When kk 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 kk, 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 nn-vertex graphs is 2o(k)poly(n)2^{o(k)}\textrm{poly}(n), improving upon the 2Ω(k)poly(n)2^{Ω(k)}\textrm{poly}(n) performance of the best-known algorithms designed for worst-case instances of these edge deletion problems.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.