Abstract
We study the notion of local treewidth in sparse random graphs: the maximum treewidth over all -vertex subgraphs of an -vertex graph. When 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 , 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 -vertex graphs is , improving upon the performance of the best-known algorithms designed for worst-case instances of these edge deletion problems.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.