5
Here is a dynamic programming algorithm. Given a graph $G = (V, E)$ and two vertices $u, v \in V$. We define the recursive function $C:V\rightarrow \mathbb{N}$, such that $C(w)$ is the number of paths from $w$ to $v$. Note that we are looking for the value of $C(u)$. We set $C(v) = 1$ and $C(w)=0$ for each vertex $w \neq v$ with out-degree equal to zeroo. ...
5
Hint #1:
Hint #2:
3
There is a $\mathcal{O}(nk)$ DP approach.
Call an edge covered if we select a vertex next to it. Root the tree at an arbitrary vertex $r$. Define $DP[i][b][t]$ as the maximum number of edges in the subtree of node $i$ that can be covered by selecting at most $t$ nodes from the subtree. If $b = 0$ we are not allowed to select node $i$, and if $b = 1$ we must ...
3
A conditional lower bound based on max-plus convolution can be shown: Fix $n = 3$. If a $\mathcal{O}(k^{2 - \epsilon})$ algorithm to this problem (with fixed $n$) exists, then MAXCONV could be solved in $\mathcal{O}(n^{2 - \epsilon})$. Max-plus convolution is a reasonable hardness assumption, as it is a much-studied problem for which no $\mathcal{O}(n^{2 - \...
2
Suppose that the candidates are $x_1,\ldots,x_n$ and the target is $T$. I'm assuming all candidates are positive. If $T < 0$ then there are no solutions. If $T = 0$ then the only solution is the empty solution. Otherwise, there are two kinds of solutions:
$x_1$ together with a solution for $T - x_1$ using all candidates.
A solution for $T$ using the ...
1
The function
$$f:\mathbb{N}\rightarrow\{0, 1\}:f(k) =
\begin{cases}
1; &\text{if there is a solution of size $k$,}\\
0; &\text{otherwise}
\end{cases}
$$
is monoton, since if there is no solution of size $k$ then there is no solution of size $k+1$. That means we can binary search the value of $k$ in the interval $[1, |B|]$, and output the greatest $...
1
A simple solution is to use the state $dp(n,2,n)$. Let $dp(i,0,j)$ be the maximum number of edges we can get by using $\leq j$ nodes in the subtree rooted at node $i$, with node $i$ itself not being in the vertex cover. Let $dp(i,1,j)$ be the same, except node $i$ is included in the vertex cover.
The transition itself is not obvious, but it can be done ...
Only top voted, non community-wiki answers of a minimum length are eligible
