# 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
Filter by
Sorted by
Tagged with
1 vote
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
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.
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 ...
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 ...
1 vote
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
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
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
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: ...
1 vote
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
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 ...
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
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 ...
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 (...
1 vote
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
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 ...
1 vote
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
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
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
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
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 ...
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
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
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
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 ...
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
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
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
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 ...
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
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
37 views

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 ...
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
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
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
35 views

1 vote
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....
1 vote
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 ...