In this report, we investigate the NP-complete minimum contagious set problem in bootstrap percolation. We present the following: three new bounds providing approximations for the size of minimum contagious sets, efficient and optimal algorithms for special types of graphs, and an optimal algorithm for any graph. Furthermore, we created a publicly available software product named `Booper', a web application that can help mathematicians research and visualize bootstrap percolation. Users of Booper are able to upload a custom graph, find the minimum contagious set of a graph, perform iterations of bootstrap percolation with user-defined threshold and probability parameters, and much more.

• This report represents the work of one or more WPI undergraduate students submitted to the faculty as evidence of completion of a degree requirement. WPI routinely publishes these reports on its website without editorial or peer review.

Creator

• Poskanzer, Henry
• Anderson, Connor C.
• Balasubramanian, Akshaj

Publisher

• Worcester Polytechnic Institute

Identifier

• E-project-050421-171326
• 22011

Keyword

• NP-completeness
• Graph visualization
• Contagious sets
• Web application
• Graph theory
• Bootstrap percolation

Award

• Provost's MQP Award

Advisor

• Sarkozy, Gabor N
• Reichman, Daniel

Year

• 2021

Date created

• 2021-05-04

Resource type

• Major Qualifying Project

Major

• Computer Science

Rights statement

• In Copyright

License

• Creative Commons BY Attribution 4.0 International

Last modified

• 2023-01-19