Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.
-1
votes
1answer
26 views
Algorithm for Graph merge and recompute
I want to construct a complete graph where each node is connected to every other node. The link between the nodes give a distance function (does not follow triangle inequality) between them. What I ...
1
vote
0answers
29 views
Is there a word/name for the node(s) in a graph with the minimal cumulative path length to a set of other nodes?
In other words, given a graph with nodes $N=\{n_0,n_1,...,n_j\}$, and a set of nodes in the graph $M=\{n_a,n_b,...,n_k\}$ with $M\subseteq N$, I'm looking for what to call the node or nodes $n'$ which ...
5
votes
0answers
33 views
Complexity of finding a spanning tree that minimizes the maximum interference
Given $n$ nodes in the plane, connect the nodes by a spanning tree.
For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning ...
4
votes
1answer
72 views
Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph
Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes.
I tried to look it up at a few places (including ...
3
votes
1answer
33 views
Max cut in cubic graphs
The following question is related to the max cut problem in cubic graphs. In this survey paper Theorem 6.5 states
A maximal cut of a cubic graph can be computed in polynomial time
Browsing ...
2
votes
2answers
104 views
Detecting cycles in undirected graph
I want to detect cycles in an undirected graph such that I get a list of all edges/vertices which form each cycle. For a graph G({a,b,c,d}, {a-b, b-c, c-d, d-a, b-d}) this would be {a, b, c, d}, {a, ...
5
votes
1answer
106 views
Dividing a weighted planar graph into $k$ subgraphs with balanced weight
I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge ...
3
votes
0answers
41 views
Drawing Zonotopes from an Adjacency Matrix
I'm conflicted whether to post this here or in either math.stackexchange or mathematica.stackexchange.
Define a "simple zonotope" to be a regular $2n$-gon which is tiled by the following rule: all ...
1
vote
1answer
74 views
Number of Combinations of Connected Bipartite Graphs
Given two sets of vertices $U$ (size $n$) and $V$ (size $m$), how many possibilities of set of edges $E$ exist that make the bipartite graph $G = (U, V, E)$ connected?
Obviously there are $2^{n m}$ ...
2
votes
1answer
97 views
Can the shortest simple cycle between two given nodes be found in polynomial time?
Given an undirected simple graph $G$ and two nodes $s$ and $t$, the question asks for an algorithm to find the shortest simple cycle (no edge or vertex reuse) that contains the two. As far as I know, ...
4
votes
1answer
25 views
Subgraph isomorphisms: does large out-expansion imply large in-expansion?
Let $G$ be a directed graph, and $H$ a subgraph of $G$ that contains all the vertices of $G$. (In other words, $H$ is obtained by deleting some of the edges of $G$, but not any of the vertices of ...
2
votes
1answer
42 views
Electrical resistance of expander graphs
Let $G$ be a $d$-regular expander graph. What is the electrical resistance of $G$? Is it a constant independent of the number of nodes $n$ once $d$ is large enough? If not, can we give matching upper ...
1
vote
1answer
72 views
Sabatier conjectures
While I was doing
CLRS (3rd
edition), I came across this question on page 629:
Professor Sabatier conjectures the following converse of Theorem
23.1:
Let $G = (V,E)$ be a connected, undirected ...
-1
votes
1answer
37 views
Minimum path in an undirected graph with 2 kinds of edges
Given an undirected graph with positive weights, there are 2 kinds of edges: locked edges and unlocked edges.
Determination if a given edge is either locked or unlocked edge takes O(1).
For given ...
1
vote
1answer
42 views
r-regular graph and hamiltonian path
I am having some issues proving a problem I am working on. I have been sketching out examples but the proof is not jumping out at me.
Question:
Let $G = (V,E)$ be an undirected $r$-regular graph ...
1
vote
1answer
39 views
Upper bound on the number of edges relative to the height of a DFS tree
Let $T$ be a depth-first search tree of a connected undirected graph $G$ and $h$ be the height of $T$. How do you show that $G$ has no more than $h \times |V|$ edges where $|V|$ is the number of ...
3
votes
1answer
43 views
Is there a name for this kind of graph?
Is there a name for the DAG obtained from a directed graph by collapsing together the strongly connected components?
2
votes
1answer
72 views
Minimum number of vertices to remove to bound the largest connected component of a graph
I have this problem, maybe anybody could help.
Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G ...
1
vote
2answers
81 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 ...
2
votes
1answer
61 views
Get nodes that are participating in any cycle in a graph
I have a problem that states the following :
Given 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
21 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
25 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
32 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
24 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
65 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 ...
0
votes
2answers
72 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
37 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
76 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
60 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?
...
6
votes
5answers
165 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.
...
4
votes
1answer
121 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
34 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
201 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
228 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
28 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
178 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
71 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
266 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
98 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
71 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
124 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
185 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
37 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
42 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
28 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
92 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
39 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
83 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 ...
9
votes
1answer
101 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
106 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 ...
