4

Hint: find a topological ordering, and for each vertex $v$, in the topological ordering, compute (the score of) the path with the highest score that ends at $v$.


3

In the worst case any such algorithm will work $\Omega(n^2)$ because your graph can have $\Omega(n^2)$ edges. By the way, are you interested in some particular string metric?


2

Cuts aren't made as part of Kruskal's algorithm; they are used in a proof that it always returns a minimum spanning tree. See e.g. here. But you don't need them to answer the question in the title; instead, take as your graph a triangle with all 3 edges the same weight. Then any order on these edges is allowed and Kruskal's algorithm will return the tree ...


2

This tree traversal sounds similar to a Best-first traversal where the heuristic function is based on your weight function w. This strategy uses a priority queue (e.g. a heap, in this case a max heap). Consider the following algorithm. $G=(V,E)$ is a graph with vertex set $V$ and edge set $E$, $w(j,t)$ is the weight function taking a vertex $j \in V$ and a ...


2

You can solve this in $O(|V| \cdot |E|)$ time. Construct a digraph with vertices of the form $\langle v,b\rangle$ where $v \in V$, $b \in \{0,1\}$, as follows: for each edge $v \stackrel{t}{\to} w$ in your graph, add the edges $\langle v,b \rangle \to \langle w,b + t \bmod 2 \rangle$ for each $b \in \{0,1\}$ to the new graph. Then, for each $v \in V$, ...


2

Construct the edge-vertex incidence matrix: rows correspond to edges, columns to vertices, and there is a $1$ if the edge is incident to the vertex. Add another columns full of $1$'s. You want to know whether there is a subset of the rows summing to the vector $0,\ldots,0,1$ (modulo 2). You can find out using Gaussian elimination, in polynomial time. What ...


2

On the question from title For fixed sink $s \in S$ you can find maximal distance from each vertex to this sink by running dynamic programming on topological order: $$ d(v)= \begin{cases} 0\text{ if } v = s\\ -\infty \text{ if } v \not= s \land v \in S\\ 1 + max_{(v, u) \in E} d(u) \end{cases} $$ You can run this algorithm for every $s \in S$ to get the ...


2

If $G=(V,E)$, with $V=\{v_1,v_2,...,v_n\}$ and weights $\{c_{i,j}, i=1,2,...,n, j=1,2,...,p\}$ is the given graph, then we can construct the strong product (I finally found the name of the operation) $G\boxtimes K_p$ of $G$ and $K_p$, where $K_p$ is the complete graph with $p$ vertices. This is the graph with vertices $\{v_{i,j},i=1,2,...,n, j=1,2,...,p\}$ ...


2

