Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,455
questions
0
votes
0
answers
29
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
2
votes
1
answer
513
views
Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?
The problem concerns finding shortest paths in graph from a single source to a single destination.
So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A* ...
1
vote
0
answers
28
views
Split Bipartite Graph
I have a bipartite graph $G=(U=\{U_1, U_2,\cdots\}, V=\{V_1, V_2,\cdots\} , E)$ such that edges don't "skip" the $V$ vertices. Meaning, if edge $(U_i, V_j)$ doesn't exist, neither will edges ...
- 143
0
votes
1
answer
73
views
Finding a Hamiltonian Cycle in a directed graph - graph problem
$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like ...
- 29
0
votes
1
answer
39
views
Walk from vertex u to vertex v on complete graph, formula for number of walks of length k
Complete graph with n vertices.
Walk from vertex u to vertex v of length k.
I don't understand how the number of walks between the two of length k is $n^{k-1}$
I've tried this formula on an example ...
- 13
0
votes
0
answers
10
views
Approach for flattening a 3-d cube given cuts
Take a cube. Cut seven of its edges. Consider a graph whose vertices are the centers of the faces of the cube. If two faces share a common edge, then the graph also has an edge connecting the two ...
- 305
-1
votes
0
answers
17
views
How to make this directed graph DFS algorithm search an undirected graph DFS still using adjacency list? [closed]
for example if I pass 5 to the below program, it will print the nodes from the edges in green (see image below), but it won't print the ones in red
...
- 99
0
votes
0
answers
31
views
Special case of single vehicle routing
I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
- 2,851
4
votes
1
answer
74
views
Name and complexity of this problem on bipartite graphs
Let $G=(U, V, E)$ be a biparite graph, with $U$ and $V$ being the two sets of nodes.
I am trying to find the smallest set of nodes $\hat{V} \subseteq V$ such that, for every node $u \in U$, $\hat{V}_u$...
0
votes
0
answers
35
views
Wrong Solution for `Spanning tree with chosen leaves` problem
Suppose that we're given a connected, undirected graph $G = (V, E)$ with
edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find
the lightest spanning tree in which the nodes of $U$ ...
- 1
0
votes
0
answers
23
views
Using an undirected graph to represent an ordered pair?
Set theory depends on a set membership function $\epsilon$ which is a class of ordered pairs. Is it possible to construct the ordered pair from an undirected graph of unordered pairs? Alternatively, ...
- 175
-1
votes
0
answers
14
views
Obtaining min cost perfect matchings from arbitrary matchings [closed]
Let $G = (V, E)$ be an $n$-vertex complete bipartite graph with vertex bipartition $(L, R)$ with
$|L| = |R|$, and an integral cost function $c : E → N$ on the edges.
For a perfect matching $M ⊆ E$, ...
- 331
2
votes
2
answers
311
views
Graph Injective-Homomorphism Problem
Graph Homomorphism is a well-known NP-complete problem. Given graph $G$ and $H$, $G$ is said to be homomorphic to $H$ if there is a mapping $f: V(G) \mapsto V(H)$ such that $(u,v) \in E(G) \implies (f(...
- 129
-2
votes
0
answers
12
views
For given machine assume some strings and evaluate those string will be accepted or not then find out the generalized language
For given machine assume some strings and evaluate those string will be accepted or not then find out the generalized language.
1
vote
0
answers
29
views
What LaTeX library do you use for adding graphs to your papers?
the expression "graphs" in the title refers to graphs as they are thought in computer science:
Let G = (V(G), E(G)) be a graph. It is a tuple with a set of vertices and edges.
- 11
1
vote
1
answer
29
views
Variation of Assignment Problem to maximize amount of agents working
I'm looking at a problem similar to an assignment problem.
There are both agents and tasks. Each agent has a list of tasks they are able to do, and cannot do any task not within that list (note that ...
- 11
0
votes
0
answers
18
views
Looking for an algorithm for multi-path funnel analysis
Suppose we have a dataset with each instance: {uid, action, TS}. The funnel algorithm (e.x https://clickhouse.com/docs/en/sql-reference/aggregate-functions/parametric-functions/#windowfunnel) looks at ...
0
votes
1
answer
81
views
Is there an edge whose removal will extend the shortest path? - graph problem
Given an undirected and unweighted graph $G = (V, E)$ and two of its vertices $s$ and $t$. My task is to find an algorithm that checks if there exists an edge belonging to $E$ such that its removal ...
- 29
-1
votes
0
answers
8
views
lightest path from s to t that goes through vertex v even number of times [duplicate]
Given a directed simple graph G=(V,E) and two vertices s,t and a vertex v∈V−{s,t}, we would like to find the lightest path from s to t, that passes through v even number of times.
for every edge there'...
1
vote
1
answer
19
views
Dual of a graph where the faces are unclear
To get the dual of a planar graph, each of the faces becomes a vertex. And then, two vertices in the dual graph are connected if they share a common face. My question is about planar graphs that have ...
- 305
0
votes
1
answer
44
views
Performant way to find all leaf nodes in a undirected graph
I am trying to find a better way to find all leaf nodes in my undirected waypoint graph.
This is how I define a leaf node:
A leaf node is a node that is never part of a cycle and so has to meet one of ...
- 137
0
votes
1
answer
33
views
Tweaking Floyd-Warshall Algorithm to detect cycles
Cheers, I am trying to solve the problem of minimum length cycle in a graph, and I came across a solution that suggested that I should tweak the Floyd-Warshall algorithm to solve that. It stated that ...
3
votes
1
answer
41
views
Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?
Suppose the optimal color assignment of graph $G$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $\overline{G}$?
A ...
- 170
0
votes
1
answer
103
views
why use bellman-ford instead of Dijstra in RIP routing?
The RIP routing protocol was published in 1988 and uses Bellman-Ford algorithm to calculate shortest path. Also more recent version of RIP (RIPv2 and RIPng) use the same algorithm. The Djikstra ...
- 103
2
votes
0
answers
29
views
How would I prove that the algorithm to find the k-cores graph, produces a maximum size of vertices?
I came across this simple algorithm for finding a k-core of a graph, but every paper I read gives this notion of being maximal without proof, and I'm wondering how I might prove it.
So a k-core of a ...
1
vote
1
answer
35
views
Why Least Cost Airline Fare problem shows optimal substructure when given a certain intermediate stops?
In the Optimal Substructure Wikipedia,
As an example of a problem that is unlikely to exhibit optimal
substructure, consider the problem of finding the cheapest airline
ticket from Buenos Aires to ...
- 173
1
vote
0
answers
68
views
With fixed k>=4, can 3-coloring in a graph of vertex degree at most k be solved in polynomial time?
I couldn't think of a poly-time solution. Moreover, I think that there is a pretty simple Karp-reduction from 3-coloring problem, which is NP-complete.
let's say that graph G is in 3-colloring.
I'll ...
- 11
0
votes
0
answers
24
views
Why is necessary for finding strongly connected components to have a reverse graph?
I'm trying to learn SSC, but it is illogical to me why I need a reverse graph for it. I drew a graph and it's reverse:
So, we have a road from vertice 6 to vertice 5, and we have a road from vertice ...
- 1
2
votes
2
answers
30
views
Matching problem in bipartite network with more than one edge per vertex
I'm interested to know if there is an algorithm to find possible solutions for the matching problem, in a bipartite network where each vertex have maximum number of connections greater than one. For ...
- 123
1
vote
2
answers
33
views
Repeated vertices in cycles (graph theory)
In graph theory, can a cycle contain repeated nodes/vertices not including the first and last ones? If so, can you please give an example?
- 17
-3
votes
1
answer
36
views
Can there be an infinite number of different cycles in a directed graph?
If not, then what is the maximum number of cycles in any graph?
- 17
2
votes
1
answer
37
views
Differences between DFS based cycle detection algorithms
I have seen several variants of DFS algorithms used to check existence of cycles in graphs.
They all have the same structure : do a DFS in the graph. There is a cycle in the graph if and only if there ...
- 131
1
vote
1
answer
54
views
an O(m+n) algorithm to decide whether a graph can be reduced to a single edge with two vertices
Given B and C operations.
B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices.
C-operation: When one edge ...
- 163
1
vote
1
answer
52
views
How to prove non-planar graph can't reduce to single line
Define two operations:
B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices.
C-operation: When one edge connects ...
- 163
2
votes
1
answer
20
views
Consequence of having a randomised algorithm for graph colouring, which shows Yes and No with probability $1$ and $p(n) \sim_{n} 1$
Suppose we have a randomized algorithm that takes a graph G and color k as inputs and provides yes if the graph is k-colorable and no with probability $p(n)$ if it's not k-colorable, where $n$ is the ...
- 170
6
votes
1
answer
363
views
What role is the set, S playing in Dijkstra's algorithm given in the book CLRS?
I'm looking at Dijkstra's algorithm for single source shortest paths in a graph $G$ from a vertex $s$ from Introduction to Algorithms by Cormen et al. The $w$ parameter is the weight function such ...
- 305
2
votes
1
answer
21
views
First-order model checking is not fixed parameter tractable on general graphs
I read that the problem of first-order model checking is believed to be not fixed parameter tractable on general graphs.
Why is this the case? Would be happy about some reference
Thanks in advance!
- 35
0
votes
0
answers
18
views
Efficient way to partition graph maximum and minimum number of cycles
Is there an efficient way to find the minimum and maximum number of edge disjoint cycles an undirected graph can be partitioned into, given that every vertex has an even degree?
3
votes
1
answer
111
views
Is there an efficient algorithm to find GCD of all cycles' lengths in directed multigraph?
I have weighted connected directed graph with cycles which can have multiple edges and loops (edge from vertex back to itself). Weight of each edge is its length (always positive integer). There ...
- 245
0
votes
0
answers
17
views
Common name for "insert unique root" operation?
I had a graph operation come up in a code review, and was wondering if there is a common name for it.
Given a DAG with multiple roots, you can trivially create a graph with a single root by adding one ...
- 799
-3
votes
1
answer
27
views
Which algorithm would be most suitable for finding a minimum subgraph that connects all vertices in a graph and has the smallest weight?
Which algorithm would be most suitable Kruskal, Prims or Steiner tree algorithm ?
- 1
1
vote
1
answer
53
views
Find max of all trees resulting from single edge removal in generic tree in linear time
Given a generic tree with $n$ weighted nodes, there are $n-1$ edges. Removing any of the edges will partition the tree into two distinct trees, hence we can construct $2(n-1)$ possible trees in this ...
0
votes
0
answers
22
views
How to proof This for Maximum Independent Set Problem?
Show that the problem of finding a Maximum Independent Set doesn't have approximation with factor $\Omega(\frac{1}{n^{1-\epsilon}})$ unless P = NP.
2
votes
1
answer
22
views
a generalized job assignment problem
The following problem is from a past algorithms course exam and I'm using it to test my knowledge.
There are m machines and n jobs. Each machine can doing a subset of jobs. Each machine i has a ...
- 1
1
vote
1
answer
30
views
First-order model checking on general graphs is intractable
I read that the first-order model checking problem is intractable on general graphs.
How is this shown? Would be happy about some reference!
Thanks in advance
- 35
2
votes
0
answers
25
views
The Roskind-Tarjan Algorithm
I am going through the paper https://pubsonline.informs.org/doi/abs/10.1287/moor.10.4.701 which is
A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees and the authors are James Roskind and ...
- 53
0
votes
1
answer
52
views
Implementation of Kruskal's algorithm using priority queues
Is there a way to implement Kruskal's algorithm for finding the MST of an undirected graph using priority queues? The standard implementation uses the disjoint set data structure but I was curious if ...
- 53
1
vote
1
answer
23
views
Rank of a graph in matroid theory
I was going through the concept of graphs as matroids and I came upon the rank of a graph. Wikipedia lists it as $n - c$, $n = |V|$, $c =$ # of connected components.
I do understand rank and nullity ...
- 53
0
votes
0
answers
27
views
Can a complex arrangement of diodes do computation?
If I have a bunch of diodes arranged in some complex, directed graph, can I get it to do computation?
I mean will it add voltages and, for example, as I insert voltage sources in-between the diodes? ...
- 125
2
votes
0
answers
18
views
Edmond's theorem for k-disjoint arborescences in digraphs
Recently while studying arborescences in graph theory, I came across Edmond's theorem for $k$ edge-disjoint arborescences in digraphs
if a finite digraph is $k$ edge-connected from a vertex r for ...
- 53