# Recent Advances in Positive-Instance Driven Graph Searching +
## 2 Preliminaries: Graphs and Their Decompositions
### Graph Decompositions  
Let \(G=(V,E)\) be an undirected graph. A _tree decomposition_\((T,\iota)\) of \(G\) is a tree \(T\) and a mapping \(\iota\) from the nodes of \(T\) to subsets of \(V\) (which we call _hags_) such that (i) for every \(v\in V\), the set \(\{\,x\mid v\in\iota(x)\,\}\) is non-empty and connected in \(T\), and (ii) for every edge \(\{v,w\}\in E\) there is a node \(y\) in \(T\) with \(\{v,w\}\subseteq\iota(y)\). The _width_ of a tree decomposition is the maximum size of one of its bags minus one. The _treewidth_\(\operatorname{tw}(G)\) is the minimum width over all tree decompositions of \(G\) and its _pathwidth_\(\operatorname{pw}(G)\) is the minimum width over all tree decompositions of \(G\) in which \(T\) is a path. Furthermore, its _treedepth_\(\operatorname{td}(G)\) is the minimum width over all tree decompositions in which \(T\) can be rooted in such a way that for all nodes \(x\), \(y\) of \(T\) we have \(\iota(x)\subsetneq(y)\) if \(y\) is a descendant of \(x\). Finally, its _q-branched treewidth_\(\operatorname{tw}_{q}(G)\) is the minimum width over all tree decompositions of \(G\) that can be rooted such that there are at most \(q\) vertices with more than one descendant on any root-leaf path. Intuitively, the treewidth of a graph measures how similar the graph is \"to being a tree\", in the same sense pathwidth measures the similarity to a path and treedepth the similarity to a star. The \(q\)-branched treewidth allows to study the phase transition between the pathwidth and the treewidth of a graph. Loosely speaking, we can study the trade-off between the _width_ of a decomposition and its \"complexity\". A path decomposition has thehighest width, but it is not \"complex\". In contrast, a tree decomposition has the smallest width but may be arbitrary \"complex\", as it may contain a large number of nodes of high degree. It is well known that we have \(\operatorname{tw}(G)\leq\operatorname{pw}(G)\leq\operatorname{td}(G)\leq \operatorname{tw}(G)\cdot\log_{2}n\)[58] and, by definition, we have \(\operatorname{tw}(G)=\operatorname{tw}_{\infty}(G)\) and \(\operatorname{pw}(G)=\operatorname{tw}_{0}(G)\). Figure 1 shows an example graph with multiple tree decompositions that minimize the various invariants defined above.  
Another important variant of these parameters is _dependency treewidth_, which is used primarily in the context of quantified Boolean formulas [12]. Intuitively, this notion captures the idea that vertices in the graph are dependent on each other and thus need to be processed in a certain order. More formally, for a graph \(G=(V,E)\) and a partial order \(\preccurlyeq\) of \(V\), the dependency treewidth \(\operatorname{dtw}(G)\) is the minimum width of any tree decomposition \((T,t)\) with the following property: Consider the natural partial order \(\leq_{T}\) that \(T\) induces on its nodes, where the root is the smallest elements and the leaves form the maximal elements; define for any \(v\in V\) the node \(F_{v}(T)\) that is the \(\leq_{T}\)-minimal node \(t\) with \(v\in t(t)\) (which is well defined); then define a partial order \(<_{\mathcal{T}}\) on \(V\) such that \(u<_{\mathcal{T}}v\) if, and only if, \(F_{u}(T)\leq_{T}F_{v}(T)\); finally, for all \(u,v\in V\), it must hold that \(F_{u}(T)<_{T}F_{v}(T)\) implies that \(u\preccurlyeq v\) does not hold.  
There are multiple generalizations of treewidth for _digraphs_. We will use the so-called _D-width_, which was introduced by [PERSON] [73] and is based on _D-decompositions_. Such a decomposition is a tuple \((T,t)\) as above, but with the conditions that (i) for every strongly connected subset \(S\subseteq V\) there is at least one \(x\) in \(T\) with \(t(x)\cap S\
eq\emptyset\), and (ii) the subgraph of \(T\) induced by \(\{\{x,y\}\mid t(x)\cap t(y)\cap S\
eq\emptyset\}\) is connected. The _D-width_ of a digraph \(G\), denoted by \(\operatorname{\overline{tw}}\)\((G)\), is the minimal width of any D-decomposition of \(G\).