Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
3,804
questions
1
vote
0answers
27 views
“Second order” widest path problem
Let's say we have a directed graph in which each pair of adjacent edges has a weight; or, alternatively, each ordered triple of vertices A, B, C has a weight $W(A,B,C)$ of going A->B->C.
I am ...
0
votes
0answers
18 views
How can I examine the subnetworks of a nearly fully connected graph?
I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in R3 and each edge represents the distance between them with a ...
0
votes
1answer
49 views
Finding minimum possible cost of road network between cities with distance from capital condition
I have a graph G containing cities (vertices V) connected by distanced roads (weighted undirected edges E).
Characteristics of the graph:
Each city is connected to the rest of the graph
Each city ...
0
votes
0answers
12 views
How do I efficiently visualize subnetworks in a highly connected large graph? [closed]
I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in $R^3$ and each edge represents the distance between them with ...
0
votes
1answer
19 views
How to estimate the computational cost in a neural network?
Given a neural network(assuming no regularisation/dropout), I want to determine the computational cost of doing a forward and a backward pass of a datapoint. I want the measure to be of independent of ...
0
votes
0answers
32 views
Question regarding a particular type of graph
Let $G = (V,E)$ be a directed graph where every vertex is represented by an $n$ bit string. The edges are represented by two polynomial-sized circuits $S$ and $P$. There is an edge from $u$ to $v$ if ...
0
votes
0answers
26 views
Max flow but distribute evenly among candidate vertices
The max-flow algorithm finds the maximum flow through a graph given edge capacities. However, if there is an option between flowing through two edges, it will typically just leverage one of those ...
-1
votes
0answers
31 views
Partitioning graph into two parts with equal clique number
Prove that if the maximum clique size in a graph is even, then you can color the vertices of the graph in two colors so that the maximum clique sizes in the subgraphs induced by each of the color ...
2
votes
2answers
48 views
Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem
I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following:
There exists a believed-today NP-hard problem ...
0
votes
1answer
25 views
Find subgraphs that can only be reached by two nodes
I want to find subgraphs in a graph that are only connected to the rest of the graph by two nodes; for example, node A is connected to the rest of the graph, as well as node F, but nodes B-E are only ...
0
votes
1answer
22 views
Polynomial-time algorithm to solve the maximum vertex bipartite subgraph problem
I'm trying to find an algorithm that solves the maximum vertex biclique problem. I know that that algorithm can be solved in polynomial time (in contrast with the maximum edge biclique problem, which ...
0
votes
1answer
22 views
Generating topological sequence from DAG with additional “not appearing before” constraints
DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG?
Is there an algorithm for ...
3
votes
3answers
338 views
Forest characterization
Prove that each property below characterizes forests...
a. every induced subgraph has a vertex of degree at most one.
When proving a characterization, do we have to prove both directions, like an if ...
1
vote
0answers
23 views
Extremal graph. $2n$ vertices in which every subgraph of $n$ vertices has $k$ edges. Lower bound on the number of edges
Assume that a simple graph has $2n$ vertices and the property that every subset of $n$ vertices induces a subgraph with at least $k$ edges.
Question: What lower bounds are known on the total number of ...
0
votes
1answer
26 views
Bottleneck TSP with repeated nodes
I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also ...
-2
votes
1answer
135 views
maximum spanning tree in a complete graph
Given a complete graph how do I find maximum weight spanning tree.
where $weight(u, v) = \sum_{i=1}^{k} |w_{i,u} - w_{i,v}|$
assuming $k \lt 7$ and $n \le 500000$.
$n$ number of nodes
$weight(u,v)$ ...
0
votes
1answer
30 views
how to find all negative weight cycles(elementary circuit) in a strongly connected directed graph?
I can use Bellman-Ford to get some of the elementary negative weight cycles in a graph. It's not guaranteed to always get all of them.
(Elementary Cycle: A cycle is elementary if no vertex but the ...
1
vote
0answers
20 views
Partition graph in a way that minimizes inter-partition edges
I have a graph in which certain vertices are labeled. I need to assign labels to all of the other vertices in a way that minimizes the number of edges between different-label vertices.
How can I do ...
0
votes
0answers
28 views
Graph algorithm to group nodes by level and group size
I have a directed graph representing some topics organized as follows (below screenshot is a subset of the graph):
I'm looking for an algorithm to group a set of nodes (in blue in the diagram) ...
7
votes
1answer
195 views
Polynomial time algorithm for finding a maximal monotone subset
Input:
Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$.
Output:
A subset $I\subset\{1,\dots,n\}$ of maximal size such that
$(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$.
...
0
votes
1answer
51 views
What is the polynomial time reduction between these two Hamiltonian cycle problems?
Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle.
Problem 2: Given an undirected graph, decide whether or not the ...
0
votes
0answers
10 views
Ranking (k-best) or genetic coding for spanning arborescences
I am wondering if there is a simpler way to rank spanning arborescences or any way to code spanning arborescences genetically.
According to the comment by @BearAqua in my another question, min ...
3
votes
4answers
159 views
How to build a graph of people where node connections are determined by name and age?
I was given the following question (please don't mind the programming language semantics, it's a language-agnostic question):
Given a list of Persons, and two ...
0
votes
0answers
18 views
Time complexity for computing the highest degree vertex
Consider an undirected and unweighted graph with $n=|V|$ nodes and $m=|E|$ edges stored in adjacency matrix format.
What is the time complexity of finding the highest-degree vertex, assuming the ...
1
vote
1answer
38 views
How to find a cut in a graph with additional constraints?
I have a complete undirected graph $G=(V,E)$ with positive non-null rational weights $c:E \to \mathbb{Q}^+_{*}$ on the edges, such that $c(v,v) = 0$ for all $v$, and a subset $C \subset V$.
I would ...
0
votes
0answers
14 views
How to cluster a dataset in which each data point is composed of a set of 2-dimensional coordinates
I have a dataset with totally $1000$ scenarios, each of which is composed of $5$ users' coordinates $(x_i,y_i), \forall i \in \{1,\dots,5\}$. Now, based on users' coordinates, I want to cluster these $...
0
votes
0answers
13 views
Relationships between centrality metrics?
I am studying graph centrality, and came across a very nice table in here (reproducing it below, all credit goes to the original authors Shaikh Arifuzzaman and Md Hasanuzzaman Bhuiyan).
I have ...
0
votes
0answers
15 views
Various implementations of adjacency list representation of a Graph
Just started learning about graph and it's various representations (matrix and adjacency list). Now I found that the adjacency list representation can be implemented in various ways:
Array of arrays (...
1
vote
0answers
39 views
Oriented undirected edges in directed graph
I have a graph with $n$ vertices and $m$ edges. Some edges are already oriented, some are not. How do I determine how to orient all undirected edges so that each vertex has the same outgoing and ...
-1
votes
1answer
21 views
Checking whether there is cycle of odd length in a k-coloring undirected graph
Also, what is the meaning of the notation used in the question- c: v->{0,1,2....k-1} such that c(u)!=c(v)?
1
vote
0answers
16 views
Proof that “the last vertex in any postordering (in a DFS) of G lies in a source component of G”
From the book Algorithms (Jeff Erickson), there's a lemma that states:
The last vertex in any postordering of G lies in a source component
of G
My initial reaction to this was that the proof would ...
-2
votes
0answers
27 views
Š”yclic routes in the table
In a $n Ć m$ table, some cells are locked. How to determinate time whether it is possible to split the remaining cells into cyclic routes of length at least $3$? All unremoved cells must participate ...
1
vote
0answers
22 views
Can Johnson's algorithm for simple cycles be modified in order to find only cycles up to length L (but all of them)?
I have a question regarding Johnsonās algorithm for finding all simple cycles in a graph.
I was wondering it is possible to modify the algorithm in order to find only cycles up to a given length.
...
0
votes
0answers
38 views
Finding the smallest-cost way to deliver goods
I want to deliver products from various sources to various destinations such that the overall cost is minimized. We need to deliver these products while obeying our contractual obligatione with each ...
1
vote
1answer
94 views
Reducing a problem to the MST problem
Let $G = (V, E)$ be a connected, undirected graph. Given a subset of distinct vertices $S = \{v_1, v_2, \ldots, v_n\} \subseteq V$, how can I find a forest in which each vertex $v \in V - S$ is ...
4
votes
1answer
182 views
The same outgoing and incoming degree in graph
I have an undirected graph with $n$ vertices and $m$ edges. How to determinate in $poly (n, m)$, is it possible (and how is it necessary) to orient all the edges so that each vertex has the same ...
0
votes
1answer
47 views
Bipartite maximum matching with added constraints
Suppose you have two lists as follows
List $A$ = $(a_1, a_2, ..., a_m)$
List $B$ = $(b_1, b_2, ..., b_n)$
Each element in list $A$ can be paired with many or no elements in list $B$. I have a function ...
0
votes
1answer
42 views
3SAT and directed graph
Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x_{i}$ we have the nodes $x_{i}$ and $!x_{i}$; for each ...
6
votes
5answers
224 views
How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?
Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never ...
2
votes
0answers
20 views
Comparing Directed Unweighted Graphs with Different “Densities” [closed]
I'm looking to compare 2 unweighted directed graphs and get an (ideally differentiable) similarity score. Both graphs describe a trajectory in a 2d space.
The reference graph is a step by step guide ...
2
votes
0answers
22 views
How to calculate delta Q (modularity increase matrix) in graphs?
I've been trying to implement the Three-stage Algorithm to compare its results with our new proposed algorithm with different datasets than those mentioned in the article. I've succeeded in ...
3
votes
1answer
110 views
How to detect “tree-able” set-families?
A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
4
votes
1answer
181 views
Game on the graph with matchings
The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move ...
0
votes
0answers
29 views
Problem with the algorithm
I am trying to execute the following algorithm shown in the image from my course slide. I am trying to get the table shown in the image:
1st Iteration
L2: 1:CS=A, SL = A, NSL = A
L3: while NSL!=[]: ...
1
vote
1answer
18 views
Efficient calculation or estimation of āminimized combined Manhattan distanceā between two sets of points
Iām attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. Iām looking for options for a ...
-1
votes
1answer
14 views
Maximal vs maximum matchings
Let $M_1$ be an inclusion-maximal matching in $G$ (that is, there is no matching which strictly contains it), and $M_2$ a maximum-size matching in $G$. How to prove that $|M_2| \le 2|M_1|$?
1
vote
1answer
38 views
Independent sets into which all the vertices of the graph can be split
How to prove that if $G$ is an acyclic transitive digraph, then the least independent sets into which all vertices of G can be divided is equal to the size of the longest paths to $G$?
0
votes
0answers
11 views
Which algorithm suits best for AST pattern matching
I want to create a refactoring/analysis for java tool in Haskell.
I can write the monadic parser, but I don't have clarity about next steps.
I could express AST transformations via functions and built-...
0
votes
0answers
24 views
Set of cycles in directed graph
I have a directed graph. How to find in it some set of cycles that are pairwise
do not intersect, but cover the entire set of vertices, if a cycle from one vertex is not considered a cycle, but cycle ...
0
votes
1answer
20 views
Randomly generating graph based off number of connections on each node
I'm trying to generate a graph based off some data I have.
This graph should have N nodes where the number of edges each node has is equal to a random number ...
