Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.
0
votes
1answer
17 views
How is a hypergraph different from a bipartite graph?
How is a hypergraph different from the bipartite graph generated from the hypergraph by introducing new vertices for each hyperedge, and connecting these vertices with the vertices connected by the ...
1
vote
1answer
15 views
Get nodes that are participating in any cycle in a graph
I have a problem that states the following :
Give a cyclic graph , output for each node if the node removes all cycles in the graph.
The most trivial way to do this is using a Union-find ...
1
vote
0answers
14 views
How to cluster nodes based on the number of dependencies
I have a problem where, there are a set of nodes and dependencies between them. I want to cluster them based on the maximum number of dependencies. Dependencies can be thought of as number of edges ...
1
vote
0answers
17 views
Library for Maximum independent set on a sparse bipartite graph (from sparse matrix)
I am working with sparse matrices (not particularly huge, <100Mb) and I want to compute the largest independent set on the bipartite graph $(N,E)$ defined as follows: suppose the matrix is named ...
1
vote
1answer
22 views
How to perform alphabetically ordered DFS?
I've been working on this graph and just completely botching it. I mean to say that my solution may be the worst possible other than if a monkey had thrown darts at the graph to decide the next path. ...
1
vote
1answer
20 views
Find the number of topological sorts in a tree
Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself.
I've tried thinking what would be the best for m to define it but couldn't get ...
2
votes
0answers
45 views
Effect of increasing the capacity of an edge in a flow network with known max flow
I need your help with an exercise on Ford-Fulkerson.
Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance.
Now suppose you are ...
-4
votes
0answers
19 views
how to run minisat+ sat solver [closed]
I downloaded the minisat+zip file
I extracted the zip.According to install file i run
make rx
but i have the following result:
...
0
votes
2answers
54 views
Worst case scenario in binary search tree retrieval
Well, i have a binary search tree $T$ that is equilibrated by height witch has $2^d+c$ nodes ($c<2^d$).
What is the number of comparisons that will occur in the worst case scenario, if we ask ...
1
vote
0answers
29 views
Proving that a BST with N>=1 nodes will have log(N+1) levels
I am trying to prove by induction the following theorem:
Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels.
I've ...
2
votes
2answers
65 views
Max-Flow: Detect if a given edge is found in some Min-Cut
Given a network $G=(V,E)$ , a max flow f and an edge $e \in E$ , I need to find an efficient algorithm in order to detect whether there is some min cut which contains $e$.
Another question is, how do ...
-3
votes
2answers
58 views
Does reachability belong to P?
Reachability is defined as follows:
a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$?
Is it possible to write a polynomial time algorithm for it?
...
5
votes
3answers
144 views
Team construction in tri-partite graph
The government wants to create a team with one alchemist, one builder, and one computer-scientist.
In order to have good cooperation, it is important that the 3 team-members like each other.
...
-1
votes
0answers
32 views
Bellman-Ford and Dijkstra - Differences after k Iterations
I have a small statement I need to prove and I'm not sure how to start.
Introduction:
Let G be a directed graph.
Let w be a non-negative weight function on the edges of G.
Let s be the ...
4
votes
1answer
73 views
Longest path in grid like graph
This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:
Find the length of the longest ...
1
vote
1answer
32 views
Is there a program to solve a metric TSP for 80 edges at optimum?
i'm going to use the Christofides heuristic algorithm in order to solve a TSP for about 80 edges. Eventually i should have a solution, that is within the factor 1.5 of the optimum.
But when i'm ...
1
vote
2answers
183 views
Shortest path with odd weight
Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd.
We are looking for an algorithm for finding the weight of the shortest odd ...
10
votes
1answer
223 views
Longest cycle contained in two cycles
Is the following problem NP-complete? (I assume yes).
Input: $k \in \mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are not ...
1
vote
0answers
24 views
Graph estimation in high dimensional data
I am trying to estimate the graph in very high dimensional data, I mean with million nodes. Up to now all the papers that I have found, they are limited to few thousands.
All of them like graphical ...
2
votes
1answer
176 views
Shortest paths candidate
Let $G = (V,E)$ be a directed graph with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. ...
3
votes
1answer
64 views
Proof that fast broadcasts have to target larger cycles first
I am having trouble trying to formulate a simple proof. I can clearly see that what I am trying to prove is correct but to prove it I am not sure what to do.
The problem is a broadcasting problem on ...
8
votes
3answers
203 views
Graph Has Two / Three Different Minimal Spanning Trees?
I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
4
votes
1answer
92 views
Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?
Given a directed graph with the following attributes: - a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. - additionally a set of nodes having bidirectional ...
1
vote
1answer
60 views
What makes Bayesian Networks decomposable into joint trees?
Given a Bayesian Network $N$, one can build a junction/joint tree $JT$ over $N$ by applying series of steps (namely, moralisation,triangulation..etc). Then we can use $JT$ to answer queries over $N$.
...
1
vote
1answer
76 views
Show that Vertex-Cover is NP-complete, using Stable-Set
My task is to give proof, the Vertex-Cover problem is NP-complete, assuming it's already shown that the Stable-Set problem is NP-complete, too.
My approach: i know, Stable-Set is NP-complete, and all ...
0
votes
1answer
171 views
Reducing from Hamiltonian Cycle problem to the Graph Wheel problem [duplicate]
EDIT: This question is different from the other in a sense that unlike it this one goes into specifics and is intended to solve the problem. In the previous post, the only answer was a hint. In this ...
1
vote
1answer
33 views
Vertex Cover problem modification
Modification of vertex cover problem.
Given a graph G,does G have a vertex cover with 10 vertices? Is this problem still in NP?
Given a graph G and integer k, does G have a vertex cover with k ...
2
votes
0answers
31 views
Complexity of finding a subset of vertices within distance k of each other, given a set of vertices
I am trying to understand an algorithm presented in Using Stable Communities for Maximizing Modularity by S. Srinivasan and S. Bhowmick, along with its complexity results. (The complete algorithm is ...
-3
votes
1answer
58 views
Would a graph with 8 vertices and 6 edges be connected? [closed]
I need to know if a graph with 8 vertices and 6 edges is a connected graph and why?
3
votes
1answer
27 views
Finding Hamiltonian cycles in polynomial space
Question: If $H = \{(G,m)$ $|$ $G$ is a graph with $m$ distinct Hamiltonian cycles $\}$ ($m$ is in binary), prove that $H \in$ polynomial space.
My thoughts: I thought that I could show that $H \in ...
1
vote
3answers
84 views
k-path problem - P, NP or NPC?
I need to determine which complexity class this problem belongs to:
Given a graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of length $k$ exist between thesee two ...
2
votes
0answers
38 views
End-Of-The-Line Augmented Problem of PPAD
Famous PPAD class of problems is formally defined by specifying one of its complete problems, known as End-Of-The-Line:
End-Of-The-Line Problem:
$G$ is a (possibly exponentially large) directed ...
2
votes
1answer
75 views
How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE?
Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET:
INDEPENDENT SET VALUE
Input: An undirected graph G.
Output:The size of the largest ...
8
votes
1answer
87 views
How to practically construct regular expander graphs?
I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices.
What is the easiest method to do this in practice?
Constructing a random d-regular graph, which is ...
7
votes
1answer
95 views
Finding the largest 3-clique-free induced subgraph
Consider this problem:
Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that:
$G'$ is an induced subgraph of $G$
$G'$ has no 3-cliques
$|V'|$ is maximal
So the ...
2
votes
1answer
105 views
Shortest path with exactly $k$ edges
From Skiena's book:
Let $G = (V,E,w)$ be a directed weighted graph such that all the weights are positive. Let $v$ and $u$ be two vertices in $G$ and $k \leq |V|$ be an integer. Design an algorithm ...
1
vote
0answers
60 views
Terminology for vertices in graph connecting vertices “in” and “outside of” a given component
Basically, I am looking for a (well-defined) term for some "borderline" vertexes interconnecting other vertices in and outside of a given connected component.
More specifically, given directed graph ...
1
vote
0answers
45 views
LInear time algorithm to find the diameter of a tree [duplicate]
This is NOT HW, this is from Skienas book, and I just couldn't solve it at all.
Please give me a hand here, in understanding and solving it, thanks.
Let G = (V, E) be a binary tree. The distance ...
8
votes
1answer
122 views
Pebbling Problem
Pebbling is a solitaire game played on an undirected graph $G$ , where
each vertex has zero or more pebbles. A single pebbling move consists
of removing two pebbles from a vertex $v$ and adding ...
-1
votes
1answer
44 views
Directed Acyclic graph question [closed]
first of all - great site!
Here is my problem, I am studying for an interview, and I ran into this problem,
http://i.stack.imgur.com/JmdER.png
I am asked, Suppose an arithmetic expression is given ...
5
votes
1answer
96 views
Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves
This problem is about finding a route on a square grid.
The starting point is $(1,1)$ and the target point $(n,m)$.
I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$.
...
1
vote
2answers
99 views
Show that the following problem is NP-complete
In a directed graph, the indegree of a node is the number of incoming edges and
the outdegree is the number of outgoing edges. Show that the following problem
is NP-complete. Given an undirected graph ...
1
vote
0answers
18 views
Is it possible to discern the quality of web data from networks derived from it?
One topic I've recently looked at is co-occurence networks formed from Twitter tweets. This is how I felt after looking at the tweets of random people:
This leads me to the question:
Question: ...
1
vote
1answer
80 views
Size of maximum clique given a fixed amount of edges?
Given an undirected graph $G = (V,E)$, what is the clique number $\omega(G)$ given $|E|$, i.e., the size of the largest clique in a graph with $|E|$ edges.
I think this is doable after realizing that ...
9
votes
1answer
158 views
Transforming an arbitrary cover into a vertex cover
Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$.
I have furthermore a set $C$ of points where each point $c \in C$ is contained ...
2
votes
1answer
26 views
Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?
Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? ...
2
votes
1answer
136 views
Maximum number of augmenting paths in a network flow
Let's say we a have flow network with $m$ edges and integer capacities.
Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.
A good way to start thinking ...
1
vote
0answers
92 views
Bridge determination in undirected graphs
A bridge (critical edge) in an undirected graph is an edge whose removal increases the number of connected components.
I need to determine all critical edges in an undirected graph, in $O(V+E)$ time. ...
0
votes
0answers
27 views
Bridge determination in undirected graphs [duplicate]
I need to determine all critical edges (bridges) in an undirected graph, in $O(|V|+|E|)$ time. From what I found out, I need to use a modified Depth-First search, but all pseudo-code algorithms I ...
5
votes
2answers
67 views
Given a tree, find a vertex which maximizes the minimum distance to any leaf
If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf.
I am sure this problem has been studied before.
Does anybody know the ...
