# 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,848 questions
Filter by
Sorted by
Tagged with
36 views

### Complexity of Finding Every Cycle in a Graph?

What's the best asymptotic complexity of finding every cycle in a simple, directed graph? I haven't been able to find anything regarding this online. I'm able to use DFS for cycle detection, but I'm ...
47 views

### Diameters of isomorphic graphs

Is it necessary that two isomorphic graphs must have the same diameter? As far as I know, their adjacency matrix must be retained, and if they have the same adjacency matrix representation, does that ...
32 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 ...
33 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 ...
56 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 ...
24 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 ...
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 ...
61 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 ...
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 ...
27 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 ...
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 ...
23 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 ...
343 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 ...
26 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 ...
28 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 ...
155 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)$ ...
33 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 ...
21 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 ...
30 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) ...
205 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$. ...
54 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 ...
11 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 ...
161 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 ...
25 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 ...
39 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 ...
14 views

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