Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.7
URN: urn:nbn:de:0030-drops-171299
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17129/
Mehta, Hermish ; Reichman, Daniel
Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{mehta_et_al:LIPIcs.APPROX/RANDOM.2022.7,
author = {Mehta, Hermish and Reichman, Daniel},
title = {{Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {7:1--7:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-249-5},
ISSN = {1868-8969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17129},
URN = {urn:nbn:de:0030-drops-171299},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.7},
annote = {Keywords: Graph Algorithms, Random Graphs, Data Structures and Algorithms, Discrete Mathematics}
}
| Keywords: | Graph Algorithms, Random Graphs, Data Structures and Algorithms, Discrete Mathematics | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 15.09.2022 |
