Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [graphs]

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

4,945 questions
Filter by
Sorted by
Tagged with
965 views

### Create a binary search tree from a sorted array: Space complexity reasoning

Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'. ...
58 views

### What are the best parameters possible from a binary linear LDPC code where each parity-check matrix is the incidence matrix of a graph?

There is an obvious construction of linear codes from graphs, where each codeword is a cycle in the graph. Physical bits are edges in the graph, and constraints are vertices. This has been used in the ...
707 views

### Longest-Path Layering algorithm

NOTES: there are a myriad of graph data structures, I use a spin-off of a directed adjacency hash. the code provide in this post is python3 on the premise that it ...
3k views

### Why are search problems assumed to have the structure of "find a path in a graph"?

I have skimmed a few introductions to "search problems", and I have noticed that: Stated informally search problems are defined as "find an object y inside a larger space/object X"...
34 views

### Balancing tree by removing nodes instead of perfoming rotations to defined height $h$

I am provided a tree that may be very deep and unbalanced. I want to be able to transform this tree into a more balanced form with maximum height $h$. We can do this by removing internal nodes, but we ...
14 views

### Finding Common Neighbors between Graph Nodes

I am working on an Application that will generate a graph where each node is either a disease or its symptom. This is an undirected graph, and there is an edge between the disease and its symptoms. ...
541 views

### Retrieving the cheapest path of a graph with time-dependent edge weights

There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the weights of edges are time-dependent? I'm trying to find an efficient ...
1 vote
229 views

### Find a weight threshold for edges for maximum number of connected components in a graph

So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or ...
1 vote
21 views

### Pseudo-Traveling Salesman on a colored graph

I have a graph with nodes of various colors and weighted edges between them. I would like to find the least cost path that touches exactly one node of each color. Is this a known problem or reducible ...
1 vote
350 views

### Clash Royale Algorithm for troops path

I am making a clone of Clash Royale which is basically a Tower Defence game. As you can see from the picture you can deploy different troops only in your side of the court (that blue rectangle), and ...
42 views

### Algorithm for finding a path factor in a graph

A 1-factor is a perfect matching. A path factor of a graph $G$ is a spanning subgraph, each of whose components is a path with at least two vertices (see the following figure). Since every path with ...
1 vote
19 views

### Defining multi commodity flows as polytopes

