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

Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

1
vote
0answers
16 views

Minimizing cost of shortest paths to a group of vertices by adding minimal edges to an unconnected vertex

Let $G=(V,E)$ be directed graph, where the weights of the edges are non-negative. Consider a $T \subset V$, and $u \notin V$. I'm trying to develop algorithm for following optimization problem: ...
0
votes
0answers
15 views

Can ideas of maximum flow be used to solve the problem of traffic?

So I'm considering the problem of traffic congestion. I was wondering if it is possible to solve the problem of Maximum Flow on a graph representing a city, at least in theory (lets say you have ...
0
votes
0answers
22 views

How to randomly sample a social graph to find paths between at least 20% of profiles?

Given a Graph, where we know Total number of nodes (~100,000) Average no of connections per node (~200) Maximum distance between two nodes (~5) How many nodes (and its connections) do we have to ...
0
votes
0answers
13 views

Can we update a cut-block tree in linear-time?

Every graph $G$ admits a cut-block-forest decomposition. This is a forest $F$ where each node corresponds to a maximal 2-connected component (called block) in $G$ and two nodes are adjacent in $F$ if ...
0
votes
1answer
23 views

Proving equivalent definitions for MSTs

I am working on the following homework exercise: Let $G = (V,E)$ be an undirected graph and $c: E \rightarrow \mathbb{R}$ it's cost function. Further let $T = (V,E')$ be a spanning tree in G. I need ...
1
vote
1answer
45 views

A simple way to find the feasible region of a system with simple constraints

I'm coding something... weird, and I'm running into some constraint satisfaction and graph theory problems, which are fields I'm not too experienced in. Here's the problem: I start out with this ...
1
vote
0answers
32 views

Minimum and maximum of sum of inverse degree of a graph

Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find ...
1
vote
0answers
5 views

graph trend filtering results from different maxflow algorithm

We have followed the official code of the Graph trend filtering (GTF) https://arxiv.org/abs/1410.7690, and modified the code with Ford Fulkerson Algorithm (FFA) instead of parametric maxflow. The ...
4
votes
1answer
56 views

Given a directed graph, allowed to reverse one or zero edges to make shortest path from S to T

I googled and couldn't find something similar, thanks for your attention and help. EDIT: Thanks for your feedback. Now I try to be more clear. Given a directed graph with $V$ vertices and $E$ edges....
0
votes
0answers
32 views

Number of X3SAT Instances?

Exactly 1 in 3SAT (X3SAT) is known to be NP-Complete. It remains NP-Complete even if we only consider instances that are monotone and linear. Monotone means all of the literals are positive. Linear ...
2
votes
1answer
41 views

Understanding CLIQUE structure

I am working on the following problem: Recall the definition of a complete graph Kn is a graph with n vertices such that every vertex is connected to every other vertex. Recall also that a clique is ...
0
votes
1answer
17 views

Is any State Space Tree always Binary Tree?

A backtracking algorithm generates, explicitly or implicitly, a state-space tree. Introduction to the design & analysis of algorithms / Anany Levitin I wonder that whether the saying ...
4
votes
0answers
37 views

Karp hardness of a module in a graph

DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property: For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
1
vote
1answer
21 views

Manber's graph-partitioning implementation

I'm having trouble understanding a part of Manber's graph-partitioning algorithm, presented in A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File. Generally speaking ...
1
vote
0answers
17 views

Can Fiedler vector be used for displaying an undirected graph in a sequential manner?

