Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,497
questions
0
votes
1
answer
16
views
How to find a crticial edge in a flow network?
The complete question is as follows:
An edge of a flow network is called critical if decreasing the
capacity of this edge results in a decrease in the maximum flow. Give
an efficient algorithm that ...
- 101
0
votes
1
answer
19
views
Algorithms for finding closest graph node within set of nodes
Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$?
Furthermore, say we are doing many ...
1
vote
1
answer
42
views
Data structure and optimal algorithm for modeling reachable outputs given a set of inputs
Given the following:
A set of input types $I$ = {a, b, d, ...}
A set of functions $F$ (With associated costs, and possibly identical signatures) = {($c_1$, a -> d), ($c_2$, (a,b) -> e), ($c_3$, ...
- 113
0
votes
0
answers
33
views
Longest shortest path between two classes of nodes
(larger context at the end)
My view of the problem
I have an undirected graph whose nodes can be categorized into three classes depending on some metadata (I have a function that can tell me the class ...
- 101
-1
votes
1
answer
14
views
Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?
I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.
- 1
1
vote
1
answer
36
views
What algorithm will visit each node in a graph a number of times equal to the number of paths to that node from the root?
First Few Iterations of the Algorithm
We have an algorithm in which a squirrel visits the nodes of a directed graph.
Our graph has two colors of edges: black and white.
Initially, the graph has black ...
- 139
3
votes
1
answer
33
views
Algorithm for maximum non-crossing edge set in bipartite graph with a fixed permutation
I'm trying to identify an algorithm to solve this computational problem
Input:
Bipartite graph (V, W, E), with E ⊆ V×W
A fixed ...
- 53
-1
votes
1
answer
28
views
Does a minimum spanning tree necessarily provide the lowest cost path between any 2 nodes?
If I'm given a minimum spanning tree, my understanding is that it is a structure that connects all nodes to each other through some path, and that the overall weight of the tree is smallest. However, ...
- 125
0
votes
0
answers
61
views
Using topological sort to find inconsistencies represented by cycles in directed graphs
Consider the following scenario.
Let $x_1,...,x_n$ be a group of cars that all drive from some point A to some point B. Each car starts driving in index order. i.e. $x_1$ starts driving strictly ...
2
votes
0
answers
54
views
Playing with boxes: NP-hard? [Graph Theory]
You are playing with boxes on a $K_{1, n}$-$\textbf{subdivision}$ graph $G:=(V, E)$ whose number of vertices is odd, i.e., $|V| \equiv 1$ (mod $2$) with a given central point $C$ such that $\forall v \...
- 121
2
votes
1
answer
22
views
Fast algorithm for Graph Edit Distance to vertex-labeled Path Graph
Let $G$ be a vertex-labeled directed graph with unique labels $L$. Let $G_P$ be a path graph with the same vertex labels and the same number of vertices as $G$.
I know that in the general case ...
- 23
1
vote
1
answer
19
views
Finding articulation points
I have learnt about both articulation points and bridges and I have understood the algorithm used to find the number of bridges in O(n) time which is Tarjan's algorithm. But now, can I simply say that ...
- 127
0
votes
1
answer
42
views
Does order of elements in a set matter in Dijkstra's Algorithm?
When we use a set for doing Dijkstra's Algorithm, we use a pair of {distance,node} which we insert in a set. Most of the articles say that the first element of pair should be the distance , else we ...
1
vote
1
answer
30
views
Find the placement of gates on 2D points that minimizes the total distance of all paths to be made
Suppose we have a 6 vertices graph. We also have 6 gates. Each gate is attributed a path.
For example,
Gate 'A' will have to go to 'B'- 'C' - 'D' and 'E'
Gate 'B' will have to go to 'D'
Gate 'C' will ...
- 113
2
votes
0
answers
39
views
An inverse problem of lexicographic product of graphs
In graph theory, the lexicographic product or (graph composition) $G ∙ H$ of graphs $G$ and $H$ is a graph such that
the vertex set of $G ∙ H$ is the cartesian product $V(G) × V(H)$;
and any two ...
- 121
1
vote
1
answer
28
views
Max flow bottleneck approach flow after k iterations
This is a question from a previous exam in Graph theory and algorithms, the correct answer is E but I don't understand why.
Given a network flow $(G,c)$ over graph $G(V,E) $.
Assume we run Edmonds-...
- 159
-1
votes
0
answers
42
views
Minimum cost to selected rooms among N rooms with given costs to trap rats running along k known paths
I am asked the following problem in interview so source of the problem is unknown.
Students are trying to trap rat in a hostel with N rooms. Students are aware of K unique paths to these room which ...
1
vote
1
answer
88
views
Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?
Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?
Given an undirected graph ...
- 395
1
vote
1
answer
19
views
What is the time complexity of the EMST problem in 3D space
We have an unstructured cloud of $N$ points in 3D space. What is known about the complexity of building the Euclidean Minimum Spanning Tree of the points ?
The tree is made of $N-1$ edges and can be ...
- 4,518
4
votes
1
answer
84
views
Computing biconnected components
My question relates to Problem 22.-2 in Introduction to Algorithms 3rd edition.
There biconnected components are defined as maximal sets of edges such that any two edges in the set lie on a common ...
- 155
0
votes
0
answers
27
views
Computational Complexity theory - Confusion about solving by reduction an NPC problem
I can't seem to grasp the term of reduction that well.
To explain I will take an example the problem of $$\sqrt{k} - clique $$ such that $$ k \leq \sqrt{V}$$
Solving by reduction with normal k-clique ...
2
votes
0
answers
19
views
Is there a difference between realization and embedding of a graph?
Given a geometric graph (interval, circular arc, disk, etc.), is there a difference between the realization of that graph and the embedding of that graph?
- 1,425
3
votes
1
answer
64
views
Efficiently determine which nodes should leave a graph while maintaining connectedness
Suppose I have a graph with node weights, where a weight is either -1 or a positive integer. For example:
If a node has weight -1, it is "happy", and cannot be kicked out of the graph.
If a ...
- 133
1
vote
1
answer
174
views
Optimal path problem with constraint of minimal weight
Given an undirected weighted graph $G$ and two vertices $s, t$. We want to find a path $P$ from $s$ to $t$ that minimizes the following objective function $L$
$$L(P) = max(len(P), max\{c(e) \mid e \in ...
- 294
3
votes
0
answers
49
views
Minimize edge count in directed graph, allowing auxiliary nodes
Suppose I have a directed acyclic graph $G$. I want to find a graph $H$ containing the nodes of $G$ (and potentially more) which minimizes the number of edges in the graph, without changing the ...
- 12.4k
0
votes
0
answers
37
views
Definition of NP within an implementation of deterministic TMs
I am currently writing a mathematical definition for the deterministic Turing Machine so I can make use of it in one of my papers.
(below, I will use the term "tuple" as a synonym for "...
- 61
1
vote
0
answers
22
views
Dominators when node not reachable
For the definition of domination [Wikipedia],
a node $d$ of a control-flow graph dominates a node $n$ if every path from the entry node to $n$ must go through $d$.
If node $n$ is not reachable from ...
- 11
-1
votes
1
answer
25
views
weighted graph separation algorithm proof
I have a graph G (G=(V,E)), where each edge has a non negative weight to it.
My problem is to find a subset S (it doesn't have to exist) of nodes such the sum of all the weights of the edges that ...
0
votes
2
answers
64
views
Calculate shortest cycle that contains node $s$
Let $ G(V,E,w)$ be a graph with no negative weights.
Describe an algorithm that returns the shortest cycle containing a node $ v $.
I came across this algorithm https://courses.engr.illinois.edu/cs374/...
- 159
-1
votes
1
answer
55
views
Converting a Directed Acyclic Graph to a Directed Tree
I'm wondering if anyone can help me with this. Say I have a DAG, I understand that it has no directed cycles, but it can have loops ( "diamonds" ).
My question is, is there a known way to ...
- 1
2
votes
0
answers
46
views
Subgraph Isomorphism with Same Number of Nodes
I am looking at a specific variant of subgraph isomorphism:
Instance A graph $G = (V_G, E_G)$ and a target graph $H = (V_H, E_H)$ such that $|V_G| = |V_H|$.
Question Is there a subgraph $G' = (V'_G, ...
- 21
2
votes
1
answer
68
views
Efficient algorithm to count number of intersections of n sets
I've come across this problem when working on a personal project of mine. I need an efficient algorithm of counting the number of overlaps between all pair combinations of n sets.
Example:
Set a = [...
- 23
1
vote
1
answer
21
views
safe edge theorem proof clarification
I found the following proof for the theorem that states "A light edge that crosses a cut that respects A is safe for A":
See: https://www2.hawaii.edu/~janst/311_f19/Notes/Topic-17.html ...
- 55
0
votes
1
answer
36
views
Recursively deleting spanning forest from graph, how many iterations maximum to get to the empty graph?
As in the question stated, I am interested in the approximation factor of the greedy approach to compute the arboricity of the graph.
My intuition tells me the factor should not be bigger than $2$, ...
- 294
0
votes
0
answers
24
views
The notion of "simulating an edge" in graph algorithms
I am reading a 1996 paper by Panconesi and Srinivasan :(https://www.sciencedirect.com/science/article/abs/pii/S0196677496900176) on distributed network decomposition.
In the analysis of the recurrence ...
- 371
1
vote
2
answers
76
views
Are Control Flow Graphs(CFG) planar?
I notice there are different definitions for CFG(basic block or statement), so let's consider following definition:
Given a program, each statement is a node in CFG, and $(u,v)\in E\iff \text{v is ...
- 93
0
votes
0
answers
11
views
Pursuit-evasion graph problem Top down DP approach?
I'm solving this problem here to learn about pursuit-evasion problems https://leetcode.com/problems/cat-and-mouse/
Basically cat starts at 2, and mouse starts at 1 (goes first) to escape to 0 and they ...
- 111
1
vote
0
answers
25
views
Algorithm to determine maximum difference between different sets of a graph
I saw this image only, and it got me thinking: is this the maximum area difference between a contiguous region and Los Angeles County, such that the population of that region is smaller?
Formally, ...
- 111
0
votes
1
answer
42
views
Transitive Closure of a graph
Assuming we have a DAG, $G = (V, E)$, and we know that we can calculate $G$'s transitive closure in time complexity of $f(|V|, |E|)$, whereas $f$ is monotonic increasing function.
Show that given a ...
- 45
0
votes
0
answers
16
views
How to plot the 'back-to-home-city-path' in TSA without repeating cities
I'm doing an implementation of the traveling salesman problem using genetic algorithms, but I can't get it: If we need to get the best route in a certain set of cities and then go back to the first ...
1
vote
1
answer
30
views
Confuse on proof of theorem 22.9 (White-path theorem) Depth-First search (DFS) on Cormen-Leiserson-Rivest-Stein "Introduction to algorithms" book
I'm reading the DFS section of CLRS-Introduction to Algorithms, and confuse on the $\Leftarrow$ direction of the proof of the white-path theorem of DFS algorithm in this book.
Note that each node u ...
- 11
0
votes
2
answers
57
views
Find a simple path from S to T in a directed graph so that the product of its weights is maximum
I'm looking for an algorithm that finds a simple path from S to T in a directed graph (which might have cycles) so that the product of edge weights in the path is maximum. All the edge weights of the ...
- 23
2
votes
1
answer
29
views
Are the clusters in a cluster graph complete graphs?
I read two definitions of cluster graphs that seem in conflict to me. One is from Koller:
We begin by defining a cluster graph — a data structure that provides a graphical flowchart of
the factor-...
- 135
1
vote
1
answer
34
views
Difference between cost and the heuristic function in A* search
Looking at the image above, thinking in terms of A* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd ...
- 113
0
votes
0
answers
40
views
DAG graph where indegree >= outdegree and indegree = 0 => outdegree <= 1, cover all vertex with min amount of paths
Given a graph $G = (V, E)$ where
G is directed: $ \forall \ e \in E$ : $e$ has a direction.
G is acyclic (no cycles): $ \forall$ path $v_1, \dots , v_n : (v_n, v_1) \not\in E $.
If indegree $\gt0$, ...
- 11
1
vote
2
answers
92
views
Topological sort of minimum costs to finish interdependent tasks
The problem that I'm trying to solve goes like this:
A project is split into tasks. Each task takes a known number of days. Some tasks can be done at any time(lets call these simple tasks), others ...
- 125
2
votes
1
answer
60
views
FPT algorithm for dominating set
An instance of the Dominating Set problem is given by an undirected graph
$G = (V, E)$ and an integer $k$; it is a ‘yes’-instance if there is a subset of vertices $S ⊆ V$
with $|S| ≤ k$ such that for ...
- 379
1
vote
1
answer
68
views
Shortest path in a directed weighted graph
Suppose we have a directed, weighted graph, $G = (V, E, w)$, with non-negative weights. We define the weight of the shortest path different from the original definition.
The weight of a path with at ...
- 45
1
vote
0
answers
30
views
Is There a Term for "Factoring" a Graph by an Equivalence Relation on Nodes?
I have a coding problem I'm running into that feels like it's solved:
Given a (directed) graph, and an equivalence relation on nodes, merge the equivalent nodes in a way that preserves the graph ...
- 111
3
votes
0
answers
31
views
Add an edge to a planar graph and preserving the planarity
I've already posted in the Math StackExchange section, but nobody answered.
I’m wondering if, given a planar graph $G$ And two vertices $v,u$, is there an efficient algorithm to know if adding the ...
- 131