Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

Filter by
Sorted by
Tagged with
21 votes
2 answers
772 views

Finding at least two paths of same length in a directed graph

Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$. I would like to know if there are already algorithms for calculating the following decision problem: Are there at least two ...
3 votes
1 answer
692 views

Efficient bandwidth algorithm

Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario: Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 ...
9 votes
5 answers
22k views

Using Dijkstra's algorithm with negative edges?

Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance ...
's user avatar
3 votes
0 answers
140 views

Beating fair colorings with few edges

I have been investigating parallel algorithms to compute certain two-dimensional dynamic programming recursions (on natural parameters); see also here. Under certain assumptions, cases one and two can ...
  • 71.2k
0 votes
2 answers
290 views

Proving that the cover time for graph is exponential in the worst case

How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$? The cover time is the expected length of a random walk that visits all vertices.
  • 489
1 vote
0 answers
38 views

constrained cover on biparite graphs [duplicate]

Possible Duplicate: Restricted version of vertex cover Suppose we have a $(A,B,E)$ bipartite graph and a positive integer k. Suppose that k is smaller than $|A|$ and we want to find one of those ...
2 votes
1 answer
134 views

Algorithm to check the 2∀-connectness property of a graph

A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of ...
  • 123
7 votes
2 answers
995 views

Has anyone found polynomial algorithm on Hamiltonian cycle isomorphism?

As the title says, has anyone found a polynomial time algorithm for checking whether two graphs having a Hamiltonian cycle are isomorphic? Is this problem NP-complete?
2 votes
0 answers
199 views

IDS algorithm optimality for grid?

My homework is implementing algorithms BFS, DFS, depth-limited and IDS for the map as a 2D grid with 8 directions of movement. I read that the IDS algorithm is optimal, but in my case is not optimal ...
's user avatar
3 votes
1 answer
504 views

Restricted version of vertex cover

I am interested in the complexity of the restricted version of the vertex cover problem below: Instance: A bipartite graph $G =(L, R, E)$ and an integer $K$. Question: Is there $S \subset L$, $|S| \...
's user avatar
9 votes
1 answer
1k views

Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
  • 261
2 votes
1 answer
2k views

Enumerating all the walks in a graph between a start vertex and a terminal vertex?

I was reading something about the concept of walks in a graph b/w a start vertex and a terminating vertex in a graph and then suddenly a problem struck me, is there any algorithm or a method that can ...
6 votes
2 answers
8k views

How to find spanning tree of a graph that minimizes the maximum edge weight?

Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am ...
  • 1,101
7 votes
2 answers
13k views

Reducing minimum vertex cover in a bipartite graph to maximum flow

Is it possible to show that the minimum vertex cover in a bipartite graph can be reduced to a maximum flow problem? Or to the minimum cut problem (then follow max-flow min-cut theorem, the claim holds)...
21 votes
2 answers
13k views

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same ...
  • 1,101
4 votes
2 answers
3k views

How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves?

Given a complete binary tree with $n$ nodes. I'm trying to prove that a complete binary tree has exactly $\lceil n/2 \rceil$ leaves. I think I can do this by induction. For $h(t)=0$, the tree is ...
7 votes
0 answers
186 views

What is the proof for the lemma "For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge"?

For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
  • 261
5 votes
1 answer
1k views

Dependency Graph - Acyclic graph

I have a directed acyclic graph where edge (A,B) means that vertex A depends on vertex B. Vertex deletions have the following restrictions: When vertex B is removed, all dependent vertexes should ...
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 ...
4 votes
1 answer
142 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
386 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 ...
7 votes
1 answer
424 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
281 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,...
's user avatar
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. ...
5 votes
1 answer
79 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
160 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
883 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 ...
8 votes
0 answers
202 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
45k 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? ...
's user avatar
5 votes
2 answers
4k 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 ...
  • 151
22 votes
0 answers
513 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
878 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
233 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 ...
's user avatar
24 votes
2 answers
2k 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 ...
  • 391
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
261 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
162 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 ...
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 ...
  • 561
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'...
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
1k 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 ...
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
964 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 ...
's user avatar
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