Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

Filter by
Sorted by
Tagged with
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.
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: ...
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 (...
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 ...
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 ...
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 ...
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 $...
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,...
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 ...
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 ...
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 ...
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,...
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....
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 ...
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? (...

1
2 3 4 5
93