8

You are asking for the minimum weight fundamental cycle basis (in an unweighted graph). I think the standard reference for its NP-hardness is: Deo, Narsingh; Prabhu, G. M.; Krishnamoorthy, M. S. (1982), "Algorithms for generating fundamental cycles in a graph", ACM Transactions on Mathematical Software, 8 (1): 26–42, doi:10.1145/355984.355988.


4

Yes. More generally, any spanning tree can be reached from any arbitrarily-chosen MST by a sequence of single-edge replacement operations that never decrease the weight. When such a sequence is used to reach another MST, it can also never increase the weight, because then it would have to decrease it at some other step. See e.g. H.N. Gabow, Two Algorithms ...


1

Leaving aside the trivial case (graphs which only have one $r$-arborescence), this won't be possible. Suppose $(V,E)$ is an $r$-arborescence of $(V,A)$. Then $E$ contains some (nonzero) number of arcs $(r,s_1),\ldots,(r,s_k)$ out of the root (otherwise we are in a trivial case). Now if $(V,F)$ is another arborescence, then either $F$ also contains some $(r,...


1

This answer addresses the NP-hardness of the SPANNING SYMMETRIC HYPERFOREST ROOT SET (SSHRS) problem (given an undirected hypergraph $G$ and a number $k$, is there a spanning hyperforest with root set of size at most $k$ in the symmetric directed hypergraph $D_G$). We prove that this problem is hard by reduction from the MAXIMUM UNIQUELY RESTRICTED ...


Only top voted, non community-wiki answers of a minimum length are eligible