2026-07-22T01:18:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17129 2024-03-06T10:59:02Z ddc:004 open_access

Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks Mehta, Hermish Reichman, Daniel Graph Algorithms Random Graphs Data Structures and Algorithms Discrete Mathematics 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 nearly 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) poly(n), improving upon the 2^Ω(k) poly(n) performance of the best-known algorithms designed for worst-case instances of these edge deletion problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hermish Mehta and Daniel Reichman 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.7 urn:nbn:de:0030-drops-171299 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.7 eng https://creativecommons.org/licenses/by/4.0/legalcode