Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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 ...