Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
4,200
questions
0
votes
0answers
2 views
Can I move across backward edges in a network flow graph
In the problem of maximum flow where we keep augmenting paths until we got no way to reach the sink, we say that we reached the maximum flow which is equal to the minimum $s-t$ cut. Now, Given the ...
2
votes
0answers
31 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
24 views
Meaning of source here
In graph theory, a source of a directed graph $D = (V(D), E(D))$ is a vertex of it whose in-degree is zero.
The book CLRS makes these statements:
Given a graph $G = (V, E)$ and a distinguished source ...
1
vote
0answers
10 views
If we have a graph with 2 nodes, the flow added to one edge will be added as extra capacity to be second edge
If we have the following subgraph of a graph where I will just show 2 nodes please, where the capacity is 7 and 2 respectively:
Now, if we have received flow at node 1 of value 5, then we will have:
...
2
votes
1answer
43 views
Unusual MST variant on bipartite graph
On math.se, Sybren Zwetsloot has asked for help with an unusual optimal subtree problem. Here's my understanding of what he's asking:
We have a weighted bipartite graph on two sets $N$ and $B$, call ...
1
vote
1answer
36 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
35 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
33 views
Input size in graph algorithms
I know from the book by Neapolitan that for any algorithm input size is defined as the number of bits to encode the input. In graph algorithms, the input size is defined as $|V(G)| + |E(G)|$ for the ...
0
votes
0answers
23 views
Terminology for multiply visiting walks of directed graphs
In phrasing an information model for consumption-optimized RDF-like data (full context at 1 for the curious), I'm looking for any established term for X as used here:
Given is a directed rooted graph....
1
vote
1answer
31 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
24 views
Desired outcome calculation in a single player game
I have a game.
In which we have 2 steps.
In the first step we have 3 moves.
In the second step we have 2 moves.
At the end, we would have 6 outcomes as illustrated in the picture.
One (or more) of ...
0
votes
0answers
20 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(...
1
vote
0answers
29 views
Describing the matrix product $BB^T$ of the incidence matrix of a directed graph $G=\left< V,E \right>$
I would like to discuss a solution with you below please.
Describing the matrix product $BB^T$ of the incidence matrix of a directed graph $G=\left< V,E \right>$.
Question: The incidence matrix ...
-1
votes
1answer
26 views
K-Path-Problem is in $P$ or $NPC$
Given an undirected graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of at least length $k$ exists between these two vertices?
How can we solve this problem? I think ...
1
vote
0answers
39 views
Square of a directed graph $G=\left< V, E\right>$
I have this question from CLRS book please.
Question: The square of a directed graph $G=\left< V, E\right>$ is the graph $G=\left< V, E^2\right>$ such that $(u,w) \in E^2 $ iff for some ...
2
votes
1answer
180 views
Topological sort with minimum maximal distance in array
I have a DAG that admits many possible topological sorts. I want to construct one that has the minimum maximum distance between a node and its neighbours in an array storing the nodes in sorted order.
...
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 ...
1
vote
1answer
22 views
Finding maximum clique given, for each edge, union of all cliques containing it
For every edge $e\in E$ of a graph $G=(V,E)$ we know the union $U_{e}$ of the edges of all cliques that contain $e$.
Can we determine, in polynomial time, for a given edge $e_{0}\in E$, the size of ...
0
votes
1answer
53 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
80 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 ...
2
votes
1answer
47 views
Graph cycle basis and odd cycle transversal
I have a graph $G$ and an its fundamental cycle basis $B$.
The question: is an odd cycle transversal of $B$ an odd cycle transversal of $G$?
0
votes
0answers
36 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 ...
0
votes
0answers
17 views
Number of possible boolean functions in a DAG of lookup tables?
A K-input lookup table (K-LUT) can represent any function with K boolean inputs and a single boolean output. The number of possible functions represented by this LUT is $2^{2^K}$ according to this ...
0
votes
0answers
12 views
Mechanism of improved version of Howard's algorithm
For Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems , could anyone advise how the following Howard's algorithm works to compute minimum mean cycle path ?
-1
votes
0answers
19 views
Issue regarding time complexity of Dijkstra's Algorithm
So I tried writing Dijkstra's Algorithm for the following graph. I used Priority Queue so time complexity could be less than V^2 ( where 'V' is the total number of vertices)
My approach ->
...
2
votes
1answer
44 views
Are recursion and a stack equivalent in terms of inplementing DFS?
It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem:
...
0
votes
1answer
21 views
A proof that if f is the heaviest edge in weight from all the other edges in the circle which it is a part of, then f will not participate in any MST
I cant proof that if f is the heaviest edge in weight from all the other edges in the circle which it is a part of, then f will not participate in any Minimum Spanning Tree. please help.
1
vote
1answer
39 views
Why is Independent Set "at least" and Vertex Cover "at most" k
The decision version of the Independent Set and Vertex Cover problems are phrased as:
Given a graph G and a number k, does G contain an independent set of size at least k?
Given a graph G and a ...
0
votes
1answer
23 views
Does the A* algorithm visit every node in an undirected graph when no path to the goal node exists?
When no path to the goalnode exists, does the A*-Algorithm a) visit and b) expand every node in an undirected graph?
I have a monotone heuristic.
Thanks
2
votes
2answers
75 views
Can you use Dijkstra's algorithm to find the maximum cost path?
Suppose you have a DAG and the edges are positively weighted, and you want to find the maximum cost path from any node with no in degree to any node with no out degree.
Is it possible to negate all ...
0
votes
0answers
19 views
Important cuts bound
Important $(X,Y)-cut$ is defined as follows: S is an important $(X,Y)-cut$ if it is inclusion-wise minimal and there is no $(X,Y)-cut$ $S'$ with $|S′|<=|S|$ such that $R′⊃R$ where R,R' are the sets ...
3
votes
1answer
99 views
Maximum number of distinct nodes that can be visited on a single walk
Given a directed graph which may contain cycles, how can I find the maximum number of distinct nodes that can be visited on a single walk?
I have done some research and the most similar-sounding ...
2
votes
1answer
44 views
important separators
Given a graph G and an important (X,Y)-separator S, why is it true that for every edge e in S the set of S\e is an important (X,Y)-separator in G\e
Important (X,Y) cut is defined as follows:
S is an ...
2
votes
1answer
22 views
Building a game tree from a board game
Currently I want to come up with a program able to solve a specific type of board game, where we have a car moving across a randomly generated board, can't move backwards, a gas gauge and a food gauge....
1
vote
0answers
37 views
What if have a algorithm that could generate a NFA of 42 states of any binary string of 2^32 length?
For example, if we have a true algorithm that could generate any NFA of at most 42 states from any binary string of 2^32 length. So, this algorithm can not just recognize the string but just recreate ...
2
votes
1answer
63 views
Longest path between two nodes of a graph
I have a graph $G$ (NOT directed). $SP$ is one of the shortest paths between $a$ and $b$ ($a$ and $b$ are nodes of $G$). $e$ is the edge of $SP$ between the nodes $j$ and $k$ ($j$ is before $k$ if we ...
0
votes
0answers
18 views
Score and bound in Goemans-Williamson algorithm
I am trying to have a deeper understanding of the following implementation of the Goemans-Williamson algorithm for solving the maxcut problem.
...
3
votes
1answer
35 views
How to match two point sets to minimize total distance?
Let's say we have two sets $X = \{x_1, \ldots, x_n\} \subset \mathbb R^d$, $Y =\{y_1,\ldots, y_n\} \subset \mathbb R^d$, how can we find a permutation $\pi$ such that
$$D = \sum_{i=1}^n d(x_i, y_{\pi(...
3
votes
1answer
90 views
Winning move in graph based strategy game
I'm prototyping a deterministic Risk like game. A player can move units from one node to a connected node if he has more than 1 unit the in origin node (must leave 1 unit behind). The player wins if ...
6
votes
5answers
2k views
Example of a graph with negative weighed edges in which Dijkstra's algorithm does work
I was asked to give an example of a graph that has edges with negative weight, but Dijkstra's algorithm will still give us the correct output. It was part of a prove/disprove question. The claim was.. ...
1
vote
1answer
21 views
Complexity of checking graph separation
Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). ...
3
votes
2answers
68 views
Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?
This is my first post on CS Stack Exchange. For some time, I have been studying basic graph algorithms, mainly BFS, DFS, minimum spanning trees and their basic algorithms (Kruskal and Prim). One thing ...
3
votes
1answer
179 views
Disconnected bipartite graph
I was searching whether a bipartite graph can have a vertex with 0 degree. I found this, but the answer there says it is possible. Wouldn't that make a graph tripartite?
Also, if a vertex with zero ...
0
votes
2answers
44 views
Show that for a singly-connected graph the number of edges $E$ must be equal to the number of vertices minus $1$, $E=V-1$
I am reading "Bayesian Reasoning and Machine Learning By David Barber". I am not completely sure how to do question 19 on page 23:
Show that for a connected graph that is singly-connected, ...
2
votes
2answers
35 views
Algorithm that will find the minimum number of steps to get from state $j$ to state $i$
Consider an adjacency matrix $A$ with elements $[A]_{ij}=1$ if one can reach state $i$ from state $j$ in one timestep, and $0$ otherwise. The matrix $[A^k]_{ij}$ represents the number of paths that ...
2
votes
1answer
48 views
Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)
Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: ...
0
votes
3answers
52 views
O(m) time algorithm to check for a strongly connected graph
Given a directed graph G=(V,E) how can I check to see if it is strongly connected i.e.
every vertex is reachable from every other vertex.
what's a good algorithm to check for this that runs in O(m) ...
1
vote
0answers
22 views
Maximum number of edges with k components
Given $N$ vertices and $K$ components what is the maximum number of edges that may exists ? I just got gut instinct that it will be maximum if we take one set with $k-1$ vertices and this will have no ...
3
votes
0answers
39 views
Finding a minimal colored graph containing all given subgraphs
I suspect this is a standard problem, but I was unable to find any literature on it -- my question is, what is the canonical formulation (and ideally solution) to the following:
Given a set $S$ of $K$...
2
votes
0answers
24 views
Best grid/lines to map a group of points
The data I have is a group of points with their position (x,y) known:
It is known that all these red dots are situated exactly on the lines which form a grid system like following:
My object is to ...
