Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,850
questions
10
votes
2
answers
2k
views
NP-Completeness of a Graph Coloring Problem
Alternative Formulation
I came up with an alternative formulation to the below problem. The alternative formulation is actually a special case of the problem bellow and uses bipartite graphs to ...
- 541
13
votes
1
answer
2k
views
Number of clique in random graphs
There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of ...
- 641
4
votes
1
answer
146
views
Need help understanding this optimization problem on graphs
Has anyone seen this problem before? It's suppose to be NP-complete.
We are given vertices $V_1,\dots ,V_n$ and possible parent sets for each vertex. Each parent set has an associated cost. Let $O$ ...
- 373
2
votes
1
answer
418
views
Could someone suggest me a good introductory book or an article on graph clustering?
For my pet project I need to cluster some data which could be easily represented as graph, so I want to use this as an opportunity to educate myself and play with various algorithms. I'd prefer the ...
- 155
7
votes
1
answer
470
views
In s-t directed graph, how to find many small cuts?
Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in ...
- 123
4
votes
1
answer
305
views
How to prove every well-balanced orientation of an Eulerian graph is Eulerian?
I'm trying to prove that every well-balanced orientation of an Eulerian graph is Eulerian.
I want to prove it by showing that for any two vertices $u$ and $v$, their local arc connectivities coincide,...
Han Xiao
6
votes
1
answer
2k
views
Bellman-Ford variation
I have a "smarter" version of Bellman-Ford here; this version is more clever about choosing the edges to relax.
...
- 61
5
votes
1
answer
82
views
Finding small node sets that can not be avoided on paths from source to sink
In a directed graph with a starting node and an ending node, how to find a small (doesn't have to be smallest. <10 for example) set S of nodes such that every possible path from the starting node ...
- 123
7
votes
2
answers
165
views
Low-degree nodes in sparse graphs
Let $G = (V,E)$ be a graph having $n$ vertices, none of which are isolated, and $n−1$ edges, where $n \geq 2$. Show that $G$ contains at least two vertices of degree one.
I have tried to solve this ...
- 899
12
votes
2
answers
917
views
Reconstructing Graphs from Degree Distribution
Given a degree distribution, how fast can we construct a graph that follows the given degree distribution? A link or algorithm sketch would be good. The algorithm should report a "no" incase no graph ...
- 223
8
votes
0
answers
210
views
Optimizing order of graph reduction to minimize memory usage
Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used.
That is, given ...
- 81
14
votes
4
answers
48k
views
Dijsktra's algorithm applied to travelling salesman problem
I am a novice(total newbie to computational complexity theory) and I have a question.
Lets say we have 'Traveling Salesman Problem' ,will the following application of Dijkstra's Algorithms solve it?
...
Kamaal
6
votes
2
answers
5k
views
Find the minimal number of runs to visit every edge of a directed graph
I am looking for an algorithm to find a minimal traversal of a directed graph of the following type. Two vertices are given, a start vertex and a terminating vertex. The traversal consists of several ...
- 161
22
votes
1
answer
547
views
Approximate minimum-weighted tree decomposition on complete graphs
Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
- 321
5
votes
3
answers
5k
views
Finding the maximum bandwidth along a single path in a network
I am trying to search for an algorithm that can tell me which node has the highest download (or upload) capacity given a weighted directed graph, where weights correspond to individual link bandwidths....
5
votes
1
answer
920
views
Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED
NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really ...
- 53
16
votes
3
answers
1k
views
How to approach Dynamic graph related problems
I asked this question at generic stackoverflow and I was directed here.
It will be great if some one can explain how to approach partial or fully dynamic graph problems in general.
For example:
...
- 161
7
votes
1
answer
234
views
Simple paths with halt in between in directed graphs
I have two problems related to paths in a directed graph. Let $G=(V,E)$ be a directed graph with source $s \in V$ and target $t \in V$. Let $v \in V \setminus \{s,t\}$ be another vertex in $G$.
Find ...
Bin Fu
25
votes
2
answers
3k
views
Is Logical Min-Cut NP-Complete?
Logical Min Cut (LMC) problem definition
Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
- 401
15
votes
1
answer
18k
views
Find the longest path from root to leaf in a tree
I have a tree (in the graph theory sense), such as the following example:
This is a directed tree with one starting node (the root) and many ending nodes (the leaves). Each of the edge has a length ...
- 255
4
votes
1
answer
266
views
Modified Djikstra's algorithm
So, I'm trying to conceptualize something:
Say we have a weighed graph of size N. A and B are nodes on the graph. You want to find the shortest path from A to B, given a few caveats:
movements on ...
- 487
19
votes
2
answers
21k
views
Shortest Path on an Undirected Graph?
So I thought this (though somewhat basic) question belonged here:
Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving ...
- 487
8
votes
1
answer
165
views
Find minimum number 1's so the matrix consist of 1 connected region of 1's
Let $M$ be a $(0, 1)$ matrix. We say two entries are neighbors if they are adjacent horizontal or vertically, and both entries are $1$'s. One wants to find minimum number of $1$'s to add, so every $1$ ...
- 3,023
2
votes
1
answer
5k
views
NP-completeness of a spanning tree problem
I was reviewing some NP-complete problems on this site, and I meet one interesting problem from
NP completeness proof of a spanning tree problem
In this problem, I am interested in the original ...
- 273
9
votes
1
answer
4k
views
Chinese Postman Problem: finding best connections between odd-degree nodes
I am writing a Program, solving the Chinese Postman Problem (also known as route inspection problem) in an undirected draph and currently facing the problem to find the best additional edges to ...
- 571
29
votes
2
answers
6k
views
Where to get graphs to test my search algorithms against?
I am implementing a set of path finding algorithms such as Dijkstra's, Depth First, etc.
At first I used a couple of self made graphs, but now I'd like to take the challenge a bit further and thus I'...
- 600
0
votes
2
answers
4k
views
How to construct the found path in bidirectional search
I am trying to implement bidirectional search in a graph. I am using two breadth first searches from the start node and the goal node. The states that have been checked are stored in two hash tables (...
- 954
22
votes
1
answer
2k
views
How many shortest distances change when adding an edge to a graph?
Let $G=(V,E)$ be some complete, weighted, undirected graph. We construct a second graph $G'=(V, E')$ by adding edges one by one from $E$ to $E'$. We add $\Theta(|V|)$ edges to $G'$ in ...
- 9,036
16
votes
2
answers
7k
views
How to implement AO* algorithm?
I have noticed that different data structures are used when we implement search algorithms. For example, we use queues to implement breadth first search, stacks to implement depth-first search and min-...
- 161
20
votes
1
answer
974
views
Optimal algorithm for finding the girth of a sparse graph?
I wonder how to find the girth of a sparse undirected graph. By sparse I mean $|E|=O(|V|)$. By optimum I mean the lowest time complexity.
I thought about some modification on Tarjan's algorithm for ...
user742
5
votes
3
answers
4k
views
Does spanning tree make sense for DAG?
Why cannot I find any information about spanning tree for DAG ? I must be wrong somewhere.
- 374
11
votes
1
answer
1k
views
Proving that directed graph diagnosis is NP-hard
I have a homework assignment that I've been bashing my head against for some time, and I'd appreciate any hints. It is about choosing a known problem, the NP-completeness of which is proven, and ...
- 113
23
votes
2
answers
7k
views
NP completeness proof of a spanning tree problem
I am looking for some hints in a question asked by my instructor.
So I just figured out this decision problem is $\sf{NP\text{-}complete}$:
In a graph $G$, is there a spanning tree in $G$ that ...
- 333
14
votes
2
answers
8k
views
Proving a binary tree has at most $\lceil n/2 \rceil$ leaves
I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction?
For people who were following in the ...
- 453
7
votes
2
answers
621
views
Is Directed Graph a Graph?
I came across an issue with the definition of a (directed) graph in Sipser's Introduction to the theory of computation, 2nd Ed.
On pp.10, An undirected graph, or simply a graph, is a set of points ...
- 430
19
votes
2
answers
469
views
How many edges can a unipathic graph have?
A unipathic graph is a directed graph such that there is at most one simple path from any one vertex to any other vertex.
Unipathic graphs can have cycles. For example, a doubly linked list (not a ...
12
votes
1
answer
1k
views
Find shortest paths in a weighed unipathic graph
A directed graph is said to be unipathic if for any two vertices $u$ and $v$ in
the graph $G=(V,E)$, there is at most one simple path from $u$ to $v$.
Suppose I am given a unipathic graph $G$ such ...
- 467
1
vote
1
answer
770
views
Improve worst case time of depth first search on Euler graphs
How to improve the worst case scenario for a depth first search on an Euler graph, starting at some point and ending at that same point?
I need to do the whole search but it is not fast enough for ...
- 119
11
votes
3
answers
2k
views
How Do Common Pathfinding Algorithms Compare To Human Process
This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A*) compares to the process humans use in different ...
- 303
6
votes
1
answer
109
views
An indexing function for graphs
Definition from wikipedia:
A graph is an ordered pair $G = (V, E)$ comprising a set $V$ of nodes together with a set $E$ of edges, which are two-element subsets of $V$.
The set of all finite ...
- 1,470
30
votes
1
answer
12k
views
How hard is counting the number of simple paths between two nodes in a directed graph?
There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search).
However it seems that, ...
- 1,379
28
votes
4
answers
2k
views
How to find a superstar in linear time?
Consider directed graphs. We call a node $v$ superstar if and only if no other node can be reached from it, but all other nodes have an edge to $v$. Formally:
$\qquad \displaystyle $v$ \text{ ...
- 72k
43
votes
1
answer
11k
views
Do you get DFS if you change the queue to a stack in a BFS implementation?
Here is the standard pseudocode for breadth first search:
...
- 1,326
85
votes
8
answers
59k
views
Graph searching: Breadth-first vs. depth-first
When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).
Now, are ...
- 975
29
votes
4
answers
42k
views
The time complexity of finding the diameter of a graph
What is the time complexity of finding the diameter of a graph
$G=(V,E)$?
${O}(|V|^2)$
${O}(|V|^2+|V| \cdot |E|)$
${O}(|V|^2\cdot |E|)$
${O}(|V|\cdot |E|^2)$
The diameter of a ...
- 2,193
18
votes
4
answers
1k
views
Is this finite graph problem decidable? What factors make a problem decidable?
I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is ...
- 2,193
8
votes
1
answer
146
views
Find all the special graphs which can reduced to the shortest paths graph
I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative ...
- 237
9
votes
3
answers
4k
views
Unique path in a directed graph
I'm designing an algorithm for a class that will determine if a directed graph is unique with respect to a vertex $v$ such that for any $u \ne v$ there is at most one path from $v$ to $u$. I've ...
el diablo
6
votes
3
answers
282
views
Can two neighbors in a graph be at the same depth in a DFS tree?
In an undirected graph, can two nodes at an identical distance n from the root of a DFS tree be neighbors in the original graph? I'm thinking no, but I'm not sure (because of back edges)
el diablo
9
votes
1
answer
440
views
Euler cycles in biconnected components
If a graph has a Euler cycle, do the biconnected components have Euler cycles as well?
el diablo