This answer is mostly based on my earlier comments. It is unlikely that there is an algorithm that works in $O(|E|^{2 - \varepsilon})$ time for all graphs. It is still possible that there are faster algorithms for dense graphs ($E = \Omega(V^2)$) or somehow dense graphs ($E = \Theta(V^\alpha)$ for some $\alpha > 1$), but an algorithm that works in $O(|E|^{...


2

It is nice that you have checked your idea on some random samples. To see why your idea work, let us find the simplest but non-trivial case and then take a look at it. For simplicity and WLOG, the weight of a node will be used to denote that node. For example, if $A$ contains a node with weight $42$, that node will be referred to as node 42. The case of $...


2

Let us start by observing that after the $k$-th iteration in the main loop, the Bellman-Ford algorithm has computed minimal weight paths (or the weight of such a path if we do not store the predecessors) of length at most $k$ from the starting vertex $s$ to every other vertex of our graph $G$ (if such paths exists). To prove this, we can use induction: ...


2

The problem can be solved in polynomial time. Here is one algorithm: For each $s \in C$ and each $t \in V \setminus C$ such that $s \neq t$: Find the minimum-cost $(s,t)$-cut. By the max-flow min-cut theorem, this can be done in polynomial time using any maximum flow algorithm. If the cost of this cut is < 2, output it and halt. For each $s_0 \in C$...


2

This problem seems to be NP-hard. A reduction from 3-SAT is left as an exercise, but here is a hint. The empty nodes are free, and then create a color for each literal and its negation. The cost is 1 for each. You can then visit a "clause" for free if and only if one of its literals is selected. Now, the cheapest s-t-path costs $n$ if and only ...


2

An $A$-$B$ path is a path that starts at some $a \in A$ and ends at some $b \in B$.


1

When solving most optimization problems on paths (e. g. shortest, longest path) a cycle is either useless or makes the optimum not exist (allowing infinitely long or short paths). Thus there's generally no point in allowing cycles.


1

Firstly, note that you can reduce $CMCG$ to $MCG$ by setting the value of the node that must be in the set to the sum of all positive weights of all other nodes $+1$ and then applying $MCG$ and retrieving the result set. Thus $CMCG\in NP$. As proved in the paper the $NP$-complete Steiner-Tree problem can be reduced to $CMCG$ meaning that $CMCG$ is $NP$-hard....


1

The claim you are trying to prove by induction is wrong, and I believe this is exactly the source of your confusion. The correct claim is the following: Consider the values of $\text{dist}[\cdot]$ computed at the end of the $k$-th iteration of Bellman-Ford. For any vertex $u$, let $d^{(k)}_u$ be the length of the shortest path from $s$ to $u$ that ...


1

As you highlight in your comments, a reasonable approach is to delete all edges with weight $\ge T$, then compute the connected components of the resulting graph (using any standard algorithm for computing connected components).


1

It seems to me that what you need is an integer mincost flow algorithm. Each matrix entry gets a vertex in the network, with each vertex having arcs to all of the vertices in the next column. The solution flow values indicate how many edges to place between each pair of entries. The flow constraint enforces equal numbers of edges in and out of each entry. ...


1

Many such problems can be solved by modifying the input instance rather than a known algorithm. In your case you can consider your graph as directed and create a new directed graph $G'$ the is split into $2$ "layers", $A$, and $B$. Layer $A$ contains a copy of all the vertices in $V$, layer $B$ contains a copy of all the vertices in $V \setminus X$. Given ...


1

for i in V: weight(i) = 0 for e=(i,j) in E: weight(i) = weight(i) + weight(e) weight(j) = weight(j) + weight(e)


1

Let’s prove this by contradiction. Say $T_a$ is not an MST of $G_a$, that means there is some cheaper MST $T_a^*$. However, if that were true, then by reconnecting $T_a^*$ to $T_b$ we would obtain a tree that spans $G_a$ that has a lower weight than the MST $T$, which is a contradiction.


1

I've got bad news. There's no hope for an algorithm whose worst-case running time is polynomial in the size of the weighted graph (unless P = NP, which seems unlikely). Your problem is as hard as the knapsack problem, which has no polynomial-time algorithm (unless P = NP) when the input is represented in binary. The knapsack problem has a pseudopolynomial ...


1

In each iteration, instead of choosing the node $u$ with smallest $\mathtt{dist}[u]$ in the standard Dijkstra's algorithm, we choose the node $u$ with smallest $\mathtt{dist}[u]+w(u)$, where $w(u)$ is the weight of outgoing edges from $u$. The proof of the correctness of this modified algorithm is almost the same as the one of the standard Dijkstra's ...


1

Suppose there is a cycle $v_1v_2\ldots v_kv_1$ such that every edge in this cycle belongs to some shortest path. Suppose $v_1v_2$ belongs to the shortest path $1\ldots u_1v_1v_2u_2\ldots N$ and $v_2v_3$ belongs to the shortest path $1\ldots u_3v_2v_3u_4\ldots N$, then the weight of the path $v_2v_3u_4\ldots N$ is no greater than that of the path $v_2u_2\...


1

Build the metagraph of strongly connected components. Then execute your idea on the metagraph. Note that once you enter a strongly connected component through any in-edge, you can collect all coins within it and leave through any out-edge out of that component.


1

We can solve the problem in $\mathcal{O}(E \log V)$ by binary search. We can identify the strongly connected components in a graph in linear ($\mathcal{O}(V + E)$) time. Thus we can check if the graph is strongly connected in linear time. If $G(t_{0}) = (V, E(t_{0}))$ is strongly connected, so is $G(t) = (V, E(t))$ for $t \geq t_{0}$. Further, if $G(t_{0})$...


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