Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,832
questions
0
votes
0
answers
34
views
The second shortest path on a directed graph
The question asks to write an algorithm using Dijkstra's algorithm with time complexity of
$\Theta(|E| \log |V|)$ that find the second shortest path between s∈V and t∈V.
The farthest I managed to get ...
- 1
1
vote
0
answers
44
views
Borůvka's step in linear time
I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step.
My problem is with the removal of duplicate edges between merged ...
- 12.5k
0
votes
0
answers
36
views
Complexity of topological sorting with a special restriction
Let $G = (V, E)$ be a connected DAG (representing a circuit) with every vertex may be one of the following three types:
Input variable, with in-degree $0$ and out-degree $\geqslant 1$.
A gate, with ...
- 13
-2
votes
2
answers
174
views
Could this novel algorithm be qualified to be published in Nature or Science
I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
0
votes
0
answers
10
views
O(n^3) Algorithm for Maximum Weighted Cycle Cover for Undirected Complete Graph with Triangle Inequality
I have been trying to implement an approximation algorithm for the max traveling salesman problem with triangle inequality, and each paper I've read references the step of finding the max cycle cover ...
-3
votes
0
answers
42
views
shortest path question
suppose directed graph $G = (V,E)$
Let $C$ be a cycle with weight 0. The weight of the minimum cycle in the graph is also 0. Prove that for every pair of nodes $u,v$ $(u \neq v)$ in the cycle $C$:
$\...
- 1
1
vote
2
answers
88
views
NP-hardness of modified distance-colouring of graphs
Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\{0,1,2,3,...,c-1\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must ...
- 11
0
votes
1
answer
25
views
Fully Connected Graph to Lattice
I am looking for algorithms (or at least something similar to the problem definition):
Given a fully-connected weighted graph $G$ with $n$ nodes, find a subset $S$ of edges that form a square lattice ...
- 113
1
vote
1
answer
29
views
Independent sets generation in a graph
Is there an algorithm that, given an undirected graph and one independent set IS1, finds an other independent set IS2 by adding and deleting vertices from the first IS1?
- 11
1
vote
1
answer
23
views
Algorithm for constructing a numbering reflecting the order of activities
I'm following a book about graphs and they introduce a concept called 'activity network'. In an activity network, each vertex represents an activity in a project (like building a house for example) ...
- 219
0
votes
1
answer
15
views
Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes
I am having trouble with a problem where I am given an adjacency list and a list of the nodes that must be visited exactly once to connect two nodes. What is the most efficient way of doing this? This ...
0
votes
1
answer
15
views
Graph Algorithms (SSSP vs MST)
I am currently facing a question "Can a graph with a unique MST product a different spanning graph using Dijkstra vs using Prim's algorithm?" The answer is false and I am struggling to ...
0
votes
1
answer
24
views
Can Dijkstra's algorithm be used this way?
Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose ...
1
vote
0
answers
16
views
epsilon-optimality in cycle-cancelling for min cost flow
I'm learning about the (min-mean) cycle-cancelling alg for min-cost flow in Ahuja, Magnanti, and Orlan's Network Flows book (Chapters 9 and 10). When talking about the alg, they prove this fact ...
- 21
-2
votes
0
answers
33
views
Prove vertex limit for cluster editing kernel
A graph G is a cluster graph if every connected component of G is a clique. In the Cluster Editing problem, we are given as input a graph G and an integer k, and the objective is to check whether one ...
0
votes
1
answer
47
views
How to modify Dijkstra's algorithm to model the path of an electric car?
I know that Dijkstra's algorithm is used to find the shortest path between nodes in a weighted graph. And I know that this can be used to model road networks.
Somebody online asked (but nobody ...
0
votes
1
answer
85
views
Why not n^2 comparisons in the Alien Dictionary problem on leetcode?
Here's the problem statement (as given on GeeksForGeeks website):
Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of ...
2
votes
2
answers
108
views
A $O(|E||V|)$ algorithm to determine if a graph is singly connected?
In exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition), the authors provide the following problem:
A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ ...
- 67
0
votes
0
answers
13
views
Edge connectivity using flow network
Find an algorithm for edge connectivity in undirected graph using flow networks. Try to use $O(m)$ edges.
So basically the flow network should be used as a "helper function" and the graph ...
- 21
0
votes
1
answer
52
views
Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time
In a graph with N nodes, where each node represents a house and is labeled from 0 to N-1, an ...
- 135
1
vote
1
answer
44
views
Expected maximum matching size in a random bipartite graphs
What is the expected maximum matching size of a bipartite graph $(A\cup B, V)$ where $\lvert A\rvert = n$ and $\lvert B\rvert = n$ and the probability of a edge existing between $A$ and $B$ is a fixed ...
- 25
2
votes
1
answer
56
views
Dinitz’ algorithm in simple unit-capacity networks
I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time.
This is what is written on the slides ...
0
votes
1
answer
24
views
Can a trie or DAWG loop?
I am looking at DAWGs, which are compressed tries, like this:
It is an acyclic graph though, and I'm wondering if you are allowed to create loops or cycles in such a data structure.
For example, I am ...
- 2,163
0
votes
0
answers
61
views
In Johnson's algorithm for enumerating elementary circuits in a directed graph, why do B-lists have a different structure than the adjacency list?
I have a question on the implementation of the Johnson's algorithm in C that is actually at the interface of theory and practice.
Link to Johnson's paper
I already implemented this algorithm in R ...
3
votes
1
answer
31
views
Increasing families of expander graphs
I would like to know if there is any research dealing with the problem of constructing an increasing family of expander graphs.
The goal is to find a family of expander graphs $(G_i)_{i \in \mathbb{N}}...
- 31
0
votes
0
answers
28
views
Lookup Using Path Matrix in Floyd Warshall Algorithm
How is the path matrix created by the Floyd Warshall algorithm used for path lookup?
The 2 images show the graph (b) and the path matrix (c). Both are taken from the book: Foundations of Algorithms by ...
1
vote
1
answer
77
views
Number of decycling sets in a 3-regular planar graph
Defintitions:
A graph is said to be r-regular if every of its vertex has a degree $r$. A graph is planar if it can be drawn in a plane without any of its edges intersecting each other except at their ...
- 73
0
votes
1
answer
44
views
Reductions to perfect matching
Can we reduce any well-known problems to deciding whether a (possibly non-bipartite) graph $G$ has a perfect matching? I'm particularly interested in finding a reduction from deciding whether a ...
- 1
7
votes
2
answers
1k
views
Algorithmic Complexity of Recognizing Claw-Free Graphs
Let $H=\left(V_H, E_H\right)$ and $G=(V, E)$ be graphs. A subgraph isomorphism from $H$ to $G$ is a function $f: V_H \rightarrow V$ such that if $(u, v) \in E_H$, then $(f(u), f(v)) \in E$. $f$ is an ...
- 303
1
vote
1
answer
22
views
Linked Lists, Ordered Pairs?
I would like to model linked lists using set theory similar to that in Scheme and LISP.
There is a set theoretic definition of the ordered pair:
$p = \{\{a, 1\}, \{b, 2\}\}$
My question is how does ...
- 111
1
vote
1
answer
14
views
How to avoid global delaunay check in conforming triangulation?
I implemented a conforming (i.e. it creates Steiner points using Ruppert's algorithm) delaunay triangulator, which is working, but there is one step I am doing that I straight up don't understand and ...
- 331
3
votes
1
answer
44
views
Fast way to know if deleting an edge will disconnect a fully connected undirected graph
Given a fully connected undirected graph, is there a quick way for me to know if the graph will remain fully connected if I delete a given edge from the graph?
Quick = O(lg V) or something like that. ...
- 209
1
vote
1
answer
45
views
GNI public coin interactive proof: why randomize y?
I've read this scribe that provides a public coin interactive proof for graph non-isomorphism.
In the proof, the verifier samples both a pairwise-independent hash function and a target $y$. Then it ...
- 11
1
vote
0
answers
26
views
How to actually implement ruppert's algorithm?
I have been scouting the internet for resource son how to properly implement Ruppert's algorithm and what I ahve found is always lacking in details. The best resources I have so far are these 2:
...
- 331
2
votes
1
answer
245
views
An efficient way to find a pair of unrelated edges
I'm writing a program which uses an undirected graph to represent certain social connections, and I'm trying to check whether or not it's contains a specific induced subgraph.
Given a dense an ...
3
votes
0
answers
27
views
Why is there no self-stabilizing determinsitic algorithm for vertex coloring in general graphs?
This question considers the design of a deterministic self-stabilizing algorithm for vertex coloring in uniform anonymous networks. Uniform anonymous networks do not have distinguished nodes and all ...
- 171
1
vote
2
answers
71
views
Time complexity of using BFS to find shortest path within k stops
I'm referencing this Leetcode question: https://leetcode.com/problems/cheapest-flights-within-k-stops/solution/, which asks you to find the length of the shortest path from source to dest using less ...
- 11
0
votes
0
answers
31
views
Probabilistic Pathfinding
Here an interesting graph problem I've recently saw:
After a heist in New York City, a group must reach Miami within a set timeframe to catch an escape boat. Their vehicle's GPS shows U.S. routes with ...
- 1
0
votes
0
answers
11
views
Constructing a sparse subgraph of original weighted undirected graph with approximation algorithm
In Kruskal's algorithm, we sort edges from least weight to greatest weight and add the edge if and only if both endpoints are in different connected components in current iteration.
Now the question ...
0
votes
0
answers
27
views
Is there a fully dynamic algorithm to find a minimum arborescence (like Chu–Liu/Edmonds' algorithm)?
Given a weighted directed graph with nonnegative edge weights and a vertex $r$ designated as root, at each step I will do one of the following:
Add a new edge to the graph.
Remove an edge from the ...
- 101
0
votes
0
answers
26
views
A* (A-star) search algorithm including closest distance from a node to an obstacle in heuristic and step cost
I want to include the distance of a node to the closest obstacle in the cost function, so that the path length is not only minimal, but also not near obstacles.
We know that:
Dijkstra's algorithm uses ...
- 1
1
vote
1
answer
39
views
Efficient intersection of multiple paths in a tree
Consider a graph tree $T$, where we are given $k > 1$ unique pairs of nodes $\{u_1,v_1\}\dots \{u_k,v_k\}$. Let $P_{i}$ denote the unique path on $T$ between $u_i$ and $v_i$. Then, my problem is ...
- 13
1
vote
1
answer
54
views
Chordal graphs - what are the use cases?
I'm taking a course in graph algorithms. I've just implemented recognition of chordal graphs for an assignment.
I'm wondering: what are the use cases for chordal graphs?
In other words, what are the ...
- 13
1
vote
1
answer
113
views
Finding the Largest Partition of Non-Connected Nodes in a Graph in polynomial time
I have a graph, and I want to determine the largest possible set (or partition) of nodes such that no two nodes within this set have an edge between them. I am looking for an efficient algorithm to ...
- 83
1
vote
0
answers
84
views
complexity of graph matching with order constraint
Given a graph with $n$ vertices and $m$ edges, $m \le {n \choose 2}$, we index the vertices from 1 to $n$, and denote every edge by $(l,r)$ where $1\le l < r \le n$.
Find the maximum $k$ such that ...
- 11
1
vote
1
answer
46
views
Searching for a Connected Graph with Vertex Count $n$ and Path Lengths Less Than $k$
Question:
I'm looking for a type of connected graph where the number of vertices is $n$ and every pair of vertices is connected by a path with a length less than $k$, where $k$ is a constant. Are ...
- 318
2
votes
1
answer
51
views
Efficient solution for dominating set with two neighbors instead of one
The dominating set problem asks us to find a set of nodes $S$ such that for a graph $(V, E), \forall v \in V$, $v$ has a neighbor in $S$ or is in $S$ itself.
I'm looking for an algorithm which finds $...
- 23
1
vote
1
answer
31
views
Exponential sized graph 3-coloring is in MIP
I was watching a talk by Anand Natarajan on $\text{NEEXP} \subseteq \text{MIP*}$, and he uses $\text{3-coloring}$ as an example problem for $\text{NEXP} = \text{MIP}$ (timestamp 3:50). He mentioned ...
5
votes
1
answer
973
views
Can a graph problem remain NP-hard when restricted to cycle graphs?
Does anyone have any examples of NP-hard graph problems which stay NP-hard on cycles, or is this class somehow not able to have NP-hard problems?
I found a similar post concerning trees here which ...
- 737
-1
votes
1
answer
49
views
Trying to give a proof about graphs. Having a hard time giving proof for Kruskals algorithm. Can you check my answer?
Question: Let G(V, E) be an undirected connected finite graph with the weight function
w : E → R+. Let T be a minimum spanning tree of G. Prove that there exists a run of
Kruskal’s algorithm that ...
- 19