Skip to main content
8 votes
Accepted

NP-completeness: sum of "some" paths in a spanning tree

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. (...
David Eppstein's user avatar
4 votes
Accepted

Are equally weighted MSTs closely related?

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 ...
David Eppstein's user avatar
4 votes
Accepted

Connected dominating set in bipartite graphs

Yes, you can, by adapting the argument from this answer. Note that in a bipartite graph $G=(A, B, E)$, the set $B$ is a vertex cover. Lemma 1. Let $G$ be any $n$-vertex connected bipartite graph ...
Neal Young's user avatar
  • 10.8k
2 votes
Accepted

Spanning Tree that Preserves the Number of Branch Vertices

No, not even close. Lemma 1. For any $n\ge 6$, all $n$ vertices in the complete bipartite graph $K_{3,n-3}$ are branch vertices, but each spanning tree of the graph has at most 4 branch vertices. ...
Neal Young's user avatar
  • 10.8k
1 vote
Accepted

Are there digraphs such that any two arborescences are arc-disjoint?

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 ...
Klaus Draeger's user avatar
1 vote

Minimising the root-set of a spanning hyperforest of a hypergraph

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 ...
Mikhail Rudoy's user avatar

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