Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,666
questions
-1
votes
1
answer
68
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
88
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
67
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
40
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
42
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
158
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
35
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
47
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 ...
- 141
1
vote
1
answer
39
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-...
- 212
1
vote
1
answer
94
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 ...
- 411
1
vote
1
answer
26
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 ...
- 7,847
4
votes
1
answer
134
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
30
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
22
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
94
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
255
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
64
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.5k
0
votes
0
answers
38
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
34
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 ...
- 23
-1
votes
1
answer
29
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
180
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/...
- 212
-1
votes
1
answer
114
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 ...
- 9
2
votes
0
answers
52
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
108
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
35
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
0
answers
47
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
96
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 ...
- 103
0
votes
0
answers
30
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
50
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
115
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
75
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
155
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 ...
- 133
2
votes
1
answer
39
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
2
votes
1
answer
275
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 ...
- 123
0
votes
0
answers
50
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
231
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
135
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 ...
- 391
1
vote
1
answer
115
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
31
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
35
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
0
votes
0
answers
20
views
Unique perfect matching in unweighted bipartite graph
Say I have a bipartite graph G with vertex set A and B when |A|=|B|=n and edge set E. Then how do I determine whether the graph has unique matching efficiently. I am not sure but the permanent of ...
- 11
2
votes
0
answers
81
views
Is there an efficient algorithm for calculating shortest path for multiple (source,target) pairs in a graph?
I wonder if there is an algorithm which takes multiple (source,target) pairs and a max_depth parameter and returns all or some of the paths found with those pairs?
Thinking of Dijkstra's algorithm, it ...
- 121
2
votes
1
answer
22
views
Graph Layout Algorithm that optimizes only `x` (not `y`) of nodes?
I have a hierarchical graph structure on a vertical timeline with nodes that have a fixed y coordinate. I am now looking for:
an algorithm (suggestions, any ...
- 131
4
votes
2
answers
899
views
Spanning tree - minimum difference between smallest and largest weight
I am given an undirected, weighted graph $G$, on its base I have to create a spanning tree with such a property that the difference between the largest edge weight and the smallest edge weight is the ...
- 71
0
votes
0
answers
16
views
Is Disjoint Edge Weighted Group Steiner Tree problem equivalent to the regular Steiner Tree problem?
Disjoint Group Steiner Tree (DGST) is the following problem:
Instance: a positive edge-weighted graph $G=(V,E,w)$, a collection of $k$ vertex sets (groups) $S_1,\dots,S_k \subseteq V$, such that $S_i \...
1
vote
0
answers
14
views
Is the predecessors number check in dominance frontiers algorithm necessary?
Here is a dominance frontiers algorithm, mentioned on Wikipedia:
...
- 11
2
votes
1
answer
97
views
Prove there is only one MST in a graph with distinct weights
Let $G = (V, E)$ be an undirected, connected and weighted graph.
Let also $(e_{1},\ldots , e_{|E|})$ be some sort of the edges of $G$.
Let $w, w' \colon E\rightarrow \mathbb{R}$ such that:
$$w(e_{1})&...
- 45
0
votes
0
answers
35
views
Undirected unweighted sub-graph enumeration with threshold on node value
I have an undirected, unweighted graph $G=(V,E)$, and a function $f:V\to [0,1]$ where $[0,1]$ denotes the interval of real numbers from $0$ to $1$ inclusive.
Given an input threshold $t\in [0,1]$, I ...
- 101