The Minimum Branch Vertices problem (or MBV) consists, given an undirected graph, in the search for a spanning tree containing the minimum number of nodes with degree 3 or more, called branching nodes. For instance, on the graph on the right, a optimal solution is drawn with tick edges. It contains only one branching node. As most of the graph covering problems, this problem is applied to the search for an broadcast diffusion tree in a telecommunication network. Particularly, it is applied to optical networks in which dupplicating information is costly.
We study the approximability and the parameterized complexity of the problem. The problem generalizes the hamiltonian path problem, which is a tree with no branching node. As a consequence, no polynomial algorithm exists for this problem. However, if we assume the optimal solution has at least one branching node, the best approximation ratio is between log(n) and n, where n is the number of nodes. We also studied the parameterized complexity with respect to parameters that are small when the graph is sparse: the cyclomatic number and the number of nodes that are neither obviously branching nodes nor obviously non-branching nodes. Finally, all those studies are also used to build interesting and efficient heuristics.