As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

4,715 questions
Filter by
Sorted by
Tagged with
822 views

### DAG Minimum Path Cover in O(nlogn)? [closed]

I asked this question on stackoverflow, but was suggested to post to same here. So here goes. The following problem was asked in the recent October 20-20 Hack on Hackerrank : Evil Nation A is ...
• 273
1 vote
2k views

### Traveling Salesman with Held and Karp Algorithm

I am well aware of the DP solution to the traveling salesman problem; also known as the Held and Karp algorithm for TSP. I have implemented it with bitmask, and it's something like this: ...
• 11
1k views

### Negative weight cycle vs maximum weight cycle

I'm having trouble understanding why it's easy to detect negative-weight cycles (Bellman Ford) but hard to find the maximum weight cycle in an undirected graph. If we negate the weight of each edge, ...
• 181
1 vote
2k views

### Calculating the number of non-intersecting routes in an Euclidean graph

I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I found a geometric proof that every optimal TSP solution ...
• 899
142 views

### Unranking paths in a graph/lattice

A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified rank. ...
382 views

### Is there a relationship between graph entropy and node entropy?

Eagle, et al [1] discuss the notion of node entropy and this is captured in igraph via the diversity metric. I was wondering if there was any relationship between these node entropies and the idea of ...
• 141
1 vote
75 views

### A technical clarification on subgraph isomorhism

Let $G$ be a graph on $|\mathcal{V}(G)|$ vertices. If $H$ is another graph that contains a clique of size $|\mathcal{V}(G)|$, then does it mean $G$ is subgraph isomorphic to $H$? Does this mean that ...
• 2,862
6k views

### Efficient way to find intersections

I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I am randomly creating a path thru all the vertices and I ...
• 899
972 views

### Solve parity game in polynomial time?

Is it possible to solve a parity game in polynomial time? If yes, how? If no, why not?
• 351
2k views

### Prove that any directed cycle in the graph of a partial order must only involve one node

So I have the question: Prove that any directed cycle in the graph of a partial order must only involve one node. So I know that a partial order must be transitive, antisymmetric, and reflective, ...
• 47
545 views

### Software for testing graph homomorphism

I have graphs $G_k$ and $H_k$ with $|\mathcal{V}(G_k)|=|\mathcal{V}(H_k)|^{2k}=n^{2k}$ with $k\in\Bbb N$ that pass sanity checks such as no-homomorphism lemma. Are there free and easy to use tools to ...
• 2,862
1 vote
271 views

### Converting graphs to sets of paths

I have an Euclidean, undirected graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. The number of vertices with no edges is small ...
• 899
871 views

### Direct reduction from Near-Clique to Clique

An undirected graph is a Near-Clique if adding one more edge would make it a clique. Formally, a graph $G=(V,E)$ contains a near-clique of size $k$ if there exists $S\subseteq V$ and $u,v\in S$ ...
• 31
366 views

### Courcelle's Theorem: Looking for papers

I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth. I am only a beginner ...
• 534
247 views

### Sort edges in euclidean graph

Given a euclidean graph $G$ and a node $p$ with edges to all the other nodes, is there a more efficient solution than $O(NLog(N))$ to output all the edges to $p$ in sorted order?
• 899
3k views

### Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)? For ...
• 6,171
1 vote
2k views

### Approximated TSP: weight of minimum spanning tree less than cost of the optimal tour?

In the chapter, Approximation Algorithms of Introduction to Algorithm, 3rd Edition, for the approximation problem Travelling Salesman Problem, the author proposes a approximation method that first ...
• 335
2k views

### Points-in-a-plane from HackerRank

I've been struggling with this problem for days now, making no progress: There are N points on an XY plane. In one turn, you can select a set of collinear points on the plane and remove them. Your ...
• 203
954 views

### Find equidistant triplets in a tree

Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between ...
• 111
133 views

### Is the per-vertex error over a PageRank iteration monotonically decreasing?

It seems to me that taken over the entire graph, the norm of the error vector must be monotonically decreasing, otherwise we couldn't guarantee that PageRank would ever converge. However, is the same ...
• 265
6k views

### A* to find the longest path in a directed cyclic graph

I have written an A* algorithm to find the shortest path through a directed cyclic graph. I am trying to modify it to find the longest path through the same graph. My attempt was to write it so that ...
15k views

### Shortest path that passes through specific node(s)

I am trying to find an efficient solution to my problem. Let's assume that I have positive weighted graph G containing 100 nodes(each node is numbered) and it is an ...
• 381
204 views

### Graphs invariant to permutations of vertices

