# Tag Info

7

Here is the original statement in CLRS. Assume that we have a connected, undirected graph $G$ with a weight function $w: E\to\Bbb R$, and we wish to find a minimum spanning tree for $G$. It is pretty good to understand "a weight function $w:E\rightarrow \mathbb{R}$" as "an edge has a weight". In fact, that is how I would interpret that notation in a rush ...

6

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not. In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that ...

6

Yes, it is true. Let $w: E(G) \to \mathbb{R}$ be a weight function on the edges of $G$, $s \in V(G)$ be the start vertex. Let $p(v) = \min\{\max\{w(e_1), \ldots, w(e_k)\} \mid e_1, \ldots, e_k \text{ is edges of a path from } s \text{ to } v \}$ i.e. the shortest path between $s$ and $v$. Let's prove by induction on the step of Dijkstra's algorithm that ...

5

It means that each edge has only one weight, which is defined as a real number. So, this definition in compact form excludes many cases, for example: an edge doesn't have weight at all an edge has two (or more) weights an edge has weight as a complex number etc.

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

Let $n := |V| = rk$ be the total number of vertices in the graph. Basically, we are looking for a partition of $V$ into $r$ sets each of size $k$. The total cost will be then the sum of the weights of all edges present in the graph induced by each of these sets. Note that the edges having one end in one of these sets and the other endpoint in another set ...

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

When you get a question about a DAG, the first thing to do is a topological sort. Now, go through all vertexes in order. For each vertex $v$, keep all the possible costs of a path from $s$ to $v$; there will be no more than $3V$ distinct costs. For each edge $e(v,u)$, add to $u$ the costs of $v$ + the weight of $e$.

2

Let's build some recursive function. We start picking any vertex of the tree $T$ and call it $R$ as root. If $R$ was removed, you would get a forest of several sub-trees. Every subtree $T_k$ has a vertex $k$ connected to $R$ in $T$. Now there are 3 types of paths contributing to the sum of cost of paths $N(R)$: $I(R)$, the cost of all inner paths of the ...

2

Your understanding is correct. The key point about TSP is that we are given a distance between every pair of cities. In other words, formally speaking, TSP is the problem of finding a minimum-weight Hamiltonian path/cycle on a weighted complete graph, given the weight function. This doesn't quite correspond to the standard intuition where a salesman is ...

2

You can solve this problem in time $O(|V|+|E|)$ by using dynamic programming. Thirst you order nodes in topological order. Let $v_i$ be the $i$-th node in topological order. Let $E_i$ be the set of edges ending in $v_i$. If $|E_i\setminus D'| = 0$ then: $$d[v_i][0] = 0$$ otherwise:  d[v_i][0] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \not\...

2

Another solution that doesn't require modifying the algorithm (so you can do it with an off-the-shelf implementation): Have two copies of the graph, one called even the other called odd. The idea is that when the total path-length so far is even/odd, you'll be in the even/odd graphs respectively. Then you only need to consider the start/end nodes on the ...

2

Here is a list of algorithms might help you: RAPTOR : Is an algorithm developed by Microsoft and is not graph based. RAPTOR produce pareto optimal unlike CSA. Connection Scan Algorithm: This is a fast algorithm that doesn't need heavy preprocessing. Trip-Based Public Transit Routing: requires more preprocessing compared to CSA and RAPTOR Transfer Patterns ...

2

The question is at least poorly worded, since it does not specify $k \leq n$ or require a simple cycle. So any positive-value arbitrage cycle can be "pumped" to generate a cycle with unbounded positive value. If we add the requirement that the cycle is simple, then finding the simple cycle with the maximum product of the weights is equivalent to finding the ...

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

I'm afraid that this idea does not work (and I actually post this question as homework to my students, the reason being that at first glance it looks sound and complete). Let $G(V, E)$ denote a graph with a cost function $c:e\in E\mapsto Z$, i.e., both positive and negative whole numbers, and no negative cycles. Let us assume there is an edge $e\langle v_i,... 2 This seems to be the "minimum weight orthogonal partition problem", which has been studied among others by Zheng et al. [1]. Computer scientists have also studied it under the name "colourful components", though it sometimes refer to an unweighted variant. The problem is known to be NP-hard, and some approximations exist [2]. There are probably more recent ... 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 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$, ... 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

This answer shows this problem is NP-hard. Further research is needed to determine whether it belongs to APX or it is APX-hard. Let $G$ be a complete directed acyclic graph, i.e., you can name the vertices $1,2,\ldots,n$ and there is an edge $(i,j)$ for all $i<j$. Let $D'=D$, and $k$ is equal to half of the sum of the weights of all vertices. Now there ...

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})$...

1

One way to proceed may be to store for each node a list of parents so $parents[v_i]$ becomes an array of lists. There is also the same array of distance from $s$, $d[v_i]$ initially infinite for all $v_i$ but $s$ ($d[s] = 0$). So like standard version of Dijkstra's algorithm, you maintaint a priority queue $q$ (sorted by $d$). When $v_i$ is depiled from the ...

1

We call an edge superheavy if it is the unique heaviest edge in some cycle. This post shows that an edge $e\in A$ if and only if $e$ is not superheavy. To find all edges that are not superheavy, we can first sort the edges according to their weights from small to large. Then, we remove all edges, re-add them in this order, and track the connected ...

1

This problem is NP-hard. It is called "the minimum-k-union problem". Given a universe $U$ and a family of sets $\mathcal{F}$ over this universe. Are there $k$ distinct sets in $F$ such that the union of all these sets has size at most $d$. Your presentation is the matrix formulation of this problem where each column corresponds to an element in the universe ...

1

A possible solution may be to compute the all pair shortest path matrix and then select the largest value in the matrix. As long as |E|<<|V|^2 or the graph is not dense, your complexity constraint should be satisifed. Johnson's algorithm does it in O(|V|^2 log |V|+|V||E|). Refer to this for a better understanding of time complexity in case of ...

1

We first sort all edges according to their costs from small to large. Say the sorted edges are $e_1,e_2,\ldots,e_{n(n-1)}$, and the corresponding costs are $w_1\le w_2\le\cdots\le w_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e_1,\ldots,e_i$. Now $w_i$ is the minimal tank capacity we want. Sorting ...

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