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
3
votes
0
answers
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
0
answers
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
8
votes
4
answers
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
1
answer
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
3
votes
1
answer
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. ...
4
votes
0
answers
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
1
answer
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
3
votes
1
answer
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
3
votes
2
answers
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
2
votes
2
answers
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
9
votes
2
answers
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
1
answer
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
2
votes
3
answers
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
8
votes
2
answers
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
-2
votes
1
answer
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
15
votes
2
answers
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
1
answer
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
6
votes
2
answers
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
6
votes
1
answer
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
8
votes
1
answer
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
4
votes
1
answer
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 ...
- 43
8
votes
2
answers
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
4
votes
0
answers
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
13
votes
1
answer
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
0
votes
1
answer
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
6
votes
1
answer
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
2
votes
1
answer
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
2
votes
1
answer
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
5
votes
1
answer
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
2
votes
1
answer
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
9
votes
3
answers
6k
views
Maintaining an efficient ordering where you can insert elements "in between" any two other elements in the ordering?
Imagine I have an ordering on a bunch of elements like so:
Where an arrow $X \leftarrow Y$ means $X < Y$. It is also transitive: $\left(X < Y\right) \wedge \left(Y < Z\right) \implies \left(...
- 6,171
1
vote
1
answer
1k
views
Clarification sought for definition of a cut that respects a set A of edges in Graph Theory
From CLRS (3rd edition), I came have this question on page 626:
Given these definitions from the text,
DEFINITIONS:
Given an undirected graph G = (V,E),
1. A CUT (S ,V-S) of G is a partition of V,
...
- 11
15
votes
3
answers
548
views
Minimal size of contracting a DAG into a new DAG
We have a DAG. We have a function on the nodes $F\colon V\to \mathbb N$ (loosely speaking, we number the nodes). We would like to create a new directed graph with these rules:
Only nodes with the ...
- 203
2
votes
0
answers
80
views
Counting modified perfect matchings
Consider a bipartite graph with vertex set partitioned into $X=\{u_1,u_2,u_3\}$ and $Y=\{v_1,v_2,v_3\}$. Consider the graph has the following edges: $\{u_1,v_1\}$, $\{u_2,v_2\}$, $\{u_2,v_3\}$, $\{u_3,...
- 2,862
7
votes
1
answer
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
6
votes
2
answers
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
5
votes
1
answer
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
2
votes
0
answers
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
12
votes
2
answers
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
4
votes
2
answers
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-...
- 141
2
votes
0
answers
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
21
votes
5
answers
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
3
votes
1
answer
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
4
votes
1
answer
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
4
votes
2
answers
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
5
votes
2
answers
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 ...
0
votes
1
answer
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
0
answers
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
5
votes
1
answer
231
views
Complexity of finding a spanning tree that minimizes the maximum interference
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 ...
user9665
7
votes
1
answer
2k
views
Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph
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 ...
- 1,686