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
1 answer
16 views

How to find a crticial edge in a flow network?

The complete question is as follows: An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Give an efficient algorithm that ...
user avatar
  • 101
0 votes
1 answer
19 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 ...
user avatar
1 vote
1 answer
42 views

Data structure and optimal algorithm for modeling reachable outputs given a set of inputs

Given the following: A set of input types $I$ = {a, b, d, ...} A set of functions $F$ (With associated costs, and possibly identical signatures) = {($c_1$, a -> d), ($c_2$, (a,b) -> e), ($c_3$, ...
user avatar
  • 113
0 votes
0 answers
33 views

Longest shortest path between two classes of nodes

(larger context at the end) My view of the problem I have an undirected graph whose nodes can be categorized into three classes depending on some metadata (I have a function that can tell me the class ...
user avatar
  • 101
-1 votes
1 answer
14 views

Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?

I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.
user avatar
1 vote
1 answer
36 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 ...
user avatar
3 votes
1 answer
33 views

Algorithm for maximum non-crossing edge set in bipartite graph with a fixed permutation

I'm trying to identify an algorithm to solve this computational problem Input: Bipartite graph (V, W, E), with E ⊆ V×W A fixed ...
user avatar
  • 53
-1 votes
1 answer
28 views

Does a minimum spanning tree necessarily provide the lowest cost path between any 2 nodes?

If I'm given a minimum spanning tree, my understanding is that it is a structure that connects all nodes to each other through some path, and that the overall weight of the tree is smallest. However, ...
user avatar
0 votes
0 answers
61 views

Using topological sort to find inconsistencies represented by cycles in directed graphs

Consider the following scenario. Let $x_1,...,x_n$ be a group of cars that all drive from some point A to some point B. Each car starts driving in index order. i.e. $x_1$ starts driving strictly ...
user avatar
2 votes
0 answers
54 views

Playing with boxes: NP-hard? [Graph Theory]

You are playing with boxes on a $K_{1, n}$-$\textbf{subdivision}$ graph $G:=(V, E)$ whose number of vertices is odd, i.e., $|V| \equiv 1$ (mod $2$) with a given central point $C$ such that $\forall v \...
user avatar
2 votes
1 answer
22 views

Fast algorithm for Graph Edit Distance to vertex-labeled Path Graph

Let $G$ be a vertex-labeled directed graph with unique labels $L$. Let $G_P$ be a path graph with the same vertex labels and the same number of vertices as $G$. I know that in the general case ...
user avatar
  • 23
1 vote
1 answer
19 views

Finding articulation points

I have learnt about both articulation points and bridges and I have understood the algorithm used to find the number of bridges in O(n) time which is Tarjan's algorithm. But now, can I simply say that ...
user avatar
  • 127
0 votes
1 answer
42 views

Does order of elements in a set matter in Dijkstra's Algorithm?

When we use a set for doing Dijkstra's Algorithm, we use a pair of {distance,node} which we insert in a set. Most of the articles say that the first element of pair should be the distance , else we ...
user avatar
1 vote
1 answer
30 views

Find the placement of gates on 2D points that minimizes the total distance of all paths to be made

Suppose we have a 6 vertices graph. We also have 6 gates. Each gate is attributed a path. For example, Gate 'A' will have to go to 'B'- 'C' - 'D' and 'E' Gate 'B' will have to go to 'D' Gate 'C' will ...
user avatar
  • 113
2 votes
0 answers
39 views

An inverse problem of lexicographic product of graphs

In graph theory, the lexicographic product or (graph composition) $G ∙ H$ of graphs $G$ and $H$ is a graph such that the vertex set of $G ∙ H$ is the cartesian product $V(G) × V(H)$; and any two ...
user avatar
  • 121
1 vote
1 answer
28 views

Max flow bottleneck approach flow after k iterations

This is a question from a previous exam in Graph theory and algorithms, the correct answer is E but I don't understand why. Given a network flow $(G,c)$ over graph $G(V,E) $. Assume we run Edmonds-...
user avatar
-1 votes
0 answers
42 views

Minimum cost to selected rooms among N rooms with given costs to trap rats running along k known paths

I am asked the following problem in interview so source of the problem is unknown. Students are trying to trap rat in a hostel with N rooms. Students are aware of K unique paths to these room which ...
user avatar
1 vote
1 answer
88 views

Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?

Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace? Given an undirected graph ...
user avatar
1 vote
1 answer
19 views

What is the time complexity of the EMST problem in 3D space

We have an unstructured cloud of $N$ points in 3D space. What is known about the complexity of building the Euclidean Minimum Spanning Tree of the points ? The tree is made of $N-1$ edges and can be ...
user avatar
  • 4,518
4 votes
1 answer
84 views

Computing biconnected components

My question relates to Problem 22.-2 in Introduction to Algorithms 3rd edition. There biconnected components are defined as maximal sets of edges such that any two edges in the set lie on a common ...
user avatar
  • 155
0 votes
0 answers
27 views

Computational Complexity theory - Confusion about solving by reduction an NPC problem

I can't seem to grasp the term of reduction that well. To explain I will take an example the problem of $$\sqrt{k} - clique $$ such that $$ k \leq \sqrt{V}$$ Solving by reduction with normal k-clique ...
user avatar
2 votes
0 answers
19 views

Is there a difference between realization and embedding of a graph?

Given a geometric graph (interval, circular arc, disk, etc.), is there a difference between the realization of that graph and the embedding of that graph?
user avatar
  • 1,425
3 votes
1 answer
64 views

Efficiently determine which nodes should leave a graph while maintaining connectedness

Suppose I have a graph with node weights, where a weight is either -1 or a positive integer. For example: If a node has weight -1, it is "happy", and cannot be kicked out of the graph. If a ...
user avatar
1 vote
1 answer
174 views

Optimal path problem with constraint of minimal weight

Given an undirected weighted graph $G$ and two vertices $s, t$. We want to find a path $P$ from $s$ to $t$ that minimizes the following objective function $L$ $$L(P) = max(len(P), max\{c(e) \mid e \in ...
user avatar
3 votes
0 answers
49 views

Minimize edge count in directed graph, allowing auxiliary nodes

Suppose I have a directed acyclic graph $G$. I want to find a graph $H$ containing the nodes of $G$ (and potentially more) which minimizes the number of edges in the graph, without changing the ...
user avatar
  • 12.4k
0 votes
0 answers
37 views

Definition of NP within an implementation of deterministic TMs

I am currently writing a mathematical definition for the deterministic Turing Machine so I can make use of it in one of my papers. (below, I will use the term "tuple" as a synonym for "...
user avatar
1 vote
0 answers
22 views

Dominators when node not reachable

For the definition of domination [Wikipedia], a node $d$ of a control-flow graph dominates a node $n$ if every path from the entry node to $n$ must go through $d$. If node $n$ is not reachable from ...
user avatar
-1 votes
1 answer
25 views

weighted graph separation algorithm proof

I have a graph G (G=(V,E)), where each edge has a non negative weight to it. My problem is to find a subset S (it doesn't have to exist) of nodes such the sum of all the weights of the edges that ...
user avatar
0 votes
2 answers
64 views

Calculate shortest cycle that contains node $s$

Let $ G(V,E,w)$ be a graph with no negative weights. Describe an algorithm that returns the shortest cycle containing a node $ v $. I came across this algorithm https://courses.engr.illinois.edu/cs374/...
user avatar
-1 votes
1 answer
55 views

Converting a Directed Acyclic Graph to a Directed Tree

I'm wondering if anyone can help me with this. Say I have a DAG, I understand that it has no directed cycles, but it can have loops ( "diamonds" ). My question is, is there a known way to ...
user avatar
  • 1
2 votes
0 answers
46 views

Subgraph Isomorphism with Same Number of Nodes

I am looking at a specific variant of subgraph isomorphism: Instance A graph $G = (V_G, E_G)$ and a target graph $H = (V_H, E_H)$ such that $|V_G| = |V_H|$. Question Is there a subgraph $G' = (V'_G, ...
user avatar
  • 21
2 votes
1 answer
68 views

Efficient algorithm to count number of intersections of n sets

I've come across this problem when working on a personal project of mine. I need an efficient algorithm of counting the number of overlaps between all pair combinations of n sets. Example: Set a = [...
user avatar
  • 23
1 vote
1 answer
21 views

safe edge theorem proof clarification

I found the following proof for the theorem that states "A light edge that crosses a cut that respects A is safe for A": See: https://www2.hawaii.edu/~janst/311_f19/Notes/Topic-17.html ...
user avatar
0 votes
1 answer
36 views

Recursively deleting spanning forest from graph, how many iterations maximum to get to the empty graph?

As in the question stated, I am interested in the approximation factor of the greedy approach to compute the arboricity of the graph. My intuition tells me the factor should not be bigger than $2$, ...
user avatar
0 votes
0 answers
24 views

The notion of "simulating an edge" in graph algorithms

I am reading a 1996 paper by Panconesi and Srinivasan :(https://www.sciencedirect.com/science/article/abs/pii/S0196677496900176) on distributed network decomposition. In the analysis of the recurrence ...
user avatar
  • 371
1 vote
2 answers
76 views

Are Control Flow Graphs(CFG) planar?

I notice there are different definitions for CFG(basic block or statement), so let's consider following definition: Given a program, each statement is a node in CFG, and $(u,v)\in E\iff \text{v is ...
user avatar
  • 93
0 votes
0 answers
11 views

Pursuit-evasion graph problem Top down DP approach?

I'm solving this problem here to learn about pursuit-evasion problems https://leetcode.com/problems/cat-and-mouse/ Basically cat starts at 2, and mouse starts at 1 (goes first) to escape to 0 and they ...
user avatar
1 vote
0 answers
25 views

Algorithm to determine maximum difference between different sets of a graph

I saw this image only, and it got me thinking: is this the maximum area difference between a contiguous region and Los Angeles County, such that the population of that region is smaller? Formally, ...
user avatar
0 votes
1 answer
42 views

Transitive Closure of a graph

Assuming we have a DAG, $G = (V, E)$, and we know that we can calculate $G$'s transitive closure in time complexity of $f(|V|, |E|)$, whereas $f$ is monotonic increasing function. Show that given a ...
user avatar
0 votes
0 answers
16 views

How to plot the 'back-to-home-city-path' in TSA without repeating cities

I'm doing an implementation of the traveling salesman problem using genetic algorithms, but I can't get it: If we need to get the best route in a certain set of cities and then go back to the first ...
user avatar
1 vote
1 answer
30 views

Confuse on proof of theorem 22.9 (White-path theorem) Depth-First search (DFS) on Cormen-Leiserson-Rivest-Stein "Introduction to algorithms" book

I'm reading the DFS section of CLRS-Introduction to Algorithms, and confuse on the $\Leftarrow$ direction of the proof of the white-path theorem of DFS algorithm in this book. Note that each node u ...
user avatar
0 votes
2 answers
57 views

Find a simple path from S to T in a directed graph so that the product of its weights is maximum

I'm looking for an algorithm that finds a simple path from S to T in a directed graph (which might have cycles) so that the product of edge weights in the path is maximum. All the edge weights of the ...
user avatar
  • 23
2 votes
1 answer
29 views

Are the clusters in a cluster graph complete graphs?

I read two definitions of cluster graphs that seem in conflict to me. One is from Koller: We begin by defining a cluster graph — a data structure that provides a graphical flowchart of the factor-...
user avatar
1 vote
1 answer
34 views

Difference between cost and the heuristic function in A* search

Looking at the image above, thinking in terms of A* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd ...
user avatar
0 votes
0 answers
40 views

DAG graph where indegree >= outdegree and indegree = 0 => outdegree <= 1, cover all vertex with min amount of paths

Given a graph $G = (V, E)$ where G is directed: $ \forall \ e \in E$ : $e$ has a direction. G is acyclic (no cycles): $ \forall$ path $v_1, \dots , v_n : (v_n, v_1) \not\in E $. If indegree $\gt0$, ...
user avatar
1 vote
2 answers
92 views

Topological sort of minimum costs to finish interdependent tasks

The problem that I'm trying to solve goes like this: A project is split into tasks. Each task takes a known number of days. Some tasks can be done at any time(lets call these simple tasks), others ...
user avatar
  • 125
2 votes
1 answer
60 views

FPT algorithm for dominating set

An instance of the Dominating Set problem is given by an undirected graph $G = (V, E)$ and an integer $k$; it is a ‘yes’-instance if there is a subset of vertices $S ⊆ V$ with $|S| ≤ k$ such that for ...
user avatar
1 vote
1 answer
68 views

Shortest path in a directed weighted graph

Suppose we have a directed, weighted graph, $G = (V, E, w)$, with non-negative weights. We define the weight of the shortest path different from the original definition. The weight of a path with at ...
user avatar
1 vote
0 answers
30 views

Is There a Term for "Factoring" a Graph by an Equivalence Relation on Nodes?

I have a coding problem I'm running into that feels like it's solved: Given a (directed) graph, and an equivalence relation on nodes, merge the equivalent nodes in a way that preserves the graph ...
user avatar
  • 111
3 votes
0 answers
31 views

Add an edge to a planar graph and preserving the planarity

I've already posted in the Math StackExchange section, but nobody answered. I’m wondering if, given a planar graph $G$ And two vertices $v,u$, is there an efficient algorithm to know if adding the ...
user avatar
  • 131

1
2 3 4 5
90