Testing branch-width (Q875941)

A connectivity system is a pair \((Z,f)\) consisting of a finite set \(Z\) and a function \(f\) that maps subsets of \(Z\) to integers such that \(f(X) + f(Y) \geq f(X \cap Y) + f(X \cup Y)\) for all \(X,Y \subseteq Z\), \(f(X) = f(Z \setminus X)\) for all \(X \subseteq Z\) and \(f(\emptyset) = 0\). Let \(Z\) be the set of leaves of a tree \(T\). Then every edge of \(T\) defines a partition \((X,Y)\) of \(Z\). Let \(f(X)\) be the width of this edge, and let the width of \(T\) be the maximum width of an edge of \(T\). Then the branch-width of the connectivity system \((Z,f)\) is the minimum width of a tree of maximum degree \(3\), whose leaves form the set \(Z\). Especially, the branch-width of a graph \(G=(V,E)\) is the branch-width of \((E,f)\) with \(f(X) = \left| \bigcup X \cap \bigcup (E \setminus X) \right|\), the rank-width of \(G\) is the branch-width of \((V,f)\) where \(f(X)\) is the rank of the submatrix of the adjacency matrix of \(G\) defined by columns in \(X\) and rows in \(V \setminus X\), and the carving-width of \(G\) is the branch-width of \((V,f)\) with \(f(X) = | E \setminus (E(G[X]) \cup E(G[V \setminus X]))| \). In time \(O(\gamma n^{8k+6} \log n)\) one can decide whether a connectivity system \((Z,f)\) has branch-width at most \(k\), where \(\gamma\) is the maximum time to compute \(f(X)\) for an \(X \subseteq Z\) and \(n = | Z| \).