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,195
questions
1
vote
1answer
15 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
21 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
16 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
27 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 ...
0
votes
1answer
21 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
37 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
171 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
22 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
50 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
76 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
46 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
43 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
21 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
69 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
95 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
36 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
89 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
66 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
40 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
21 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 ...
-1
votes
0answers
61 views
Finding number of shortest paths in Dijkstra's
I am trying to understand Dijkstra's and BFS. Following is what I understood till now
In case of BFS on un-weighted graph, we assume that each node has weight 1 and we traverse level by level, so if ...
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 ...
2
votes
1answer
41 views
Coming up with an adversary strategy for a clique of maximum size
I’m having trouble coming up with a good adversary strategy for this problem:
Input: a graph G
Output: the maximum size of any clique in G
Where the algorithm asks each time, “are vertices x and y ...
1
vote
0answers
11 views
Distributed Graph Consensus to fit a distribution?
$G$ is a strongly connected graph with nodes $V$ and edges $E$. Each node $v_i$ receives a sample $x_i$ from a Gaussian $\mathcal{N}(\mu,\sigma^2)$ with unknown mean and variance.
The objective is for ...
0
votes
2answers
57 views
Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k
I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G.
My algorithm is as follows:
Generate all subgraphs of size k, and check ...
0
votes
0answers
38 views
Graph minimal cycles
Given a graph G, we say C a cycle of G such that however we take two nodes a and b of C, there is NOT a path between a and b in G\edges(C) (that is the graph G less the edges of C).
Is C a minimal ...
0
votes
0answers
19 views
Visit each node in a circular graph with most distance
A simple graph is shown below with 10 nodes. Each node is labeled after a letter in the alphabet. This is basically a circle (J connects to A).
...
0
votes
0answers
30 views
A relaxation-free variant of Dijkstra's shortest path algorithm
I have come up with a relaxation-free variant of Dijkstra's shortest path algorithm, and I would like to see if it's correct. Here is the pseudocode for finding the shortest distance from a node $\...
0
votes
1answer
15 views
how do i remove nodes with their children but keep ones that are already connected?
suppose you have graph G and you want to remove node n and n and all of his children but keep the ones that are connected to other nodes
if i want to delete A it will delete C but not D becase its ...
2
votes
2answers
56 views
Given DAG $G(V,E)$, find $\forall v \in V$ the sum of the weights of vertices that are reachable from the $v$
Given a DAG $G=(V,E)$ and a weights function on the vertices $w:V \to \mathbb{R}$, suggest an algorithm that computes for every $v \in V$ the sum of the weights of vertices that are reachable from it.
...
