Basic Definitions

• An undirected graph $G=(V,E)$ is defined by a set of vertices, $V$, and a set of edges, $E$, where each edge in $E$ is an unordered pair of vertices drawn from $V$.

• A weighted undirected graph $G=(V,E,W)$ is an undirected graph $(V,E)$ with an associated weight function, $W: E \rightarrow {\mathbb R}_{+}$, that assigns a non-negative real weight to each edge in $E$.

• A labeled weighted undirected graph $G=(V,E,W, L)$ is a weighted undirected graph $(V,E,W)$ with an associated labeling function, $L$, that assigns a label to each vertex in $V$. In GraSPI, we label each vertex by a color.

• A path between a source vertex, $s \in V$, and a target vertex, $t \in V$ is a sequence $p=[v_0, v_1, \dots v_i \dots v_k]$ of vertices such that $v_o=s$, $v_k=t$ and for each $i$ from $0$ to $i-1$, vertices $v_i$ and $v_{i+1}$ are adjacent in $G$. The length of path $p$ is $\sum_{i=0}^{k-1}w(e(v_i,v_{i+1}))$.

• A shortest path between a source vertex $s \in V$ and a target vertex $t \in V$ is a path between $s$ and $t$ that is of the shortest length among all paths between $s$ and $t$ in $G$. The distance between vertices $s$ and $t$ in $G$ is the length of a shortest path between $s$ and $t$ in $G$. If no such path exists, the distance is defined as infinity. Note that the shortest path between a pair of vertices need not be unique, but the distance between them is unique.

• A subgraph of $G$ is a graph $G' = (V', E')$ such that $V' \subseteq V$ and $E' \subseteq E$. A vertex-induced subgraph on vertex set $V' \subseteq V$ is the maximal subgraph with the vertex set $V'$.

• A graph $G$ is connected if there is a path between any pair of vertices in $G$. A connected component $C$ in $G$ is a maximal connected subgraph of $G$.