Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
3,542
questions
0
votes
0answers
18 views
Solving NP problems : analogy between the SAT problem and the shortest path problem
in this 2minute-long video https://www.youtube.com/watch?v=TJ49N6WvT8M (pulled from a free udacity course on algorithms/theoretical computer sciences),
whose purpose is to show how a SAT problem can ...
0
votes
0answers
13 views
What Is The Best Data Structure To Implement Min Priority Queue For Dikstra's Shortest Path Algorithm?
Dikstra's shortest path algorithm uses a min-priority queue for getting the minimum vertex at every iteration. What I want to know is the best data structure to use for this algorithm. From my ...
0
votes
1answer
30 views
Algorithm to split bipartite graph into subgraphs
I'm looking for an algorithm to split a bipartite graph into subgraphs with a specific constraint. I'm not sure if any existing algorithms solve my problem or not.
I have an undirected bipartite ...
1
vote
1answer
26 views
Bridges and Edge Disjoint Paths
So , Basically assume there is a graph $G$ which has no bridges. Is it always true that there exists two edge disjoint paths between any two vertices in the Graph ?
$\text{My Attempt at the Proof}$:-
...
1
vote
2answers
45 views
Grid Puzzle Split Algorithm
I want to generate a random partition of an $N\times N$ grid into $N$ connected groups having $N$ tiles each. How would I do this? Max grid size will be 10x10. Below is an example for a 5x5 grid.
2
votes
1answer
23 views
Stretegy to find the min expected cost on a series graph with edge probability pi and search cost ci
In a series graph, each edge $e_i$ exists with probability $p_i$. And if you want to examine the existence of edge $e_i$, it will cost you $c_i$. I want to test the connectivity between source $s$ and ...
1
vote
0answers
15 views
Why does this BFS solution work for this question about euclidean distance and what's its complexity?
Given a matrix of 1s and 0s where 0 represents houses and 1 represents stores, find the square of minimum Euclidean distance of every house to nearest store. Return it as a vector of vector.
...
0
votes
0answers
20 views
Please explain the algorithm for finding bridges in graph?
let, low[] and disc[] be two 1D arrays
disc[i] stores the discovery time of node[I]
low[i] stores the lowest value between disc[i] and discovery time of children of node[i]
I'm curious that what is ...
0
votes
1answer
21 views
Shortest path form node X to nodes A, B, C in graph
I have an unweighted consistent graph and some node X(the source) and some nodes A, B, C and more. I need to find the shortest paths: X->A, X->B, X->C and ...
1
vote
1answer
14 views
Matching vertex values with sum of edge weights on bipartite graph
Earlier this week I asked this question (please review):
Imagine StackOverflow started offering a subscription where companies
could buy X number of impressions per month for a set of tags.
...
4
votes
1answer
40 views
Count bridging edges in a family of two component forests
I am given a (simple, undirected, connected) graph $G = (V, E)$ and a fixed spanning tree $T$ in this graph. Removing an edge $e\in E(T)$ from $T$ splits it into a spanning forest $F^e$ with two ...
3
votes
1answer
48 views
Efficiently finding “unfounded edges” in a strongly connected graph
While implementing a debugger I've encountered a problem I need to solve concerning dependency graphs. I've simplified it as follows:
Consider a strongly connected graph G = (V,E).
We define a ...
1
vote
1answer
37 views
Finding pairs of vertices which would disconnect a graph
An assignment question asks,
Given a connected, undirected graph $G$, describe an algorithm which can determine if the removal of any pair of vertices would cause $G$ to become disconnected.
There ...
1
vote
1answer
12 views
number of connected induced subgraph in a tree
Let G be a tree-structured graph. A connected induced subgraph is an induced subgraph from G that is connected. (Since the original graph is a tree, any connected induced subgraph is also a tree)
My ...
1
vote
1answer
17 views
Covering maximal number of sets using fixed number of elements
I've encountered some problem which seems general enough to have already been solved.
There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$.
For ...
2
votes
1answer
34 views
Algorithm to find player position in a 2D grid when all you know is the directional steps he has taken
Given the 2D grid shown below, where blue tiles can be visited and island tiles cannot.
Given that we do not know the starting position of a player on this grid.
Given that the player can move 1 ...
2
votes
1answer
16 views
Transitive reduction with vertex additions?
The transitive reduction of a (finite) directed graph is a graph with the same vertex set and reachability relation and a minimum number of edges. However, what if vertex additions are allowed? In ...
3
votes
1answer
56 views
Dijkstra algorithm modification with exactly one relaxation on a directed graph where the weights of outgoing edges of a node are the same
Consider the standard version of Dijkstra's algorithm on directed graphs. Assume it is known that the input digraph $G = (V, E)$ has the following property: for all $v \in V$ the weight of all ...
1
vote
0answers
11 views
Queries on unbounded knapsack
Given $n$ types of items with integer cost $c_{i}$ (there is an unlimited number of items of each type), such that $c_{i} \leq c$ for all $i = 1, 2, \dots, n$, answer (a lot of) queries of form "is ...
5
votes
0answers
34 views
MST with possibly minimal diameter
I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph ...
1
vote
0answers
26 views
Is dijkstra's algorithm fastest possible algorithm for undirected graph with no additional data?
there are many similar questions, but I haven't found direct answer to this question. Consider I have undirected, weighted graph with positive weights, no additional data - hence no heuristic (so it ...
0
votes
0answers
14 views
Connecting islands to the mainland via flood fill
Say I have a large area filled using floodfill:
Where the area in white has been flooded, and all other ares are not connected. I would like to "bridge" these islands to the main area in white, but ...
0
votes
1answer
34 views
Why do we do topological sorting to find shortest or longest path in weighted DAG?
I was wondering why do we need to do the topological sort before performing relaxing of edges.
Wouldn't it'd be better if we do :
if starting vertex is "s"
...
-2
votes
0answers
23 views
No. of distinct path between two vertices of a complete graph
Let $K_n$ denote the complete graph on $n$ vertices, where $n\ge3$, and let $u,v,w$ be three distinct vertices of $K_n$. Determine the number of distinct paths from $u$ to $v$ that do not contain the ...
1
vote
0answers
6 views
Node ordering at contraction hierarchy of biDirectional Dijkstra
I try to understand the node ordering at contraction hierarchy.
To me, ordering and contracting node looks impossible because when contracting a node, then it influence the other node. Therefore, it ...
0
votes
0answers
24 views
Least-weight path in a DAG--why not just use Dijkstra?
I have an assignment to find the least-weight path in a DAG from a source to a target. But the class has already discussed Dijkstra's algorithm, so I'm wondering, why not just use that? It seems too ...
1
vote
0answers
18 views
Maximum edge-disjoint flow
Consider the case where you have two types of flow, let's say "red" flow and "blue" flow. You want to send $k_r$ red flow and $k_b$ blue flow through a DAG $G$ from a source $s$ to a sink $t$ in such ...
1
vote
1answer
63 views
Use 2SAT to show that an implication graphs must have a cycle if it's not satisfiable
Using 2SAT and implication graphs, how could I prove the following properties of implication graphs:
Suppose there is a directed path between literals l1 and l2 in G_Ļ. Then there is also a directed ...
2
votes
1answer
81 views
Find longest path by number of edges, excluding cycles
I need to analyse a directed graph (not a DAG) but I don't know the name of the algorithm I would need to use. The graph has many cycles.
My desired behaviour is: given a graph source and graph sink, ...
0
votes
1answer
35 views
Perfect Matching in Bipartite Graph with mutually exclusive edges
Problem
I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive.
Example
Left vertices: $a,b,c$
Right vertices: $x,y,z$
Edges: $(a,x),(a,y),(b,z),(c,y)...
2
votes
1answer
75 views
Existence of graph spanners
An (unweighted) $k$-spanner of a graph $G$ is a subset of edges $S$ such that the distance between any two vertices of $G$ when using only edges in $S$ is at most $k$ times the distance in graph $G$. ...
2
votes
1answer
25 views
Definition of 2-CNF (a.k.a Krom) formula
In my lecturer's notes, the following definition for a 2-CNF wff is given:
A 2-CNF formula, or Krom formula is a CNF formula F such that every clause has at most two literals.
However, there is ...
1
vote
0answers
22 views
Minimum basis for the nullspace of sparse matrices
Let $A\in\mathbb{F}_2^{m\times n}$ and denote its nullspace as $V=\{x\in\mathbb{F}_2^m:xA=0\}$. The weight of a basis $B=\{b_1,\dots,b_l\}$ for $V$ is the total weight of vectors in the basis, denoted ...
0
votes
1answer
31 views
generate all unlabelled trees up to size n
Who has published an answer to these problems?
An isomorphism signature is a function s on the set of all trees with the property that s(T1) = s(T2) if and only if T1 and T2 are isomorphic. Define ...
-3
votes
0answers
46 views
How to find the fartest distance from a graph?
Pak Dengklek is the best scientist in Singanesia. Right now he was about to try his latest invention, the teleportation machine! He wants to try the machine to move things as far as possible. ...
1
vote
2answers
78 views
Iterative Depth First Search for cycle detection on directed graphs
I found this pseudocode on Wikipedia, and looks very elegant and intuitive:
...
0
votes
1answer
51 views
Efficiently remove nodes from a connected graph
Suppose you have a connected graph and want to remove k nodes such that the result is still connected. How could you do this efficiently?
It occurs to me that you ...
4
votes
2answers
57 views
Prove that if we take all the edges in directed graph that are on some shortest path from 1 to N we will get a DAG
We are given directed weighted graph with edges having strictly positive weight(>0) with possibly some cycles with $N$ nodes and $M$ edges. Let's observe all the shortest paths from $1$ to $N$ in this ...
1
vote
2answers
38 views
Articulation points (or cut vertices), but only subset of vertices need to be connected
I know we can find all articulation points efficiently in a graph using DFS.
But what if not all nodes need to be connected, but instead we have set of node pairs that need to communicate (there is ...
0
votes
1answer
66 views
CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm
I'm trying to better understand Question 24.3-4 From CLRS below:
Professor Gaedel has written a program that he claims implements Dijkstraās algorithm.
The program produces $v.d$ and $v.\pi$ for ...
2
votes
2answers
310 views
Proving correctness and optimality of a greedy algorithm
Here is a (slightly abridged) problem from Kleinberg and Tardos:
Consider a complete balanced binary tree with $n$ leaves where $n$ is a power of two. Each edge $e$ of the tree has an associated ...
3
votes
0answers
37 views
Random linear arrangement of a tree with constrained edge lengths
Let $T$ be a tree with $V$ and edges $E$. Let a linear arrangement $\pi$ of $T$ be a bijective mapping from nodes to integers in the range $\{1, \dots, |V|\}$. You can think of $\pi$ as defining the ...
1
vote
0answers
32 views
small world networks properties
Small-world networks have two properties: clustering coefficient and average node-to-node distance
my questions are: 1- Can a disconnected graph ( which may include multiple connected graphs) hold a ...
2
votes
1answer
61 views
In a DAG, finding the path with the highest score
Given a directed, acyclic graph in which each node has an assigned integer score, what is a fast way of finding the path from a start and end vertex with the highest cumulative score? I thought of a ...
2
votes
1answer
34 views
Number of `m` length walks from a vertice with steps in [1, s]
The problem is stated as the following:
We are given a grid graph $G$ of $N \times N$, represented by a series of strings that describe vertices s.t.
$L$ is the vertice we're interested in
$P$ are ...
23
votes
4answers
4k views
Assuming P = NP, how would one solve the graph coloring problem in polynomial time?
Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time?
Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for ...
3
votes
1answer
38 views
How to best calculate the best possible path with weights
Given a set of nodes, with connections in certain directions (see image), what is the most coins you can collect between the first and last given node. Not all rooms have coins, and we want to output ...
3
votes
1answer
243 views
Construct a DAG from given multiple topological orderings
I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as ...
1
vote
2answers
133 views
Graph with exactly 2 Minimum Spanning Trees
Say that a graph, $G = (V, E)$ has 2 minimum spanning trees (MSTs).
Given this condition stipulated, prove that any cycle formed by all
the edges in both the MSTs (i.e., the union of the edges in ...
2
votes
1answer
45 views
Finding all “basic” cycles in an undirected graph?
Say you have a graph like
a ā b ā c
| | |
e ā f ā g
and you would like to find the cycles c1, {a,b,f,e}, and c2, {b, c, g, f}, but not c3, {a, b, c, g, f, e},...