I am reading a paper on Semi Supervised Learning and I am confused about a term. The paper talks about graphs that are invariant to permutations of the vertices. Can somebody explain or perhaps give ...
• 231
13k views

### How to reduce the number of crossing edges in a diagram?

I am working on a diagram editor. Diagrams display 2D shapes (nodes) connected with connectors (edges). I'd like to add an operation that, given a selection of nodes, "disentangles" them: it ...
• 5,189
451 views

### Reducing states of a GTG

I used this generalized transition graph with 3 states and got an equivalent generalized transition graph with 2 states: GTG: Equivalent with 2 states: I'm not sure about the regular expressions ...
• 209
4k views

### Running Floyd-Warshall algorithm on graph with negative cost cycle

I am trying to find the answer to the following question for the Floyd-Warshall algorithm. Suppose Floyd-Warshall algorithm is run on a directed graph G in which every edge's length is either -1, 0, ...
• 115
121 views

### Is there a graph product that is multiplicative in independence number?

I know that Stable set cannot be approximated to constant factor. I saw a simple proof using OR product sometime back. I am unable to recall it. If anyone here knows what I am talking about could help ...
• 2,862
126 views

### What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?

Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero ...
• 21
801 views

### An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

Is there an incremental directed graph data structure that has the following properties: Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper data-...
• 6,171
80 views

### a jigsaw problem: recreating a subgraph from a limited number of fragments on an original graph

Suppose I have a set of small subgraphs $A=\{G_i\}$ of an original directed acyclic graph $G$, typically $|G_i| \ll |G|$, which together span the original graph $$G= \bigcup_i G_i$$ My question is ...
• 131
6k views

• 2,862
1k views

### Approximation algorithm for Feedback Arc Set

Given a directed graph $G = (V,A)$, a feedback arc set is a set of arcs whose removal leaves an acyclic graph. The problem is to find the minimum cardinality such set. I want to find out about is ...
• 73
2k views

### Find a simple path visiting all marked vertices

Let $G = (V, E)$ be a connected graph and let $M\subseteq V$. We say that a vertex $v$ is marked if $v\in M$. The problem is to find a simple path in $G$ that visits the maximum possible number of ...
• 1,525
203 views

### What is the optimal solution to prove the reachbility of a node from the root?

I have a finite automaton with these properties: Contains cycles It's a directed graph All the states/nodes are initialy reachable from the initial state It has final states but I guess it isn't ...
• 181
82 views

### Finding embedded DAG in another DAG based on colors

I am looking for some graph theory concepts and definitions around embedding a DAG into another DAG. I could only find a few lines on Wikipedia around this so I wonder if someone can help me find ...
• 131
2k views

### Simple graph canonization algorithm

I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if ...
• 1,505
3k views

### Shortest Minimax Path via Floyd-Warshall

I am trying to modify the Floyd-Warshall algorithm to find all-pairs minimax paths in a graph. (That is, the shortest length paths such that the maximum edge weight along a path is minimized.) Floyd-...
74 views

### Which component sizes do we observe while randomly deconstructing a tree?

Suppose I have a connected graph with $n$ vertices and $n−1$ edges, that is in form of a tree. Now, I will add the number of vertices in the tree and uniformly randomly select a vertex. I break the ...
• 101
50k views

### What is the significance of negative weight edges in a graph?

I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles. ...
• 377
16k views

### Time Complexity for Creating a Graph from a File

Assume that I have a file that consists of pairs of numbers separated by a space. These numbers are the labels for vertices in my graph. For example: ...
• 133
14k views

### Where are back edges in a DFS tree?

As I understand it when doing a DFS run when every new node is discovered and edge is added to the DFS tree from the parent of the new node to the new node. If that's the case how are back edges are ...
• 216
378 views

### Number of 5-cycles and 6-cycles in a simple graph

Is there any formula for computing the number of 5-cycles and 6-cycles in a simple undirected graph?
• 41
204 views

### Complete graph invariant

Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph ...
2k views

### Algorithm for Graph merge and recompute

I want to construct a complete graph where each node is connected to every other node. The link between the nodes give a distance function (does not follow triangle inequality) between them. What I ...
• 109
1 vote
46 views

### Is there a word/name for the node(s) in a graph with the minimal cumulative path length to a set of other nodes?

In other words, given a graph with nodes $N=\{n_0,n_1,...,n_j\}$, and a set of nodes in the graph $M=\{n_a,n_b,...,n_k\}$ with $M\subseteq N$, I'm looking for what to call the node or nodes $n'$ which ...
• 111
Given $n$ nodes in the plane, connect the nodes by a spanning tree. For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning ...
Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes. I tried to look it up at a few places (including ...