Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,852
questions
0
votes
0
answers
42
views
Algorithm for leader election in synchronous ring with a known network size $n$ with phases of length $\frac{n}{m}$
Consider the following leader election algorithm election of a synchronous ring with a known network size $n$ (simultaneous wakeup and uni-directional communication):
The leader is the node with the ...
- 315
3
votes
1
answer
93
views
Path planning on 2D grid graph to maximize the neighboring grid points of a path: Can we do better than brute DFS?
On a finite 4-connected grid graph, given the source point and destination, it is allowed to consecutively move in one of the four orientions (up, down, left or right) to form a path. We get 1 bonus ...
- 31
2
votes
1
answer
51
views
Find directed spanning tree of unweighted directed graph in $O(|V| + |E|)$
A directed tree (also called an arborescence) of $G$ is a directed subgraph of $G$ in which there exists a vertex $v$ such that there is a unique path from $v$ to every other vertex in the graph.
...
- 237
2
votes
1
answer
125
views
Fast $k$-clique checking algorithm?
I have a problem where part of it requires answering the question: does graph $G=(V,E)$ contain a clique of size at least $k$?
Obviously, answering this question is a NP-Complete problem. I am no ...
- 121
2
votes
0
answers
43
views
Has Triangle Finding ever been faster than Matrix Multiplication?
The Triangle Finding problem (TF) in Graph Theory was shown by Itai and Rodeh in 1977 [1] to be solvable as fast$^1$ as Boolean Matrix Multiplication (BMM, Matrix Multiplication over $\{0, 1\}$ with ...
0
votes
1
answer
52
views
Is the set of all duals same as the set of all planar graphs?
Let $P$ be the space of all possible planar graphs.
Fact: A planar graph may have multiple duals based on its embedding.
Let $D_p$ be the set of all possible duals of a planar graph $p\in P$
Let $S$ ...
- 73
1
vote
0
answers
66
views
Enumerate faces in any one embedding of a planar graph
Given: A planar undirected connected graph $G$ in which degree of every vertex is $2$ or more.
Fact: A planar graph can have multiple planar embeddings.
Question: Give an efficient algorithm to find ...
- 73
0
votes
1
answer
61
views
Checking if all nodes are reachable in a oriented graph from all other nodes
I'm having a lot of troubles understanding a preparation exercise about oriented graphs:
Consider the following game played on a directed graph G = (V, E) with
n nodes and m edges. A pawn is ...
- 103
1
vote
1
answer
45
views
Showing that nearly regular graphs have a specific $(2,O(\log n))$ ruling set with high probability
An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that ...
- 315
1
vote
1
answer
46
views
How to express that a graph has Independent set of size at least $n/2$ in $\exists SO$
I am looking to provide a formula saying "A graph with $n$ vertices has an independent set $X$ of size at least $n/2$" in existentional second order logic.
(This is exercise 1.2. from Libkin'...
- 267
2
votes
1
answer
52
views
Algorithm to identify common subsets
Given a large dataset $D$ and multiple sets of filters that can be applied to $D$, e.g.
$setA = \{filterOnColorRed\}$
$setB = \{filterOnAgeGreaterThan20\}$
$setC = \{filterOnColorRed, ...
- 121
1
vote
0
answers
30
views
Ramanujan graph girth comparision
I am working on Ramanujan graphs and have encountered something that needs a suggestion. Does the girth of a Ramanujan graph change if I delete one random edge from the graph? The question can also ...
- 162
0
votes
0
answers
39
views
Graph Search Algorithms that are practically fast on dense graphs
I'm trying to do some research on graph search algorithms that are practically fast on relatively dense graphs. Besides the common ones like A* or Dijkstra's, what are some graph search algorithms ...
1
vote
1
answer
45
views
Super graph restriction based on girth
Let $n$ be the minimum possible size of a 4-regular graph with girth $g$. Consider a graph with a minimum degree of at least four with girth $g$, can I say that the size of such graph must be at least ...
- 162
2
votes
0
answers
99
views
On definitions of graph width
Wikipedia shows graph width $k$ as the degeneracy, an ordering of the vertices $v_1,\ldots , v_k$ for which, if we orient each edge $(v_i, v_j)$ towards $i$ where $i<j$, the maximal degree is at ...
- 435
2
votes
1
answer
76
views
How to reduce $k$-oriented problem to max flow problem?
Given an undirected graph $G$, how to reduce this problem :"Judge whether every edge of $G$ can be given a orientation such that for every vertex $v$ in $G$ has input-degree of at most $k$" ...
- 123
2
votes
0
answers
54
views
Shortest path algorithm for longest path problem?
A central insight of Dijkstra's shortest path algorithm is that every subpath of the shortest path is also the shortest path of the subgraph. But is that also true for the longest path? In particular, ...
- 1,006
0
votes
1
answer
101
views
How to find maximum number of edge-disjoint trails of length $k$ of a directed multi-graph $G=(V,E)$ between arbitrary start and end vertices?
How to find and return the maximum number of edge-disjoint trails of equal length $k$ of a directed weighted multi-graph $G=(V,E)$ between arbitrary start and end vertices? The start and end vertices ...
- 11
2
votes
0
answers
75
views
Distribution of $k$-matchings in a random graph
Take the Erdos-Renyi random graph $G(n,p)$, i.e. the random graph with $n$ vertices and where each possible edge has an independent probability of $p$ of being present. Recall that a $k$-matching is a ...
1
vote
0
answers
32
views
Maximum size of a graph with given girth
I am unable to get the bound on the maximum size of a graph of order $n$ with girth $g$. Is there any literature regarding this. I know that there is an asymptotic bound on the size of a graph $G$ ...
- 175
0
votes
1
answer
77
views
On hardness of finding total dominating sets in triangle-free graphs
A total dominating set $S\subset V(G)$ is a set of vertices such that $\forall v\in V(G)$, $v$ has a neighbour in $S$. The minimum total dominating set of $G$ is a total dominating set of $G$ of ...
- 25
0
votes
0
answers
46
views
How hard is it to find a spring network configuration with the lowest energy?
Given a spring system:
where the total tension between the nodes should be minimized, it seems possible that a physics simulation of this graph does not arrive at the lowest energy state, getting ...
- 191
1
vote
1
answer
30
views
Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?
Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?
I am trying to write a program to analyze Java programs and figure out the
transitive closure of the ...
- 125
2
votes
1
answer
107
views
On hardness of finding dominating sets in triangle-free regular graphs
A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices ...
- 25
0
votes
1
answer
158
views
Minimum dominating set on trees
I am working on an NP-Complete problem, i.e., the dominating set. Given a graph $G = (V, E)$, a set $S$ is a dominating set if every vertex $v \in V \setminus S$ has at least one neighbor in $S$. I am ...
- 162
0
votes
0
answers
34
views
Algorithm to maximize generated maze score
I need to generate maze with 100x100 rooms. Each room connected only with 1 other room.
Here are example of correct 2x2 mazes:
+-+-+
|...|
+-+.+
|...|
+-+-+
And ...
- 1
1
vote
1
answer
44
views
What are the necessary requirements for proving NP is closed under complement?
I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why.
$VC = \{<G,k> |\ G =$ undirected graph with a vertex cover of size $k\...
- 53
1
vote
1
answer
81
views
Finding shortest path between two points in a polygon whose vertices are given?
A contiguous single polygon is specified by it's vertices $(v_1, \ldots, v_n)$, given in order such that the line between $v_i$ and $v_{i+1}$ is an edge of the polygon (there's also an edge between $...
- 532
3
votes
1
answer
50
views
How to determine the largest number of disconnected arcs in a graph?
Given a directed graph $G=(V,E)$, I'm wondering if there's a way to determine the largest size of a set of edges that are disconnected pairwise. There is a similar problem for vertices (Maximum ...
- 31
0
votes
1
answer
32
views
How to generate all the possible nodes inside a polygon, if the polygon is represented by its vertices
If a polygon is represented by its vertices(latitudes, longitudes), is it possible to find all the possible points or nodes(latitudes, longitudes). If so, what kind of algorithm is used. The polygon ...
- 3
0
votes
0
answers
14
views
Is there a mathematical classification of formal languages for denoting graphs as a sequence of finite symbols?
I believe a general or pure definition of a “graph” in mathematics can be from algebraic topology, where a graph can be more abstractly seen as a simplicial complex, or a cell complex, or with scheme ...
- 123
2
votes
0
answers
87
views
Finding a connected subset of edges with minimal sum of weights for a distributed network
Let there be $n$ processes in a general connected network with no leader such that each process has a distinct UID.
Each edge has a weight , with weights being positive or negative.
Assume that each ...
- 232
0
votes
1
answer
46
views
Bounded clique width graphs vs parameter clique width
I am Balchandar Reddy, a research scholar. I am currently working on the parameterized complexity of a problem for the parameter clique width. The problem is known to be polynomial-time solvable on ...
- 162
2
votes
1
answer
74
views
Algorithm to find intersection between collection of sets
I have two dataframes representing products two distributors sell. They look like this:
df1 for distributor 1.
...
- 280
1
vote
1
answer
30
views
Are there pairs of connected graphs that always fail the k-wl test for any k?
Is there a pair of connected graphs for which the k-wl test always fails (= judges isomorphic when not isomorphic) for any k? If so, please give an example.
How about the following image? Are they non-...
- 11
0
votes
0
answers
36
views
how to find the right path for A* algorithm (not the real time algorithm)
Hey to everyone I am trying to understand A* algorithm not the real time A* algorithm
To understand this I created the following problem
Node s is connected with Α and the heuristic value of Α is 4 ...
- 1
1
vote
0
answers
344
views
Find the number of all possibilities to visit all vertices once in a connected graph
Let $G$ be a connected undirected graph, e.g.:
u -- v -- w
\ /
x
I would like to determine the number of sequences in which every vertex of the graph is ...
- 151
3
votes
0
answers
58
views
Is there a decomposition/structural theorem for 3-edge-connected graphs?
A graph is 2-edge-connected if and only if it has a closed ear decomposition.
I am looking for such a theorem for the 3-edge-connected case. Unfortunately, I have not been able to find one. Is there ...
- 65
1
vote
0
answers
101
views
Page Rank Formula for dead end
I am trying to understand this, especially the last page. For calculating the Page Rank we can use the following formula for matrices:
$$
A = \beta M + (1 - \beta) \left(\frac{1}{n}\right)_{n \times n}...
- 121
1
vote
1
answer
195
views
How to turn a 3D polytope into a mesh?
Let us say you have a polyotpe define as the intersection of halfplanes. That is you are given N half-spaces. The polytope is the volume defined by all points which lie on the positive side of all N ...
- 331
4
votes
2
answers
109
views
Single Source Shortest Path Problem with Multiple Weights Each Edge
I am trying to solve the single source shortest path problem, but with the added constraint that there is an additional weight on each edge (so we have two weights in total for each edge, call them p ...
- 149
0
votes
1
answer
69
views
Finding the first vertex in a recursively growing graph
I have an undirected graph which grew according to a recursive algorithm, i.e., it started with a single vertex and then, one after another, new vertices arrived and connected to existing ones.
Now, I'...
- 151
0
votes
0
answers
25
views
Find maximum sum of K elements in a graph with unary and binary terms
I have an algorithmic problem that I managed to reduce to the following form:
Given a graph with $N$ elements, select exactly $K$ elements to maximize the following:
$$
\max \Sigma_{k \in K} V(S_k) + \...
- 1
1
vote
0
answers
41
views
Show that the graph on 99 vertices cannot be divided into two classes
In a graph with 99 vertices, two vertices have a degree of 3, and the degree of the other vertices is 4. Show that the graph contains an odd cycle.
I figured I have to show that the graph cannot be ...
0
votes
2
answers
59
views
Can negative edge weights in a graph be positive numbers?
I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to ...
- 149
5
votes
1
answer
131
views
Let the vertices of the graph G be the numbers 1, 2, ..., 100, a. Determine χ(G), the chromatic number of the graph G
Let the vertices of the graph G be the numbers 1, 2, ..., 100, and two (different) vertices be adjacent if and only if at least one of 2, 3, or 5 is a common divisor of the respective numbers. ...
1
vote
1
answer
61
views
Clarifications about tree-width definition
I have read the definition of treewidth/tree-decomposition both in Wikipedia and in here:
https://medium.com/@karlrombauts/treewidth-how-all-graphs-are-trees-in-disguise-ec699b69e2fb
I'm finding ...
2
votes
1
answer
65
views
Creative solving of searching redundant connection in graph
I am trying to solve problem in leetcode:
https://leetcode.com/problems/redundant-connection/description/
*finding redundant connection in undirected graph
And now I am writing a solution, inpired by ...
- 23
0
votes
0
answers
12
views
Existence of a Path from Initial to Accepting Configuration in Turing Machine Runs: A Reduction-Based Proof
Is it possible to show, by reduction(Reduction in the length of the path and the running time), that for a Turing machine M and an input X, there exists a run in which M accepts X if and only if there ...
- 1
0
votes
0
answers
59
views
Efficient Algorithm To Find A Path Which Covers Maximum Area Along Polygonal Perimeter For Surveillance Application
In the context of surveillance, I am working on a project where the goal is to find an algorithm that determines a path along a polygonal area, connecting a root node to a target node, while ...
- 3