My problem is to display an undirected unweighted graph in a grid format ( $ (n \times 3) $ - matrix for simplicity) without compromising on the connections displayed on the screen (the only ...
1
vote
0answers
21 views

Extracting room voids in a house

I am looking to create a series of closed volumes that represent the empty voids made by rooms in a house. In order to do this, all I have is the raw geometry of all the elements that encapsulate ...
0
votes
0answers
22 views

Form a Tree having minimum diameter

I am given a connected graph. I have to construct a spanning tree from the graph, that has minimum diameter. However, I looked for the solution, and the solution goes like this. If the diameter of ...
0
votes
0answers
30 views

Finding a minimal subgraph covering all parts of a multipartite graph

I have a large set of nodes $n_i$ and edges $e_{ij}$. Each node can be sorted into exactly one supernode $N_i$ based on a known and fixed parameter. Nodes within the same supernode have no direct ...
0
votes
2answers
29 views

Pancake Sorting Graph Recursive Definition

I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough ...
2
votes
0answers
32 views

Edmond's Blossom algorithm (Maximum Matching) explanation

I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here. Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph ...
2
votes
1answer
46 views

Digraph vertices: classification by counting outgoing walks

I'm reproducing a question I posted on MSE (yet with no answer both there and by myself). Given a (finite) directed graph $G = (V, E)$. For each vertex $v \in V$ and a natural number $n$, let $W_v(n)$...
2
votes
0answers
33 views

generalized translation operator on graph [closed]

David IShuman in " vertix-frequency analysis on graph" claims that,"we generalize one of the most important signal processing tools – windowed Fourier analysis – to the graph setting and When we apply ...
1
vote
0answers
26 views

How to handle negative edge weights in distance vector routing protocol with a digraph?

In a Distance Vector routing protocol each node implements a Bellman-Ford inspired algorithm that shares it's routing table (Distance Vector) with each of it's incoming links (upstream neighbors). ...
3
votes
1answer
29 views

How would I algorithmically “stretch” polygons on a plane by re-scaling the distances between interior points?

I've been thinking about a computational problem and could use some guidance for how to go about developing an algorithm to solve it. On a Euclidean plane, I have a polygon A, a set of points A* ...
2
votes
1answer
34 views

Algorithm and Formalism for Most Remote Vertices

In the graph below, N and M are most remote, and H is also an extremum. Has the problem of finding the most remote vertices been formalized? Could you point me to publications or references on the ...
0
votes
0answers
21 views

Constructing an n-node DAG, with exactly k paths between node 1 and node n

Pretty straight forward, yet I didn't find how to approach such a problem. I tried constructing a solution from the reverse problem (Given a DAG count the number of paths between node 1 and node n), ...
1
vote
0answers
11 views

Given a simple graph G, what's the quickest known way to sample one of it's spanning trees at random?

Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle. We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking ...
0
votes
1answer
40 views

Babyface vs Heel

So here's the question: "There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional wrestlers, there may or may not be a rivalry. ...
3
votes
1answer
31 views

Find least connected sub-graphs

For example the nodes in this graph should be separated into two groups (A,B,C) and (D,E,F,G). By looking at a graph of citations, assuming that most citations are papers from the same field, can we ...
2
votes
1answer
139 views

Find shortest path that visits all nodes in a given set of nodes

Suppose I have a graph $G$ and a set of target nodes $S = \{A_1, ..., A_n\}$. I'm attempting to find the shortest path that visits each target node, in order, without visiting the same node twice. ...
0
votes
0answers
33 views

Reducing a vertex AND edge colouring optimisation problem

I have a graph colouring problem that I'm having trouble solving. Here's the problem: We are given: A set of acyclic graphs $S$ that are linear (i.e. $\forall (G \in S), G$ is connected ...
0
votes
0answers
63 views

Blocking directed paths on a DAG with a linear number of vertex defects

Let $G=(V,E)$ be a directed acyclic graph. Define the set of all directed paths in $G$ by $\Gamma$. Given a subset $W\subseteq V$, let $\Gamma_W\subseteq \Gamma$ be the set of all paths $\gamma\in\...
3
votes
3answers
74 views

$k$ vertex-disjoint paths cover in Directed Acyclic Graph

The problem is that: in a directed acyclic graph $G$, I want to know the maximum vertices that can be covered by $k$ vertex-disjoint paths. Obviously, the value of $k$ is smaller than the minimum ...
3
votes
1answer
113 views

What is the best way to merge cycles to minimise total weight?

Suppose I have a vertex-disjoint set $S$ of simple cycles in a weighted undirected graph. So no vertex $v$ is contained in more than one cycle. A cycle $c$ is a closed path with no repeated vertices: $...
2
votes
1answer
61 views

Finding paths with minimum intersections

Given a graph and a set of origin-destination $<o_i,d_i>$ pairs. The goal is computing a set of paths such that every pair has a path and number of common vertices between paths is minimized. ...
0
votes
1answer
141 views

A directed graph colored path problem?

Given: A rooted, directed, a-cyclic graph $G$. Let $r_0$ be the root node and $t_0$ be another target node. Each node in $G$ is assigned a non unique id/color ($ID_i),\ 1<i<N$ for some integer N....
4
votes
1answer
41 views

Subgraph isomorphism on star multi-graphs with labelled edges

My approach to the problem has been to reformulate it into something more recognizable, but I don't know the best way to solve the reformulated problems either. I list the original problem, an example,...
1
vote
1answer
46 views

Markov Inequality in graph theory

Fix an optimal solution G∗ to k-Cycle-Free Subgraph. Partition the vertex set V of G randomly into two subsets, A and B, each of size n/2, and remove edges internal to A or B. In expectation, the ...
3
votes
1answer
39 views

(DROP) Data Reduction Algorithm - How it works?

I am studing a PHD framework which the propose is to reduce the dataset with the most representative samples for training a classifier. Maybe I am loosing something, but I could not undestand a ...
1
vote
1answer
31 views

Finding a minimum weight path with certain restrictions

I have a directed weighted multigraph whose vertices are sets of URLs. We add to this multigraph all edges of the form $i\to j$ where $i\subset j$ (such edges are of zero weight), where $i$, $j$ are ...
1
vote
2answers
19 views

Representing a network with two types of connections: A fishing application

I want to represent a fishing network using a graph representation. My question surrounds how I can write the adjacency matrix if there are two types of connections, which I want to capture together. ...
4
votes
1answer
22 views

How to identify named points by coordinates?

The problem: This is a reduced version of a problem I currently have. I have a list of edges as input. This list contains the names of 2 nodes (the edge connects these 2 nodes) and 2 x 2D coordinates (...
1
vote
2answers
36 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
58 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 ...
7
votes
0answers
58 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 ...
2
votes
2answers
80 views

Super-strongly connected components?

I face a problem that is related to (strongly) connected components. Let $G=(V,E)$ be an undirected graph. I want to find subgraphs $G_1,G_2, \dots,G_n$ of $G$ such that they do not overlap (i.e. ...
4
votes
1answer
50 views

Longest path with limited edge traversals

Given a graph where each edge has a capacity, is there an efficient algorithm to find the longest path in the graph which does not pass through an edge more times than its capacity? The exact problem ...
0
votes
0answers
26 views

L1 sampling for sampling edges of a graph

I am trying to sample the edges of an undirected graph using weights. The goal is to run a sparsification algorithm on the graph. I see the point that L1 norm is best for sparsification. Can someone ...
1
vote
1answer
24 views

Obtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching?

I have a graph with integer-valued edge weights (possibly negative) on which I would like to obtain a maximum-weight matching. However, I am using python-graph-tool, which only has max-cardinality ...
1
vote
0answers
32 views

Minimum weight Hamiltonian path on a weighted (0 and 1) tournament graph

Suppose we have a weighted tournament graph. (A directed graph in which every pair of distinct vertices is connected by a single directed edge.) The weights are constrained to be 0 and 1. I know ...