Abstract by James Scott
Detecting Decentralized Malware
The Fractional Prize-Collecting Steiner Tree Problem (FPCSTP) is NP-Hard in general, but was recently shown to be solvable in worst-case quadratic time on rooted trees. We observe that the algorithm that quickly solves the FPCSTP on rooted trees can be run on a larger class of networks--the "multitrees"--with the same runtime, and that the algorithm cannot terminate with sensible output on a network that is not a multitree. In fact, many dynamic programming algorithms made to run on rooted trees can also run (and terminate with sensible output) on multitrees with no sacrifice of runtime. This is desirable to us since the network on which we wish to solve the FPCSTP is approximately a multitree. With that in mind, have developed an algorithm that finds a maximal spanning multitree in an arbitrary DAG (directed acyclic graph). We will discuss an application involving detection of malware distributed among several files in a computer.