Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
4
votes
2answers
71 views
Path in an edge-weighted undirected graph
Is it an $NP$-hard problem?
You're given an undirected graph $G(V,E)$ with edge weight $w: E \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$ in unary....
1
vote
1answer
34 views
Path in a vertex-weighted undirected graph
Is it an $NP$-hard problem?
You're given an undirected graph $G(V,E)$ with vertex weight $w: V \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$.
Does ...
1
vote
2answers
35 views
Probability that a random graph will remain planar after adding an edge
According to this answer, a random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (which is ...
1
vote
1answer
49 views
Split graph in two parts, such that most nodes have even number of edges
We have given graph of at most $200$ nodes, we want to split the given graph in two parts, such that the number of nodes with even number of edges is maximized, note that the edges that are between ...
5
votes
0answers
47 views
Constructing a connected graph with given degree sequence
I am interested in constructing simple connected graphs where each vertex has a fixed number of edges (degree) ahead of time. I had originally assume I could use some modification of the Havel-Hakimi ...
1
vote
0answers
28 views
Persistent data structures representing a directed graph's paths
Are there any standard persistent data structures that facilitate the following?
tabulating, for each arc in a rooted, oriented, acyclic multigraph, the set of root-emanating paths containing the arc
...
0
votes
0answers
30 views
$k$ -center with outliers - but the points are on a line
The classic $k$-center with outliers problem is NP-hard and there exist approximation algorithms to solve it.
However, what if we assume that the input point are on a line, rather than in an ...
-1
votes
1answer
27 views
DFS algorithm (directed graph)
If you have a back edge in a directed graph, then you may have a cycle or must have a cycle?
0
votes
0answers
18 views
Implementation of the PageRank algorithm
I have a question concerning the implementation of the PageRank algorithm
In this video Victor Lavrenko explain that the value of the page rank should be pulled from the source to the target ...
0
votes
1answer
18 views
What is the output of below algorithms on a disconnected Graph?
If I apply Dijkstra's ,BFS or Bellman-ford algorithm on a disconnected Graph then will the output be a tree or a disconnected Graph only because even if we have a disconnected Graph and we run ...
-1
votes
1answer
28 views
Book example Profit maximization understanding [closed]
This may not be the right place to ask this kind of question and it also sound a bit stupid, but please help me understand better. I am not able to to see why on page 192 "which imposes another ...
-1
votes
0answers
17 views
Residual Network s.t. $\forall v \in V, c_{in}(v)=c_{out} (v)$
Let $N=(G=(V,E),c,s,t)$ a residual network. We'll define $\forall v\in V,\ c_{in}(v):=\sum_{(u,v)\in E} c(u,v), c_{out}(v):=\sum_{(v,u)\in E} c(u,v)$.
It is given that:
$c(u,v)>0 \Rightarrow c(v,...
0
votes
0answers
12 views
Is reinforcement learning the right tool for inferring graph structure from sequence?
Sorry that this is a complicated question - I will try to get to the essence of it.
I am interested in learning the structure of sequences of numbers in terms of a graph encoding specific types of ...
-1
votes
1answer
17 views
Finding a Hamilton path in a Complete Euclidean Graph is in P
How is it possible to prove that this assert is not true?
1
vote
0answers
16 views
How can node2vec help find similar “roles” within a graph (nodes whose connections have similar structure within the graph)?
I have a question on the node2vec algorithm described in this paper.
Node2vec is a deep learning algorithm that word2vec to graphs to learn embeddings. The authors claim that it can help find nodes ...
2
votes
0answers
37 views
Finding maximum weighted n disjoint cliques
Maximum weight clique problem has some attention but i could not find any efficient approaches to this problem yet. I acknowledge that it is np-hard, but are there any known approximations?
Given a ...
0
votes
1answer
42 views
Subgraph Isomorphism checking in Multigraphs
I am considering the following problem:
Input: 2 Graphs G=(V,E), H=(V',E'). G and H are directed multigraphs
Question: Find a subgraph in G which is isomorphic to H
Is there any algorithm ...
0
votes
1answer
23 views
Algorithm to determine which neighborhoods of a graph contain a given set of vertices S
This question concerns determine which sets in a collection of sets contain a given subset S:
An undirected graph (V,G) is given with V= {1,..,m}, and given via its neighborhood sets, N(v_1),.., N(...
0
votes
0answers
14 views
References on the facility location problem
Thanks to the answers given to my last question, I'm looking for references on the facility location problem. I'd like to find a course for example, which can explain to me the problem and every I ...
3
votes
1answer
55 views
Choosing a random edge with restrictions
Given a bipartite graph $G = (V, U, E)$ such that $|V| = |U| =2^n$, one wants to sample an edge from $G$, uniformly at random, with the following operations:
1. One can sample $u \in U$ w.p $\frac{1}{|...
0
votes
1answer
52 views
Time complexity of transforming one string to another
Here is the problem:
Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. If it does produce $t$, output the length of of the shortest production ...
2
votes
1answer
22 views
GraphSlam Doubt
I am trying to implement Graph slam. I have some doubts regrading implementation. I attached a picture to clarify my doubt.
[
I have a doubt in line number 2. It show omega have a scalar value 0. ...
4
votes
1answer
51 views
Complexity of a graph parity-coloring problem
Suppose I have a positively weighted (bounded-degree) graph $G$ where each vertex in $G$ is colored either black or white. I'm curious about the complexity of the following problem:
Find a subset $S$...
6
votes
1answer
710 views
What algorithm should I use to find a minimal tree that include certain nodes within a graph?
Assume we need to include a certain set of nodes in the tree within the whole graph, the generated tree can contain nodes other than the specified set of nodes. We also need the number of edges (or ...
2
votes
2answers
66 views
Optimal meeting point
I'm interested in studying the problem of the optimal meeting point, which can be described as follow: $n$ individuals who want to gather in a restaurant (for example). They want a fair meeting point ...
3
votes
1answer
59 views
Dependent Type Theory Implementation of a Graph
In Haskell you find graphs defined like this:
data Graph a = GNode a (Graph a)
Or this:
...
2
votes
0answers
30 views
Optimal flow in a network with non-constant edges' weights
I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather ...
1
vote
0answers
26 views
Strict partitioning clustering of points in 2D space into variable (but fixed) length cluster in order to minimize distance from center
Given $\\N$ points in 2D space, one is required to cluster them into $\\M$ clusters, with each cluster of a given size $\\S_m$ such that $\sum S_m = N$, in order to minimize the sum of the distance of ...
1
vote
1answer
30 views
If the parent in a bridge is the root, is it a bridge cut node?
I am going through Professor Skiena's textbook and he says that there are 3 types of cut-nodes - root, bridge cut node, and parent cut node.
Now if the earliest reachable ancestor from a node is ...
2
votes
1answer
54 views
Find the shortest sub-tree with node deletion
Let $T=(V,E)$ be a tree rooted in $r$ and let $L$ denotes the set of leaves of $T$. For a given $v \in V$, let $C(v)$ be the out-neighors of $v$ i.e. its children in $T$ and $p(v)$ be its in-neighbor ...
4
votes
2answers
56 views
Largest weight-limited connected subgraph: NP-complete?
When playing Terra Mystica, it might be useful to predict how many spades you will get throughout the game, and use this information to decide where to build, such that you stand a good chance of ...
2
votes
2answers
37 views
Find out an algorithm that finds out if an undirected graph contains even length cycle or not using BFS?
I know how to find odd length cycles(a bipartite graph cannot have odd cycles) but I cannot manage to make an algorithm when considering even length cycles.
2
votes
1answer
14 views
Merge a set of strings based on overlaps
I have a set of strings that are slices of a single, longer string. It is not guaranteed, however, that any two strings from this set must overlap: only that all of them together overlap. I want to ...
0
votes
0answers
45 views
Time complexity of kruskal using array data structure
I was going through MST(minimum spanning tree) algorithms in a given undirected graph. By using the disjoint data structure It is fairly easy. All I have to do follow these steps:
Sort the edges as ...
0
votes
0answers
27 views
Measuring how “balanced” a binary tree is
I have some binary trees, and I'm looking for a metric to quantify how "balanced" a tree is. I don't have a rigorous definition for "balanceness", but my intuition suggests it's a measure of how close ...
0
votes
0answers
10 views
Hierarchical Parallel Processing Machines
Introduction
I am wondering if there is a generalization of parallel processing / asynchronous communication that explains/models how to deal with a hierarchy of parallel processes. Mainly looking ...
2
votes
1answer
20 views
How many different strongly connected graphs can be created given n nodes?
Given some fixed number of nodes $n$, which we will number 1 to $n$ in order to tell them apart, how many different strongly connected graphs can be created? Multiple edges with the same starting and ...
3
votes
1answer
69 views
Finding all edges on any shortest path between two nodes
Given a directed weighted graph with non-negative weights, how can I find all edges that are a part of any of the shortest paths from vertex X to Y?
In the example below the yellow edges are the ...
0
votes
1answer
23 views
Stacking Boxes in topological order
recently i was solving a programming question on uva judge Stacking boxes
link to the problem : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=...
1
vote
0answers
24 views
Clustering via Max-Cut
I wonder if there are papers that uses max cut algorithm(s) to cluster data. For example, if an edge between two nodes $u$ and $v$ indicate that $u$ and $v$ are different, then the max-cut in some ...
2
votes
1answer
24 views
How to efficiently select the initial node to start a search in a Skip Graph
Checked out a few papers on Skip Graphs:
Locally Self-Adjusting Skip Graphs
Adaptive Probabilistic Skip Graphs
Skip Graphs
Family Trees
All of the insertion/deletion algorithms assume that you have ...
2
votes
1answer
48 views
Careful 5COLOR NP hardness
Given the following definition of Careful 5COLORING:
A 5-coloring is careful if the colors assigned to adjacent vertices
are not only distinct, but differ by more than 1(mod 5)
how would a ...
2
votes
0answers
92 views
Shortest path from one source which goes through N edges [closed]
In my economics research I am currently dealing with a specific shortest path problem:
Given a directed deterministic dynamic graph with weights on the edges, I need to find the shortest path from ...
2
votes
1answer
42 views
How to find MST for each source
Let's say I have a map with factories and selling points. I want to trace the paths from factories to the selling points with the lower possible cost.
The image bellow is an example of a possible ...
0
votes
1answer
21 views
Testing graph property on enumerated graphs
I wanted to verify some graph properties on all possible graph enumerations (or graphs satisfying certain properties). There is a list of all the graphs upto 10 vertices here, but that is not ...
0
votes
1answer
30 views
A tree which each node selected as a root results in a different topology?
Show that, for every n >= 7, there exists a tree of n non-labeled nodes such that picking each of the n nodes as a root results in a different rooted tree.
2
votes
1answer
31 views
Centre, diameter, and radius of graph
I have been thinking a lot on some questions related to centres, diameter ($D$), and radius ($R$) of an undirected connected graph, but couldn't find anywhere the answers, so am posting here.
Ques1. ...
1
vote
2answers
47 views
Shortest travelling cost if we have bunch of points in 2D plane
I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane ...
1
vote
1answer
19 views
Reduce Max-Cut to Max-2SAT
I would like to find a reduction from Max-Cut to Max-2Sat.
Could someone shed light on this problem, preferably spiced with some intuition?
Thanks,
Matan.
2
votes
1answer
33 views
Minimum Height Trees. Why does deleting leaves layer-by-layer give us the answer?
Here is the problem I tried to solve. Finally, I gave up and found a solution which was correct. Here is it.
Here is the problem description:
For a undirected graph with tree characteristics, we ...