In a multi commodity network, we define a demand to be a vector $d \in \mathbb{R}^{k}$, where $k$ is the number of pairs of sinks. That is, $k = \binom{S}{2}$, where $S$ is the set of sinks (aka ...
1k views

### Global optimization of state assignments in a directed graph with a tree-based distance cost

I am exploring a general optimization framework to solve problems characterized by the following structure. Any literature references, search terms, or algorithmic strategies would be greatly ...
881 views

### Steps that guarantee exiting a maze

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
33 views

### Algorithm for all optimal s-t cuts [closed]

Suppose the $s$-$t$ min cut in a directed digraph $G = (V,E)$ is not unique ($s$ is the source and $t$ is the destination). Is there an algorithm to generate all possible $s$-$t$ min cuts, say using ...
267 views

### Literature request: Generating all vertex subsets of a graph

I am working in an algorithm which finds a unique maximal independent set of vertices. Then, using this set, one can construct all other vertex subsets. I assume this might have some applications ...
1 vote
181 views

### How to solve a system of XOR equations in a cyclic graph?

I am working on a problem where I need to find values for nodes in a graph of k-nodes. Here an example: The properties are: Each big node (A..H) is connected to at least one blue node Each blue node ...
54 views

### Number of graphs that almost contain a $k$-clique

A (loop-free) graph almost contains a $k$-clique if it does not contain a $k$-clique, but adding an edge between any two different vertices that are not already connected by an edge would produce a $k$...
16k views

### Shortest path that passes through specific node(s)

I am trying to find an efficient solution to my problem. Let's assume that I have positive weighted graph G containing 100 nodes(each node is numbered) and it is an ...
1 vote
68 views

### Choosing root for maximum matching in tree

This question deals with how to find the maximum matching in a tree. I understood the answers, but for one part. Choose a root arbitrarily. For each subtree, calculate the maximum matching within the ...
18 views

### A specification of all possible languages for representing graphs?

There are a few commonly used markup languages for specifying graph structures. I am interested in discovering alternative graph notations that may be counterintuitive yet more compact or useful in ...
1k views

### Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
44 views

### Coding the labyrinth solver

The question mathematically has been answered here: https://math.stackexchange.com/questions/4886084/guaranteed-graph-labyrinth-solving-sequence/4887473#4887473 To summarize, in an unknown strongly ...
1k views

### Best algorithm for sequencing reducible control flow graph

I have a reducible control flow graph with only natural loops, produced from a simple DSL. Every node keeps a list of successors and a list of predecessors. I need to make a sequence of nodes out of ...
4k views

### When to use DFS and when use BFS?

Preparing for an interview. I see two cases where each one is specially suited BFS: When you need to find shortest path between vertices (if one exists). DFS: If you need to find cycles in a ...
1 vote
27 views

### Minimum expected number of path to cut graph problem

I came up with a problem but was unable to show the hardness of the problem (NP/#P/P-hard). The problem is as follows. Given a directed graph $G=(V, E)$, each edge will have a confidence score $c$. ...
28 views

### Robust maximum weight forests with weights on edges

In an undirected weighted graph with edge weights, the task is to find a spanning tree T. An adversary will delete two edges (not necessarily from T), and subsequently, we can add an edge (excluding ...
1 vote
221 views

### Prove the following claim on Hamilton Path?

I am trying to prove the following claim: Given DAG graph, there is Hamilton path iff the following algorithm returns true: Do topologic sorting. Move on the graph's vertices one by one (from low to ...
49 views

### Algorithm to find minimum number of cuts in DAG based on a rule

I encountered this problem while doing some “graph”ics programming: Take a directed acyclic graph where every vertex is given a non-unique label 1..N You can ‘trim’ the DAG by making a cut that ...
26 views

### breadth first search proof incomplete statement

I'm studying Breadth-First Search (BFS) from the CLRS book and I'm having trouble understanding the proof that each distance from the source node calculated by BFS is the shortest distance from the ...
1 vote
93 views

### Number of unique paths in a grid

Suppose, I have a nxn grid. Now, I want to move from (1,1) to (1,n). How many unique ways are there possible if I can move in left, right, up and down direction. I am trying to solve it using depth ...
101 views

### Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
2k views

### Find out an algorithm that finds out if an undirected graph contains even length cycle or not using BFS?

I know how to find odd length cycles(a bipartite graph cannot have odd cycles) but I cannot manage to make an algorithm when considering even length cycles.
76 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 ...
21 views

### Selecting an Induced Subgraph from a DAG with Specific Conditions

I am working with a Directed Acyclic Graph (DAG), denoted as $G$. The graph has a specific constraint where the out-degree of each vertex in $G$ is at most $2$. My objective is to select an induced ...
1 vote
185 views

### Algorithms for finding closest graph node within set of nodes

Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$? Furthermore, say we are doing many ...
2k views

### Shortest path with odd weight

Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd. We are looking for an algorithm for finding the weight of the shortest odd ...
1 vote
45 views

### Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer. The full description of the problem is: Is it possible to find a simple path (no ...
1 vote
80 views

### Is variable a constant or a parameter

I am working on the $[1,j]$-dominating set problem defined in this paper. In section 4, they study the problem complexity on degenerate graphs and prove that the problem is W[1]-hard for the parameter ...
47 views

### Finding negative cycles using the Bellman-Ford algorithm and a source node

I'm exploring the Bellman-Ford algorithm to detect and track negative cycles (a collection of ncycle that we can see in the implementation). I'm wondering if the ...
1 vote
42 views

### Graph Coloring Decision Problem Reduction to Prove NP-Complete

I am doing research into NP-Complete problems and more specifically started looking into the Graph Coloring Decision Problem or the k-Coloring problem, as described here: Given a graph $G = (V, E)$ ...
199 views

### Kernelization algorithm for the following problem

We are given an undirected graph $G$ and a positive parameter $k \geq 0$. The problem is to decide if there exists a set $S \subseteq V(G)$ of size at most $k$ such that $G − S$ does not ...
19 views

### all pairs shortes path variant [duplicate]

Let $G=(V,E)$ a directed Graph with a coloring function $F:E \to red,blue$ and a weight function $W: E \to R$ I need to find all pairs shortest path s.t. every path visits at least one red edge, or ...
1 vote
525 views

### What algorithm will visit each node in a graph a number of times equal to the number of paths to that node from the root?

First Few Iterations of the Algorithm We have an algorithm in which a squirrel visits the nodes of a directed graph. Our graph has two colors of edges: black and white. Initially, the graph has black ...
1 vote
227 views

### Finding the two edge-disjoint paths, minimizing the sum of their lengths

Given an undirected graph and a start and end node, I am trying to find two edge-disjoint paths such that the sum of their lengths is minimized. In particular, each path must start at the start node, ...
1 vote