Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

learn more… | top users | synonyms (1)

0
votes
0answers
26 views

Marriage algorithm that maximizes number of pairings

I have a bipartite graph similar to the marriage problem, where there are M males and N females, and a 1:1 matching between males and females is desired (with the remainder of the more populous gender ...
-2
votes
1answer
58 views

How to prove correctness of BFS algorithm [on hold]

How do we prove the correctness of BFS or DFS algorithms for finding connected components in the graph? I have came up with a traversal algorithm which is very similar to these algorithms, but I need ...
2
votes
1answer
39 views

Control flow graphs - Tree decomposition

Considering above terminologies for drawing control flow graphs for any program, it is very simple. For example : While A if B do .. else do .. end while For ...
0
votes
1answer
33 views

Recognizing interval graphs--“equivalent intervals”

I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper: Each interval graph has a corresponding interval model in which two intervals overlap if and only if ...
2
votes
1answer
10 views

Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths

Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut ...
0
votes
0answers
19 views

Is the vertex cover problem NP-Hard in general graphs and in P for bipartite graphs? [closed]

Wikipedia says that finding the minimum vertex cover is NP-Hard. However, for bipartite graphs, I can solve the maximum matching problem with Hopcroft-Karp in polytime and then, through Koenigs ...
2
votes
2answers
96 views

What is the difference between maximal flow and maximum flow?

What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a ...
3
votes
1answer
262 views

Possible to connect arbitrary number of dots without intersections?

A (now closed) question on SO made me think about the following problem: Given an arbirtary number of points (2D), draw a path that consists of straight lines between points, visits each point ...
4
votes
1answer
35 views

Construct a digraph given its in-degree and out-degree distribution

Could anyone help me with this algorithmic problem: Given the in and out degrees of a set of vertices, is it possible to determine if there exist a valid graph respecting this constraint? The graph ...
2
votes
2answers
107 views

Minimum path between two vertices passing through a given set exactly once

Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes ...
-1
votes
2answers
49 views

number of edges in a graph

I got a problem related to graph theory - Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is {(i,j):1<=i,j <=12}. There is an edge between (a, b) and (c, ...
3
votes
1answer
473 views

Best solutions to 6 degrees of separation

From purely my knowledge of computer science a simple breadth first search from root A in search of node B, while keeping track of the depth of the tree, would be the most effective way to check ...
1
vote
1answer
28 views

number of different undirected graphs?

The question is: How many different undirected graphs are there with n nodes and no parallel edges but may include self-loops? I've been wracking my brain over this for hours now. Basically, I know ...
2
votes
2answers
39 views

Reconstruct directed graph from list of ancestors for each node

I have a problem that I encountered that boils down to the following: Considered this directed graph I found on Google: I have the following information available to me ...
2
votes
0answers
31 views

What is hiding behind amortized constant delay enumeration?

The following may contain errors. It is precisely because I am not sure I understand the topic that I am asking questions. I do not have books about it and could not find an adequate reference on the ...
1
vote
0answers
47 views

Clique and PSPACE [closed]

I was wondering how I could go about creating an algorithm that gets all the cliques in a graph in PSPACE So far, based on some of the readings I've done, I am considering to use bit-strings (that ...
1
vote
3answers
186 views

Can we test whether two vertices are connected in time linear in the number of nodes?

Consider the problem: Given an undirected graph and two of its vertices, is there a path between them? I often read that this problem can be solved in linear time in the number of vertices! I ...
-1
votes
0answers
20 views

Minimal I-maps induced by sets of scopes. Clarification needed [closed]

I've asked this question on cross validated and got no answer. Maybe it's more of a computer science question. Here it goes: I have a question about Prop. 9.1 on page 307 in "Probabilistic Graphical ...
5
votes
3answers
93 views

Compact representation of paths in a graph

I've a subset of the simple paths in a graph. The length of the paths is bounded by $d$. What's the most compact way (memory-wise) I can represent the paths such that no other paths apart from the ...
2
votes
2answers
311 views

If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?

If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time? Intuitively this sounds correct, as ...
1
vote
1answer
19 views

Minimum cut versus sparsest cut? [closed]

My question is that I'm trying to find the sparsest cut in a connected, undirected graph (all weights are = 1). Basically, I am looking trying to find the smallest cut (i.e., number of edges cut since ...
1
vote
1answer
44 views

Looking for sources: Graph search in social media [closed]

I am looking for more information/references on how graph search is utilized in social media. Papers, books , anything really.
1
vote
1answer
25 views

Is the minimum weight independent dominating set np-complete in chordal graphs?

I have a found a small article [1] saying (the first paragraph of the introduction) that the minimum-weight independent dominating set is NP-complete in chordal graphs, but at the same time, seems to ...
5
votes
1answer
158 views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from ...
0
votes
1answer
79 views

Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

I am reading Prim's MST for the first time and wanted to implement the fast version of it . $m$ - The number of edges in the graph $n$ - The number of vertices in the graph Here's the algorithm ...
1
vote
0answers
83 views

Algorithm to determine a minimal cost graph [closed]

I'm trying to solve this problem: Given a collection of cities and the number of commuters between cities, design a network of roads for minimal cost where cost includes the cost of building the ...
2
votes
1answer
35 views

Merge-by-weight to solve reachability problems in trees and DAGs

Let $T = (V, E)$ be a tree with a designated root $r \in V$. The fact that the tree is rooted allows us to speak of "subtrees of $T$ rooted at some node $x \in V$". Let's say we have a (not ...
3
votes
3answers
96 views

How to implement graph search to solve Sudoku puzzle

My teacher pointed out to us during lectures that we could use Graph Search to help us solve Sudoku puzzles which has left me puzzled . I dont see how this is possible as Graph Search is mostly ...
0
votes
1answer
28 views

Minimizing the following objective function with matrices

I am trying to work out centrality in a network using Freeman's network centrality. I have an in degree of 83 and an out degree of 110. I want to work out the network centrality using my out degree ...
2
votes
1answer
24 views

Meyniel's theorem + finding a Hamiltonian path for a specific graph family

Let's say we have a directed graph $G = (V, E)$ for which $(v, w) \in E$ and/or $(w,v) \in E$ holds true for all $v, w \in V$. My feeling is that this graph most definitely is Hamiltonian, and I want ...
5
votes
1answer
127 views

Is the algorithm implemented by git bisect optimal?

Let $G$ be a DAG. We know that some nodes in $G$ are "bad", while the others are "good"; a descendant of a bad node is bad while the ancestors of a good node are good. We also know that bad nodes have ...
6
votes
1answer
113 views

Why choose D* over Dijkstra?

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
2
votes
1answer
98 views

Why is determining the size of a maximum independent set or a clique in P?

I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard. With respect to ...
1
vote
1answer
24 views

How many times an empty 4-cycle can be counted in an undirected graph?

I have an undirected graph where each node is labelled with an integer key and I'm asked to detect every simple 4-cycle, which can be seen as an empty square (i.e. the two opposite nodes of the cycle ...
1
vote
2answers
71 views

Applications of Depth-First Spanning Tree

I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that ...
1
vote
1answer
39 views

Proving the correctness of an algorithm, which computes the connectivity of a directed graph

Let $G=(V,E)$ be a directed graph. The connectivity of a graph is the defined as the cardinality of a smallest separator of $G$. A separator of $G$ is a subset $U$ of $V$, such that $G-U$ is not ...
0
votes
0answers
69 views

Finding shortest path in a graph when edge weights depend on the chosen vertices

Here is my problem: I have a directed weighted graph with a substantial amount of vertices (few thousands), no cycles, in fact, it includes a starting node, a final node and an $m \times n$ grid ...
2
votes
1answer
90 views

Degree conditions sufficient for Hall's theorem

Let $G=(L,R,E)$ be a bipartite graph, are there conditions on the degree of the vertices under which the condition of Hall's theorem is surely satisfied? (meaning a perfect matching exists in the ...
3
votes
0answers
95 views

Prim's Algorithm - Building the Priority Queue

Suppose we were using a priority queue(PQ) to implement Prim's algorithm. My understanding is that initially the weight of all vertices is set to $\infty$. The weight of the starting vertex is then ...
1
vote
1answer
79 views

Deleting vertices so that largest connected component has at most $n/2$ vertices

I have a question regarding a graph algorithm which is as follows: Given a graph $G = (V,E)$ whose vertices are uniquely labeled $\{1, 2,\dots ,n\}$ we want to determine the smallest integer $k$ such ...
5
votes
1answer
70 views

Why can't you write the 2-paths problem as a max-flow problem?

This is a follow-up question to this. Consider the 2-paths problem: Given a directed graph $D=(V,A)$ and pairs of vertices $(s_1,t_1)$ and $(s_2,t_2)$, are there paths $P_1 = (s_1,\dots, t_1)$ and ...
0
votes
1answer
97 views

Does “standard” Dijkstra's algorithm work with bi-directional edges and zero cost edges?

I have been reading about Dijkstra's algorithm and I think I understand it. I followed the algorithm in pseudo-code from Wikipedia, and now I wonder: If my graph is bi-directional and I add each ...
1
vote
2answers
53 views

Simple path in a graph, within a given range of lengths [closed]

Given an undirected graph $G(V,E)$ and two nodes $s$ and $t$, $s,t\in V$, find a path whose length $L$ is bounded by a lower bound $N$ and an upper bound $M$, $N\leq L\leq M$. So, for example, $N=4, ...
1
vote
2answers
53 views

Finding all paths with lengths in a fixed interval in sparse graphs

What is the most efficient way to find all paths of length M to N in a large sparse graph? Some general information: Graph has 30,000 to 50,000 nodes Average number of edges per node ~ 10 M=4, N=7 ...
2
votes
0answers
37 views

Update SSSPP solution on complete digraph on weight changes

I have a directed graph with $N$ vertices. Every pair of vertices is connected by two edges (one in each direction), and each of these edges has a weight which may be negative. On various occasions ...
2
votes
1answer
65 views

Graphs with bounded degree and small max independent set

Graphs with degree $\Delta$ have a maximum independent set of size $\alpha \geqslant \frac{n}{\Delta}$ where $n$ is the number of vertices. But, are there graphs such that $\alpha \approx ...
12
votes
1answer
294 views

Why does Dijkstra's algorithm fail on a negative weighted graphs?

I know this is probably very basic, I just can't wrap my head around it. We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph. My ...
5
votes
1answer
254 views

Optimal algorithm to traverse all paths in the order of shortest path

I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path. The simplest way that comes to mind is to do a ...
3
votes
1answer
68 views

Most common subset of size $k$

I'm trying to write an algorithm that detects the most common subset of at least size $k$, from a collection of sets. If there are ties for the most common subset, I want the one of them whose size ...
2
votes
4answers
124 views

Converting a digraph to an undirected graph in a reversible way

I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I ...