Doubly weighted rooted trees and computer networks 09/26/2019

Speaker: Geir Agnarsson, George Mason
Date and time: Thursday, September 26, 2:15–3:15pm
Place: Phillips 110

Abstract: Let $T$ be a rooted tree with $n\in{\mathbb N}$ non-root vertices provided with two functions: $p : V(T) \rightarrow{\mathbb Q}$ on the vertices and $c : E(T) \rightarrow {\mathbb Q}$ on the edges, and two fixed numbers $B, G \in {\mathbb Q}^{+}$ . We consider the Game-Over Attack Strategy (GOAS) of finding a rooted subtree $T'\subseteq T$ such that $p(T') = \sum_{u\in V(T')}p(u)\geq G$ and $c(T') = \sum_{e\in E(T')}c(e)\leq B$ . In general, this decision problem is NP-complete, but that not the whole story. There are numerous special cases that can be solved in polynomial time in n, and these cases can be viewed as models for many security protocols in computer networks. The somber conclusion one can draw from this is that hacking into a computer system is theoretically easy! This is joint work with Ray Greenlaw and Sanpawat Kantrabutra.