# Tag Info

2

The statement is false. Take a look at the following graph: In one BFS run, you will get the following tree: That has a distance of $1$ between $u$ and $v$, while in a different run, you could get another tree: Which has a distance of $3$ between $u$ and $v$

2

Regarding the first part. Answer 1 is incorrect. Consider the graph $G = (\{1,2,3,4,5,6\}, \{(1,2), (1,3), (2,3), (3,4), (4, 5), (4,6) \})$. The maximum degree of $G$ is $3$ but the degree of $x_{(3,4)}$ in $\widetilde{G}$ is $4$. Answer 2 is correct. Consider an edge $e=(u,v)$ of $G$. The number edges distinct from $e$ that are incident to $u$ (resp. $v$) ...

2

Let's check these in reverse order. Question B: your reasoning looks good as it demonstrates that both (1) and (2) are not strong enough. The choice (4) is a possible bound, but it's not as tight as it can be. Your example is extremal in a sense that you can't make the degrees any larger, meaning that your bound is, as the question asks, "closest ...

2

This paper seems closely related. The authors study the same problem you define with the exception that edge costs are uniform and do not depend on the distance of the endpoints. This version of the problem is NP-hard. The paper provides references to variants of the problem, some involving costs and lengths. Perhaps you can see if one of the NP-hardness ...

2

1 is wrong. The problem is NP-Complete by an easy reduction $f$ from the clique problem. Let $\langle G,k \rangle$ with $G=(V,E)$ be an instance of (the decision version of) clique. If $k$ is odd then the reduction is the identity function, i.e., $f(\langle G,k \rangle)=\langle G,k \rangle$. Otherwise create a new graph $G=(V', E')$ with $V' = V \cup \{v\}$...

1

Consider the following graph: A possible DFS starting from $a$ visits the vertices in this order: $\langle a, b, c, d \rangle$ producing the cross-edge $(c,b)$. A possible DFS starting from $b$ visits the vertices in this order: $\langle b, a, c, d \rangle$ producing the cross-edge $(d,c)$. A possible DFS starting from $c$ visits the vertices in this order: ...

1

Because you run BFS from $w$, The BFS produce a shortest path tree $\mathcal{T}$ that contain shortest path from $w$ to other vertices. On the other hand the claim say that: any tree $\mathcal{T}$ that produced by BFS, the distance between $u,v$ is $x$, clearly it's not true, because the BFS guarantee the distance between $w$ and $\forall v\in V\setminus w$ ...

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