Skip to main content
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.

Filter by
Sorted by
Tagged with
0 votes
2 answers
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'. ...
0 votes
1 answer
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 ...
0 votes
1 answer
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 ...
13 votes
3 answers
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"...
0 votes
1 answer
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 ...
0 votes
1 answer
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. ...
3 votes
1 answer
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
1 answer
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
1 answer
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
0 answers
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 ...
4 votes
0 answers
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
1 answer
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 ...
4 votes
2 answers
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 ...
17 votes
3 answers
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 ...
0 votes
0 answers
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 ...
0 votes
1 answer
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
1 answer
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 ...
2 votes
1 answer
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$...
8 votes
2 answers
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
1 answer
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 ...
0 votes
0 answers
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 ...
10 votes
2 answers
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 ...
0 votes
1 answer
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 ...
0 votes
1 answer
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 ...
5 votes
2 answers
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
0 answers
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$. ...
0 votes
1 answer
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
1 answer
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 ...
3 votes
0 answers
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 ...
0 votes
1 answer
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
1 answer
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 ...
4 votes
1 answer
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 ...
3 votes
4 answers
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.
0 votes
1 answer
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 ...
0 votes
1 answer
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
1 answer
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 ...
4 votes
3 answers
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
1 answer
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
1 answer
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 ...
-1 votes
1 answer
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
1 answer
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)$ ...
0 votes
1 answer
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 ...
0 votes
0 answers
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
1 answer
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
1 answer
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
1 answer
51 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\...
1 vote
1 answer
212 views

communities problem with union and find

I am trying to solve the following problem: Input is $2D$ array of integers, $M$, which corresponds to friendship relations. For example, if $M[1][2]=1$, $1$ and $2$ are friends (assuming symmetry it ...
1 vote
2 answers
35 views

Understanding Time Complexity Calculation for Factorial and Exponential Algorithms

I'm trying to wrap my head around how to calculate the time complexity of algorithms that exhibit factorial (𝑛!) or exponential (2^𝑛) growth rates. Specifically, I want to understand the thought ...
39 votes
1 answer
753 views

Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph $G$, and two vertices $s$ and $t$, find an $s$-$t$ path $P$ ...
1 vote
1 answer
379 views

Time complexity of Tsp using DP

this is the recursion formula for problem : C(i,S) = min { d(i,j) + C(j,S-{j}) } In fact, when I tried to implement it as a code, the following code came to my ...

1
2 3 4 5
99