# Tag Info

3

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

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

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

To see whether a "reduction is correct and well-defined", first look at the definition: what is a reduction? In this case, you require a so-called Karp reduction or a polynomial-time reduction from Edge-Coloring to Vertex-Coloring. In particular, it must hold that (i) the process runs in polynomial time and (ii) an instance $G$ of Edge-Coloring has ...

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

Suppose that no symbol has frequency $0$ (otherwise the claim is false). Consider the tree $T$ built by the standard greedy algorithm to construct the Huffman code. This algorithm maintains a forest $F$ where each node $v$ is associated with a frequency $f_v$. Initially $F$ contains a collection of isolated vertices, one per input symbol (with the ...

1

Yes use induction. You will assume that $G_\pi$ is a forest, and you want to prove that $G_{\pi'}$ is also a forest, where $\pi'$ is $\pi$ after one step of the DFS algorithm. The key point, is that a forest is a graph without cycles. So basically, you want to show that no new cycles where created in the last step. To prove this, you will want to have a ...

1

I think one of an important parts of reduction for languages like Clique and Subset-sum is the integer we have given next to the input. That is $k$ for Clique which tells us which size of the clique we are looking for and $d$ in Subset-sum that tells us the sum of a collection of numbers. I have drawn little pictures for you to see how this works. For ...

1

The reduction from $Clique \leq_P SubsetSum$ is incorrect. Take a graph $G$ with four vertices $(v_1, ..., v_4)$, edges $(v_1, v_2), (v_3, v_4$) and let $d = 4$. Then $A = \{1,1,1,1\}$ (assuming $A$ is a multiset). Clearly there is a subset in $A$ whose sum is 4 but there is no clique of size 4 in $G$. As for the reduction $SubsetSum \leq_P Clique$, your ...

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