All Questions
Tagged with algorithms graphs
1,973
questions
1
vote
1answer
33 views
There are n cities and m possible bidirectional roads and k temple. build roads with minimum cost such that each city has access to at least 1 temple
There are n cities and m possible roads and k temples. The cost of each road is given. Build ...
2
votes
0answers
31 views
Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time
I am stuck with the following exercise:
Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time?
I am not sure that this is possible....
1
vote
1answer
47 views
Algorithm to find shortest distance from source to all other vertices of graph in O(m)?
My question is for (c), as I struggle to find an algorithm that can do this in O(m) time.
2
votes
1answer
75 views
Prove finding a spanning tree with no more than 50 leaves is NP-hard
This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard?
I think it is and I'm trying to ...
0
votes
1answer
26 views
Pure Directed Graph
How can a directed graph be efficiently represented in a purely functional language like Haskell? Could someone suggest relevant materials on this topic? (functional pearls perhaps?) Thanks.
3
votes
0answers
29 views
Cost of finding optimal elimination order in a planar tensor network?
Suppose we are computing a sum over $n$ factors which can be represented as a planar tensor network. What is the complexity of finding an optimal elimination order?
For example, take the following ...
0
votes
0answers
41 views
Finding the shortest path with this algorithm
This is a homework question. We want to find the shortest $s$-$t$ path in an undirected weighted graph $G = (V, E)$ with capacities $c_e$ for each edge and positive weights. Let $S'$ be the set of all ...
0
votes
0answers
12 views
Is it possible to use a random seed in the form of an integer to uniformly sample items from an array in sublinear time?
For example, given an array of reservation IDs:
...
2
votes
1answer
52 views
Restore planar graph from vertex degrees
Suppose you are given a list of vertices (with known positions) and their respective degrees, find any set of non-intersecting edges that satisfies the vertex degrees. Or, in other words, connect the ...
1
vote
1answer
51 views
Why are there here at most $ \vartriangle \cdot E $ paths?
I ran across this proof from the following paper: Finding and Counting Given Length Cycles
But I do not understand the third line.
There are at most $ \vartriangle \cdot E $ such paths and they can ...
0
votes
1answer
41 views
Find nodes at k distance from given source node in an undirected cyclic graph if k<=1e9
I have encountered this problem many times. In an undirected graph, you need to get all the nodes/one node that is k distance away from the given source node (...
0
votes
0answers
17 views
Finding the minimized absolute difference of shortest paths of two different starting vertices
I am relatively new to algorithms and I hoped you can help me with the following question. The question can be summarized as follows:
Given two different starting vertices, A and B, and a destination ...
0
votes
1answer
169 views
True/False: If v is a leaf in every spanning tree resulting from DFS(s), then v is a leaf in every spanning tree resulting from BFS(s)
Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph.
True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning ...
1
vote
0answers
37 views
Exact and approximate agorithms for independent set probem in large graphs
I have a problem which could be stated as follows:
Given an unweighted undirected graph $G=(V, E)$ and positive integer $k \leq |V|$, I need to find a subset of vertices $R \subseteq V$ such that $|R| ...
1
vote
1answer
92 views
Algorithm for finding MST in linear time
Are there any algorithm for finding MST of given graph $G$ in linear time?
I found this paper at this link
But I can't understand it running time is linear or not.
1
vote
1answer
46 views
Find MST after decrease weight of some edges
We are given an undirected weighted graph $G=(V,E)$ that contains at most $2n$ edges, as well as an MST of $G$.
If we decrease the weight of exactly $n$ edges, is it possible to compute an MST of $G$ ...
1
vote
0answers
26 views
Linear programming and network flow
I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, ...
1
vote
0answers
34 views
Finding a path that passes through a given vertex
This is a homework question. Let $G = (V, E)$ be an undirected graph. Let $u, v, w \in V$, find a path from $u$ to $w$ that passes through $v$. I know that I can solve this by running BFS on $u$ and ...
1
vote
0answers
56 views
How to find the shortest path that visits all nodes of a non-complete graph (repeating nodes allowed)?
Let $G$ be a non-complete weighted (only positive weights) undirected connected graph. I'm trying to find a path such that it visits all nodes at least once (repeating nodes is allowed), and it's the ...
1
vote
1answer
30 views
Linear deterministic algorithm for finding spanning tree T with minimal maximum edge
Given an undirected connected graph $G = (V, E)$ with weights $w : $E → $R$$^+$, define for a spanning tree T the value $λ$(T) = $max_e$∈$T${w(e)} (the maximal edge weight in T ).
I need to find a ...
3
votes
1answer
49 views
N points with maximum sum distance
Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100.
To calculate the sum of ...
0
votes
0answers
30 views
Dijkstra algorithm for DAG
Assuming we have a K-Partite DAG (edges are directed from one level to the next) with edge weights either 0, 1 or 2.
We are looking for the shortest path between a node from group 0 to group k-1 (path ...
3
votes
1answer
203 views
Finding the most profitable path
I will be working on a project soon and as I'm clearly not a star (see what I did?) in CS, I'm not sure what to think about this.
To put it simply, the problem is the following:
We want to go from ...
0
votes
0answers
31 views
Similarity between two sequences
I have two sequences whose similarity I want to measure.
Lets say sequence 1 is: abcd and sequence 2 is: badc.
These sequences are always of the same length and they contain exactly the same non-...
1
vote
0answers
20 views
Determining whether DAG is semi-connected
I have been asked to write an algorithm which determine whether a DAG is semi-connected. (Recall that a DAG is semi-connected if for any pair of vertices $x,y$, there is either a path from $x$ to $y$ ...
0
votes
0answers
35 views
An approximation algorithm for partitioning metric completed graph
Given complete metric weighted graph $G=(V,E)$ with $n$ vertices. Are there an algorithm that partition $G$ into to disjoint part $(C_1,C_2)$ that sum of heaviest edge $e\in C_1$ and heaviest edge $e'...
3
votes
1answer
50 views
Weighted maximum match for intervals
Say I have two sets of intervals sorted by time $I_1=[(x_1, y_1),... (x_n, y_n)]$ and $I_2 = [(a_1, b_1)... (a_m, b_m)]$. where $x, y, a, b$ are times in seconds. None of the intervals within $I_1$ ...
1
vote
1answer
30 views
Assigning balls to bins with constraints
Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with ...
0
votes
0answers
147 views
Problems/properties of dynamic graphs with strong lower bounds
I know from [1] that the lower bound for the maximum hitting time of simple random walk on a dynamic graph is $\Omega(2^n)$. Smoothed analysis has been applied to the maximum hitting time [3] and ...
1
vote
1answer
75 views
How should i face the cluster editing problem?
The mentioned problem: Cluster Editing Problem.
I need to code this problem but i can't understand the algorithm behind it, even when i try to search for resources about graphs into the web; can ...
2
votes
1answer
46 views
Upper-bounding the out-going degree of a graph
Given a graph $G=(V,E)$, I'm looking for a way to orient its edges in a way that will bound its out degree.
For example, I can bound the graph's out-degree by $\approx 2\cdot a(G)$, where $a(G)$ is $G$...
2
votes
0answers
45 views
Variation of the gas station problem
Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $u$ the car ...
1
vote
1answer
52 views
Traversing a directed graph with negative weights
Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
1
vote
1answer
40 views
Algorithm to find the path with minimum bending points on a square grid board
Let's suppose we have a square grid board like the one shown in the picture below:
I'm wondering how I can find the path with minimum number of "bending" points (like the ones shown in red) ...
1
vote
1answer
24 views
Given a source and destination, find the path with minimum stress level in a Graph
I faced this problem in a hiring challenge which is now over.
I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't ...
2
votes
1answer
40 views
Proof that any algorithm who builds a spanning tree using Cut and Cycle properties is an MST
The Kleinberg and Tardos Algorithm makes the following claim without proof:
Any algorithm that builds a spanning tree by repeatedly including edges when justified by the Cut Property and deleting ...
5
votes
1answer
134 views
Is classical algorithms a dead research field?
I'm starting my masters in CS soon, and I have to decide on a general research topic.
In my undergraduate studies, I've enjoyed courses regarding data structures and algorithms the most. I'm also an ...
1
vote
1answer
20 views
Lower bound for worst case running time for k-clique problem
A naive algorithm for determining whether a graph with $|V|$ vertices has a clique of size $k$ is to list all $k$-subsets of $V$, and check each one to
see whether it forms a clique. Why is the ...
0
votes
0answers
27 views
Removing and adding edges from spanning tree
Let $T_1$ and $T_2$ be two spanning trees. If $a$ is an edge in $T_1$ that is not in $T_2$, and $b$ is an edge in $T_2$ that is no in $T_1$. I want to prove that $T_1 - \{ a\} + \{ b\}$ is a spanning ...
0
votes
0answers
114 views
Approximating the number of triangles using $\ell_0$ sampling
How do you solve the following question, from this assignment?
Question 2. Consider a stream that consists of the $m$ (distinct) edges of a graph on $n$ nodes. Let $T$ be the number of triangles in ...
0
votes
1answer
103 views
Time-varying edge cost Minimum Spaning Tree
I am having a hard time wrapping my head around the time-varying edge cost of this question :
Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a ...
4
votes
0answers
54 views
Finding the smallest distance between a point and a set of points
I have a GPS dataset that corresponds to a route taken by a vehicle in a day. It consist of a set of coordinates. Then say I have a coordinate and I want to know how close this coordinate is to this ...
1
vote
1answer
49 views
Why we need topological ordering for finding shortest paths
This question is just for discussing algorithms please and not for proposing algorithms. I saw very similar post to mine, but still the answer explains definitions online for topological ordering.
...
3
votes
1answer
43 views
Comparing different versions of Steiner Connected Component Subgraph problem
Problem 1
Let $G(V,E)$ be a directed graph. Let $T \subseteq V$ be a subset of vertices called terminals. Find a subgraph $H$ of $G$, such that $T \subseteq V(H)$, $H$ is a strongly connected ...
1
vote
1answer
42 views
Detecting odd cycle using mod operator and breadth first search algorithm
If we want to detect and odd cycle if an undirected graph $G=<V,E>$. Suppose we run BFS algorithm from CLRS book as follows,
Q: Now my question is suppose we have the following graphs:
The ...
0
votes
0answers
23 views
Prove that $d[v_r] \le d[v_1] +1 ~and~ d[v_i] \le d[v_{i+1}], i=1,2, \cdots, r-1$ on queue $Q$ based on BFS algorithm
Given the following lemma first:
Lemma 1: Let $G=<V,E>$ be a directed or undirected graph, and let $s \in V$ be an arbitrary
vertex. Then, for any edge $(u,v) \in E$,
$$\lambda(s,v) \le \lambda(...
2
votes
0answers
23 views
Efficient concurrent recalculation of a dynamic subset of nodes & their dependencies in a directed acyclic graph
I'm dealing with a directed acyclic graph representing calculation steps. Imagine it as something like a big excel spreadsheet, where each cell is a node in the graph.
A node (cell) can have an ...
0
votes
1answer
56 views
A question about euclidean graph
I have an Euclidean graph $G$, but i should changes the weight of some edge of $G$ to $+\infty$. My problem is, after this change, $G$ remain Euclidean graph or not?
3
votes
2answers
83 views
Check if there is a subset of coordinates where each coordinate in the subset is diagonal to each other
Problem Statement
Given a list of XY coordinates of length N ( e.g. [(1,2),(3,4)] ) check if there is a subset of coordinates of length S where each coordinate of ...
0
votes
0answers
41 views
Longest path in a tree [duplicate]
Given an undirected weighted tree with $n$ vertices, how can I design an algorithm that is $O(n^2)$ and other that is $O(n)$ for finding the longest path between two nodes in the tree (without ...