Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,796
questions
1
vote
1
answer
30
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
48
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
27
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
95
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
73
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
52
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
96
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
74
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
69
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
43
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
28
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
101
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
75
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
32
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
32
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}
IS = ...
- 53
1
vote
1
answer
53
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 $...
- 512
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
30
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 ...
- 23
2
votes
0
answers
82
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
44
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
70
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
0
votes
1
answer
24
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-...
- 1
0
votes
0
answers
35
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
120
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
56
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
51
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
189
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 ...
- 291
4
votes
2
answers
61
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
64
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
40
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
55
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
114
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
54
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 ...
- 125
2
votes
1
answer
60
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
45
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
2
votes
1
answer
114
views
Budgeted Independent Vertex Cover
Suppose that we are given a graph $G = (V,E)$ and a number $n$. The problem is to find an independent set $I$ with $|I| = n$, such that number of vertices covered by $I$ is maximized (that is, the ...
- 131
1
vote
0
answers
41
views
Dynamic Programming: Counting *cycles* consisting of distinct numbers
I was thinking about this question and thought about it for quite a while but couldn't come up with an answer.
Firstly, we fix two sets $R$ and $S$. We consider "cycles", which are tuples in ...
- 111
1
vote
0
answers
39
views
Finding maximal cliques in a graph represented as a collection of complete biparti graphs
I have a graph whose edges can be very efficiently represented as a set of complete biparti graphs (that may share nodes). Is there a name for such a representation?
And secondly. I want to enumerate ...
- 11
3
votes
1
answer
52
views
Partition a graph into connected subgraphs of 3 vertices each
We need to partition a graph into subgraphs of 3 vertices each, such that every subgraph has at least 2 edges.
The problem is similar to the partition into triangles problem (which is NP-complete) but ...
- 71
4
votes
0
answers
73
views
Constant factor approximation algorithm for Vertex Deletion version of Maximum Diameter Bounded Subgraph
I've been stuck with this problem for quite a while now, and after reading so many papers I'm unsure whether this is even possible.
The problem is quite simple:
Given $G = (V, E)$ an undirected graph, ...
- 41
0
votes
0
answers
30
views
Directed graph where each node must contain all elements from source nodes
I'm looking for a directed graph data structure where each node is unique and contains a set of elements (at least one).
Each node must contain all elements from nodes pointing to it so it possible to ...
4
votes
0
answers
175
views
Partitioning a graph into connected pairs and triplets
We need to partition an undirected graph into connected subgraphs of size between $2$ and $k$, where $k$ is an integer.
When $k=2$, the problem is equivalent to the perfect matching problem which is ...
- 71
0
votes
0
answers
20
views
Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds
Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system:
1: Assume that initially the nodes have IDs of size $\log(n)$ bits
2: The root is ...
- 305
0
votes
0
answers
17
views
Importance of an edge regarding distances
Given a graph $G=(V,E)$ and any edge $(u,v) \in E$, let us denote by $G_{(u,v)}=(V,E\setminus\{(u,v)\})$ obtained from $G$ by removing this edge.
I am interested in the difference between the average ...
- 623