1
$\begingroup$

Given an undirected graph $G=(V,E)$, and vertex $v\in V$ and a number $k\in \mathbb{N}$, find an algorithm to find whether there exists a spanning tree of $G$ in which $v$ satisfies $d(v)=k$

I've narrowed the solution to 3 situations, in $G$: $d(v)<k , \\d(v)=k\\d(v)>k$

When $d(v)<k$, it is clear that there cannot exist a spanning tree of $G$ such that $d(v)=k$, since $d(v)$ was never of value $k$ to begin with.

When $d(v)>k$, we know that we can create a graph $G'$ in which we remove a finite amount of edges $i$ in such a matter that we reduce $d(v)$ to be $k$, and check whether $G'$ is connected or not (we can use BFS), since $d(v)\leq |V|$, the complexity would be $O(|V|\cdot (|V|+|E|))$, however I feel this is extremly inefficient.

For the case where $d(v)=k$ in $G$, I am uncertain on how to proceed.

EDIT: I've managed to update the case where $d(v)>k$ to be in linear time:

if $d(v)>k$, we'll have to remove edges from the graph.

We'll perform $DFS$ on $v$, since $d(v)>k$ there will be back edges, we can (in linear time) count how many back edges are going into(or out of) $v$, if the number of back edges is greater than $m-k$ where $|E|=m$, we can remove $m-k$ back edges from $G$, if the number of back edges is smaller than $m-k$, there cannot be a spanning tree in which $d(v)=k$.

The updated solution to the case was given to me by a colleague, I dont completely understand it yet I am trying to wrap my head around it.

About the case where $d(v)=k$, I am still uncertain.

$\endgroup$
11
  • 1
    $\begingroup$ Why can't you just run an MST algorithm in case $d(v) = k$? Or better yet if you do not need an MST, a BFS starting from $v$ to see if the graph is connected which would imply that there is a tree that spans all vertices, hence an MST algorithm will find one that minimizes the total weight. $\endgroup$
    – Russel
    Commented Jan 14, 2023 at 13:31
  • $\begingroup$ The question asks for a linear time complexity in all cases, I've edited my answer for the case in which $d(v)>k$ with a linear solution. MST finding algorithms run in $O(nlogn)$ $\endgroup$
    – Aishgadol
    Commented Jan 14, 2023 at 13:35
  • $\begingroup$ Please see my edited comment. And maybe include that running time requirement in the question $\endgroup$
    – Russel
    Commented Jan 14, 2023 at 13:36
  • $\begingroup$ @Russel Please note that this problem doesnt necessarily discuss MSTs, but spanning trees in general. $\endgroup$
    – Aishgadol
    Commented Jan 14, 2023 at 13:42
  • $\begingroup$ So I think running BFS starting from $v$ and checking if all vertices are reachable will suffice when the degree of $v$ in $G$ is $k$, since a BFS will force all edges of $v$ to be part of the BFS tree rooted at $v$, which will be a spanning tree if all vertices will be reached from $v$ $\endgroup$
    – Russel
    Commented Jan 14, 2023 at 13:45

1 Answer 1

5
$\begingroup$

First, verify that $G$ is indeed connected, otherwise say no.

Second, if $G - v$ (the graph after deleting $v$) has more than $k$ components, we can say no.

Pick any $k$ neighbors of $v$ with the restriction that you pick at least one from each component of $G-v$ and mark them. The edges from $v$ to these marked vertices are in the spanning tree.

For each connected component $C$ of $G-v$, pick a marked vertex $x$. Run a DFS from $x$ and pick the edges you traverse as long as you see an unvisited vertex. If you meet a visited vertex, you ignore the edge. If you meet a marked vertex, simply do not put that edge into the spanning tree.

$\endgroup$
2
  • $\begingroup$ The use of components here is a nice touch. What's the idea for the last part? Wouldn't the component be enough? $\endgroup$
    – Russel
    Commented Jan 15, 2023 at 2:36
  • $\begingroup$ My apologies, that was not very well explained. When you run DFS, simply do not add the edges to the marked vertices (except the starting point) to the spanning tree. $\endgroup$
    – Pål GD
    Commented Jan 15, 2023 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.