Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,645
questions
1
vote
0
answers
17
views
Finding the shortest path with Bellman-Ford [duplicate]
I feel this is a basic question but have been stuck at this for days. Consider an undirected graph with positive weights on its edges. The goal is to find is to get the shortest path between any two ...
- 257
1
vote
1
answer
24
views
How to generate all possible colour vectors generated by greedy colouring on a graph?
How to generate all possible color vectors that could be generated via greedy coloring.
- 300
0
votes
0
answers
40
views
Budgeted min cost max flow in bipartite where the flows must also be a matching set
I'm trying to find a problem description that is roughly akin to a budgeted min-cost max-weight bipartite matching where the capacities are greater than 1. Imagine a max-flow problem on a graph that ...
0
votes
1
answer
40
views
Correct Term for describing "diamond" subgraphs in a Directed Acyclic Graph
I am trying to research handling a specific type of possible subgraph in directed acyclic graphs.
However, I am struggling to find the correct term to use.
If we consider the subgraph S to be in a DAG ...
- 9
1
vote
1
answer
19
views
Route planning on line segments which can be connected or not
I have several lines that are shown in different colours, do not know which are connected to each other in advance. I want to do path planning only using these lines, i.e., route planning. If I am ...
- 111
0
votes
1
answer
63
views
Is maximal independent set on maximal planar graphs still NP-complete?
We know that finding the size of the maximal independent set of a planar graph is NP-complete. I'm curious about whether it remains NP-complete for maximal planar graphs, i.e., the graphs in which ...
- 15
0
votes
0
answers
49
views
Degree of a vertex
We have an undirected graph $G = (V,E)$ and let $|V| = n$.
Suppose edges of a graph are coming in a stream and the clustering is done in the following way. Here $N(u)$ denotes the neighborhood of ...
- 43
1
vote
1
answer
62
views
Can we prove the greedy algorithm archives 1.5-approximation for the Minimal Dominating Set Problem?
The following approximation algorithm for the Minimal Dominating Set Problem is said by a fellow student to be a 1.5-approximation:
Start with empty set $S$
As long as not all vertices are covered:
...
- 13
1
vote
0
answers
28
views
what is the worth of non-read once Branching Programs?
In Harvard CS 221 Computational Complexity, Lecture 3, it introduced Branching Programs
A branching program is a DAG that
has 1 start node and 2 output nodes with out-degree 0, labelled 0 and 1. Each ...
- 176
0
votes
0
answers
35
views
Algorithm for detecting if H is a induced subgraph of G in O(n)
Say that I am given a graph $H$ and a graph $G$ where the maximum degree of $G$ is known. How can I use BFS to find out if $H$ is an induced subgraph of $G$ in $O(n)$ time?
My current take is the ...
0
votes
0
answers
11
views
Trying to figure out how to model the structure of a multilingual dictionary for several constructed languages (basically Wiktionary for my conlangs)
Okay, so, this will be quite a bit, sorry. I'm working on several constructed languages for a worldbuilding project. Up until this point, I have been using a spreadsheet to store the vocab; each row ...
- 1
1
vote
2
answers
46
views
How much does proving that a special case of a problem is NP-complete tell me about if the general problem is NP-complete?
Define a graph problem as follows. Given a graph $G$ and
two integers $c$ and $k$, delete $k$ nodes and all edges incident to them, such
that, in the remaining graph, every connected component has at ...
0
votes
1
answer
31
views
Is there an algorithm to test for an acyclic undirected graph, using edge data, not node data (e.g. adjacency matrix)
Given an adjacency matrix or other data based on the nodes, there are many algorithms for determining whether the graph is acyclic (e.g. row reduction or leaf trimming).
If I have only a set of edges (...
- 257
1
vote
0
answers
34
views
Why does greedy approach of constructing De Bruijin Sequence work?
I have recently discovered a greedy algorithm to construct De Bruijin Sequence.
The greedy approach (prefer-largest specifically) works like the following:
Start with a sequence of all 0's of length ...
- 11
3
votes
1
answer
86
views
Find the largest caterpillar subtree
I have a problem to solve, but I am having some issues with it...
Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree ...
- 31
1
vote
0
answers
71
views
Topological sort of DAG that minimizes maximum number of unique-source-edges crossing through any node when placed in 1-d line
Consider a DAG such as one shown below:
How do I find a particular topological order of nodes, such that when the nodes are placed in a straight line, the maximum number of unique-edges that cross ...
- 260
0
votes
1
answer
41
views
Minimum number of skips needed for shortest path
In a directed, weighted graph with non-negative weights we are asked to find a path from a starting node s to node t that weights $\leq W$. In our given graph there is no such path but we have the ...
- 37
0
votes
0
answers
11
views
Generating a network with a certain value of correlation between node attributes
I have a graph $\mathcal{G}$, and a probability distribution, $f_X(x)$, (let's say $x\in[-1,1]$). I want to assign a random variable $x$ to each node of the graph.
So far so easy.
But I want the ...
1
vote
1
answer
148
views
How to determine if a set of edges is an edge cut of a graph?
An edge cut of a graph $G$ induced by a partition of $G$'s vertices into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$ and another endpoint in $Y$.
An edge separator is a set of ...
- 141
1
vote
1
answer
32
views
Add minimum numbers of edges to the graph for the existence of an eulerian path
Question is add minimum number of edges so that this given graph consists an eulerian path (but not necessarily an eulerian circuit). Why do edges less than these given edges won't suffice?
As I ...
- 13
2
votes
1
answer
58
views
Turning an undirected graph into a directed graph such that in-degree of all nodes is at most 1 or show it is not possible
I was thinking what if you just started with the node with lowest non-zero degree $u$ (only count undirected edges) and picked random edge that is connected to that and direct that inwards. EX: ...
- 21
2
votes
0
answers
21
views
Topologizing boundaries in 3D space
I have a set of closed curves (not convex, not planar) in 3D.
The goal is to produce A mesh (any will do) that is manifold and contains the closed curves as boundaries/holes.
For example like this ...
- 143
2
votes
0
answers
20
views
Algorithm for finding an embedding of a cover diagram
I am making some notes on order theory for my own self study (and certainly anyone else that wants to read them).
I'm impressed with what mermaid can do out of the ...
- 125
1
vote
2
answers
33
views
Special arcs - graph traversal
question is:
given an unwighted nondirected graph G=(V,E) portrayed as an adjacency list,
a special arc is defined as an arc (u,v) where both u and v has the same distance from source vertex s.
i ...
- 11
0
votes
1
answer
28
views
Which algorithm solves the single-pair shortest path in a weighted directed cyclic graph?
I need to find the shortest path between two nodes in a directed, positively weighted graph that migt contain cycles. All weights are either zero or one. If it was not weighted, I'd use breadth-first ...
- 3
0
votes
1
answer
34
views
Calculate all distances in an undirected and unweighted graph
Which algorithm do I use and how much does it cost if I have to:
Calculate all distances in an undirected and unweighted graph from two sources to all nodes.
I think the most appropriate algorithm is ...
- 111
1
vote
2
answers
81
views
Algorithm for finding a path in a directed graph that visits each node in a given subset
I was wondering about a solution for the following problem:
Given a directed graph $G=(V,E)$ and a subset of vertices $U \subseteq V$ suggest an algorithm that finds if there is a directed path that ...
- 129
0
votes
0
answers
18
views
Showing that the max-flow min-cut theorem holds for negative capacities as well
I want to show that the max-flow min-cut theorem still holds for a graph or network with non-positive capacities for edges as well. I was thinking I could just flip the edges and thereby flip the ...
0
votes
1
answer
34
views
Directed weighted multigraph with dynamic edges - shortest path
I need to create an implementation of a directed weighted multigraph with dynamic edges:
The edges will be changing during the pathfinding, in the following way:
Summary of the pathfinding:
...
1
vote
1
answer
21
views
Can Sutner's (1991) quadratic algorithm for testing reversibility of Cellular Automata be applied to 1-D CA with even sized neighborhoods?
Admittedly I haven't fully wrapped my head around the paper yet, but I'm curious if this algorithm can be adapted to say, a one dimensional cellular automata with two states, and an even sized ...
- 153
0
votes
1
answer
37
views
Confusion about adjacency list graph representation
From my understanding, the general implementation of an adjacency list is using a hashtable with vertices as keys and linked lists to as values in the hashtable to represent the adjacent vertices of ...
0
votes
1
answer
15
views
If a graph is not 3-COLORable, then there are at most 2 Independant Sets in G?
Assuming $G=(V,E)$ is a 3-colorable graph, then there are 3 disjoint independent subsets of $V$: $S_1,S_2,S_3$ such that $S_1 \cup S_2 \cup S_3=V$, by taking each $S_i$ to include the vertices of ...
- 37
1
vote
1
answer
55
views
Infinite Graph with Finite Degree
Let $G$ be an undirected graph with an infinite number of vertices (and edges), and assume it is connected in the sense every $u,v$ have at least one path connecting them. Assume each vertex has a ...
- 494
0
votes
0
answers
13
views
least collection of node disjoint paths that cover a given set of vertices
Given a directed graph G (with cycles) with source and target, and a set of interested vertices S.
we want to find a small n collections of vertice-disjoint-paths (path only have common nodes in ...
1
vote
1
answer
35
views
Is deciding whether a graph admits two vertex-disjoint spanning trees of bounded size difference NP-hard?
I'd like to decide whether, given a connected graph $G = (V, E)$ and an integer $k$ as input, $G$ admits two vertex-disjoint subgraphs $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ such that $T_1$ and $...
- 665
0
votes
0
answers
9
views
fault-tolerant K-median problem on an undirected graph
We know that the K-median problem is proved to be NP-Hard. In fault-tolerant K-median problem on an undirected graph $G=(V, E)$:
We are given a set of facilities $F\subseteq V$ and a set of demands (...
- 1
0
votes
0
answers
22
views
Network Flow - qualities of saturated edges
While I know that every edge is fully saturated in every min-cut of a network flow, I'm trying to get some intuition when the converse is true.
I can find an example using edges with infinite capacity,...
- 1
0
votes
1
answer
50
views
Complexity of counting odd node in an undirected graph?
I want to know if there exist a algorithm to efficiently compute the number of odd vertex in an undirected graph?
A graph vertex in a graph is said to be an odd vertex if its vertex degree is odd, ...
- 55
1
vote
1
answer
45
views
Find the shortest distance path in a weighted graph, where the weight of each edge is non-negative and less than a constant C = 500 in linear time
The problem is to find the shortest distance in a weighted graph, where the weight of each edge is non-negative and it is given that the weight of each edge is less than a constant C. For example, C = ...
- 25
2
votes
1
answer
36
views
What is the proper way to write logic formula, say concerning graph theory?
Say for example I'd like to state that there exists a pair of vertices such that they form an edge in one graph but not some other graph. I'd go about it as follows:
$$ \exists u, v \in V, (u,v) \in G,...
- 665
2
votes
1
answer
55
views
Find if there is more than one path between two vertices such that no vertices are used more than once
So I have an undirected graph G(V, E). We may assume there is always at least one path between any two vertices. I want to efficiently check if there are at least 2 different paths between x and y ...
- 21
0
votes
0
answers
13
views
Does plantri software provide the option to screen out abstract non-isomorphic graphs
This may be off topic, but I still want to find a solution.
The plantri software can generate planar graphs, but it may result in abstract isomorphism when generating planar graphs with a connectivity ...
- 141
0
votes
1
answer
25
views
Given a graph `G`, what is the maximum number of "minimum" cycles it could have?
In graph G: a cycle $A$ is a subcycle of cycle $B$ if there exists vertices $c$ and $d$ such that:
$cd$ is an edge of $A$.
$F$ is the resulting path of $A$ after ...
- 411
1
vote
0
answers
76
views
Successive shortest paths with fixed costs and costs per unit
I have a directed graph $G(V,A)$ with arc costs $c_{ij} = \alpha_{ij}1_{x_{ij}>0} +\beta_{ij}x_{ij}$, where $\alpha_{ij}$ and $\beta_{ij}$ are, respectively, a fixed cost and a cost per unit of ...
- 111
0
votes
0
answers
20
views
Observing when DFS outperforms IDS
I was thinking of a case where an IDS (Iterative Deepening Tree) always performs worse than a DFS (Depth-First Search). I have seen on numerous sources the example of a linked list(i.e. each node has ...
1
vote
1
answer
73
views
Set of all vertices in a directed tree that are within distance of strictly larger than 2
As the title says, I'm trying to solve the question where:
Input: A directed tree $T = (V, E)$.
Output: The maximal subset $A \subseteq V$ of vertices such that there doesn't exist any two vertices $u,...
- 88
1
vote
0
answers
33
views
Restricted Planar 3-SAT NP-hard
As we all know, 3-SAT is NP-hard.
Two of the less known results are that Planar 3-SAT is NP-hard and also a 'restricted' 3-SAT, where any literal appears in at most two clauses turns out to be NP-hard....
- 133
1
vote
1
answer
28
views
Optimum placement of zigzag trees in order to minimize the makespan
Suppose we have some trees of the following forms:
We want to place these trees in a linear fashion in a way such that the last node has the minimum distance to the first node. For instance, if we ...
- 53
0
votes
1
answer
46
views
Confused on Bellman Ford
We have a graph where we want to get from node u to v in the shortest path possible.
I understand how Bellman-Ford works when we have exactly i edges to go from u to v or at most i edges to get from u ...
0
votes
0
answers
30
views
The computational complexity of a variant of algorithm for the TSP (Travelling Salesman Problem)
What is the algorithm's computational complexity for a variant of the Travelling Salesman Problem, where every node must be visited at least once, meaning that a node can be visited more than once? (...
