Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
2,100 questions
1
vote
1answer
27 views
Path between two vertices in directed graph without cyclic vertices
I have been searching online for some time but I have not found an answer.
Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no cyclic ...
3
votes
1answer
36 views
Finding the shortest path for synchronized pawns in a maze
I have been trying to wrap my head around this problem, and I just can't get it.
We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, ...
11
votes
2answers
1k views
What is the meaning of 'breadth' in breadth first search?
I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this:
Breadth-...
1
vote
0answers
21 views
vertex cover of bipartite graph
A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.
A minimum vertex cover is a vertex cover with minimal cardinality.
...
1
vote
1answer
17 views
Vertex Cover without covering all edges
What would be the name of the problem of a vertex cover that covers all the vertices without the requirement of covering all the edges?
Vertex cover has to answer whether or not there is a set of $k$ ...
-1
votes
0answers
17 views
What is the source to understand Feedback edge arc set? [on hold]
What is the source to understand Feedback edge arc set?
I tried wikipedia and research papers any easy tutorial?
4
votes
3answers
738 views
What is a fractional matching?
For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation ...
4
votes
0answers
36 views
How to generate a random reducible flow graph?
Is there any known algorithm to generate a random reducible flow graph (single root, single sink) with a given maximum cardinality $N$?
Ideally, the distribution should be uniform over the set of ...
2
votes
1answer
37 views
Directed graph where DFS returns on a node before all its child nodes are visited?
Give an example of a directed graph in which a depth-first search backs
up from a vertex $v$ before all the vertices that can be reached from
$v$ via one or more edges are discovered.
My professor ...
0
votes
0answers
12 views
Linear Programming Formulation for Weighted Max-Cut
I am wondering if this Integer Linear Programming model I came up with as an exercise for my algorithms class is correct.
The Problem
Given a graph $G=(V, E)$, with a set of weights $W = \{w_{ij} \...
0
votes
1answer
32 views
What are possible uses for cross, back and forward edges after the DFS visit?
The depth-first search visit of a graph produces, in some implementations, a labeling of the edges as "Cross", "Back" and "Forward". I know "B" edges can be used to detect cycles.
What are other ...
1
vote
2answers
41 views
Size of tree decomposition
Given a graph $G$ with $n$ vertices, let $(X, T)$ be a tree decomposition of $G$ with the smallest width. Is the number of nodes in $T$ upper bounded by $n$? I have googled it but all materials I ...
1
vote
0answers
27 views
Finding weakly-negative cycles
In a directed graph where the edges may have positive or negative weights, the Bellman-Ford algorithm detects cycles in which the sum of weights is strictly negative ($<0$). I need to detect cycles ...
1
vote
0answers
96 views
+200
Morphing Hypercubes, Token Sliding and Odd Permutations
A month ago, I asked the following question math.exchange (https://math.stackexchange.com/questions/3127874/morphing-hypercubes-and-odd-permutations), but for completeness, I will include the details ...
1
vote
0answers
8 views
How to build an execution graph of concurrency accesses
Sorry If I don't use the right vocabulary, maybe part of my question is due to the fact that I don't know the name of what I'm searching.
I have a bounded set of operations that need to access a ...
1
vote
0answers
16 views
A term for a set of vertices with a small set of neighbors
Given a graph $G(V,E)$ ans a subset $S\subseteq V$, define $N(S) = $ the set of neighbors of $S$.
Is there a standard term for a subset $S\subseteq V$ for which $|N(S)|\leq |S|$? Is there a standard ...
1
vote
0answers
30 views
Finding a path with a smallest product
Let $G$ be a graph whose edges have integer weights between 1 and 255.
What is an efficient algorithm for finding a path between two vertices $s,t$, such that the product of weights on the path is ...
5
votes
0answers
54 views
Minimum Number of Edges Added to a DAG to get Unique Topological Order
The question is simple:
Given an unweighted directed acyclic graph, $G = (V, E)$, what is the minimum number of directed edges we need to add to $E$ such that the resulting graph $G = (V, E')$ has ...
1
vote
1answer
52 views
Djikstra's algorithm to compute shortest paths using at least k edges
I have a graph G = (V, E) where each edge is bidirectional with positive weight. I want to find the shortest path from vertex s ...
0
votes
0answers
38 views
Unite a forest if you know each tree's parent
I have a forest of Tries, each forest[i] is a Trie. forest[0] contains the root node to all the others. I want to recursively ...
1
vote
0answers
38 views
Given a tree find path that maximizes the median of the costs of edges
We have given tree with $N$ nodes and $N-1$ edges, such that each edges is assigned positive weight. We need to find path of length between $L$ and $R$ inclusively, with maximum cost. Cost of a path ...
-1
votes
1answer
30 views
Is there any way to find the nodes in the each subtree of each node having distance equal to height of the subtree?
We are given a tree of N nodes from 1 to N where node 1 is the root of the tree.
For each node i from 1 to N, you have to find the numbers of nodes which are in the subtree of i and are at distance ...
1
vote
1answer
33 views
How to correctly describe this action, deleting an edge that “shortcut” some vertices
Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below:
1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in ...
1
vote
0answers
18 views
maximum matching in general graph [duplicate]
How to justify the role of blossom in Edmond's blossom algorithm for maximum matching? odd cycles also can be covered in augmenting path.
3
votes
2answers
251 views
The Clique vs. Independent Set Problem
Suppose you have an undirected graph $G = (V, E)$, known to both Alice and Bob, Alice gets an independent set of $G$. Bob gets a Clique $B ⊆ V$.
Is there any algorithm in $O(\log^2 n)$ bits that ...
1
vote
1answer
38 views
Where's the flaw in my algorithm? (Linear program to solve NP-hard problem)
The problem (copy-pasted from this question on cs.stackexchange):
Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices ...
1
vote
2answers
57 views
Assigning books to boxes
I am trying to model the following problem correctly as a min-cut network flow problem. I have $n$ books and 2 boxes. I also have books that I know must go in one of the two boxes. In addition, each ...
0
votes
0answers
75 views
Maximum matching blossom algorithm
https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf
Why do we use blossom contrast in maximum matching?
The examples that I have seen can easily be solved by just ...
1
vote
1answer
59 views
Which algorithm is this?
I'm looking for someone who can tell me which algorithm this is and help me to clearify what the variable mean.
$g_j$ : the shortest path length from $1$ to $j$
$t_{i,j}$: the length from $i$ to $j$
$...
2
votes
0answers
40 views
Find optimal redistribution in flow graph
I have directed graph (maybe with cycles), and some resources in vertices (let's say gold). I can transfer gold between vertices only in direction of edges. The task is to minimize maximum value of ...
2
votes
2answers
69 views
Response time of scheduling a DAG where each vertex is a task
Suppose I have a directed acyclic graph where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to ...
3
votes
1answer
41 views
Maximal Minimum Spanning Tree by Removing $k$ Edges
The problem is as follows:
Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0 < k < |E| - |V| + 1$. Describe and analyze and efficient algorithm to remove ...
1
vote
1answer
36 views
A problem to maximize the number of edges in a cycle while minimizing the total weight
I encountered the problem below and the only solution I came up with is branch and bound like that is used in TSP and I don’t think the bound I used is good enough. Are there any better idea on this?
...
7
votes
1answer
553 views
Is finding a path with more red vertices than blue vertices NP-hard?
Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$...
0
votes
0answers
11 views
Find a path passing through the minimum number of odd nodes [duplicate]
Assume you have a undirected graph where each vertex is marked either odd or even. Given two even nodes, How do you find the path that passes through the minimum number of odd nodes in O(edges)?
Now ...
0
votes
0answers
10 views
The balanced $k-$ partitioning problem : how to design testbeds to compare different metaheuristics methods
I implemented different search metaheuristics methods (local search, Tabu search, and simulated annealing) on the problem of partitioning a non-oriented weighted graph' vertices into k parts of nearly ...
5
votes
2answers
489 views
Find a path from s to t using as few red nodes as possible
Was doing a little interview prep. Given an undirected graph G, such that each node is colored red or blue and |E|≥|V|, find a path in O(|E|) time such that starting and ending at 2 blue nodes, s and ...
0
votes
2answers
42 views
BFS Algorithm for Finding Minimum Steps for Knight Eliminating a Moving Pawn
BFS Algorithm for Finding Minimum Steps for Knight Eliminating a Moving Pawn.
As the Title suggests, I'm trying to intuitively understand this problem. Suppose we have a Pawn and a Knight taking ...
1
vote
0answers
42 views
The maximum number of uniquely intersected elements from the all possible intersection scenarios among the sets in a two-column matrix
Let us define a $n \times 2$ matrix M consisting of integer sets, such
that the first column consists of the so-called intersecting sets,
and the second column ...
3
votes
0answers
44 views
Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm
I have a graph algorithm that runs in:
$$ T(n, m) = \begin{cases}
c_1 & n \leq 2 \lor m = 1\\
T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\
T(n - i,\ m) + T(i, m) + ...
1
vote
1answer
47 views
Is Breadth First Search Space Complexity on a Grid different?
Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning:
For example, the flood fill question is described here:
https://www....
2
votes
1answer
90 views
Given directed connected weighted graph, check if d(v) = delta(s,v)
I'm having some hard time with this problem.
Can someone give me some clue/guidance?
This is an homework question, so please don't just solve it.
Given a weighted directed connected graph $G = (V,...
0
votes
0answers
49 views
A scheduling problem on an oriented graph with multiple constraints
The problem is the following :
Data
An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks
A map $d: V -> \mathbb{N}$ : to be understood a function mapping tasks to a ...
0
votes
0answers
57 views
Algorithm for finding single input/output sub graphs
I'm running into an interesting directed acyclic graph (DAG) problem and was wondering if this is a known problem and if it has an efficient algorithm for it. I will use 'graph' and 'DAG' ...
4
votes
0answers
97 views
Is Hamiltonian cycle problem on graphs with out-degree at most 3 NP hard?
I am trying to show a different form of Hamiltonian cycle problem is NP Hard. The problem is as follows.
We have a directed graph and each node can have at most 3 outgoing edges. Determine if this ...
1
vote
1answer
41 views
Prove/disprove - reverse topological sort transpose graph
I need to prove or disprove the following statement:
"Let $G$ be a directed acyclic graph, and $v_1v_2...v_k$ a topological sort of $G$.
Then $v_kv_{k-1}...v_1$ is a valid topological sort of the ...
1
vote
1answer
44 views
Algorithm to convert undirected connected graph with no bridges to strongly connected directed graph
I am not sure how to go about this exactly. My attempt is find the pick an arbitrary node and run DFS, ordering each node by order of discovery. After this, You can orient each of edges so it pointing ...
3
votes
1answer
39 views
shortest form $s$ to $t$ stopping at $u$
Suppose you want to go from vertex $s$ to vertex $t$ in an unweighted graph $(V, E)$, but you would like to stop by vextex $u$ if it is possible to do so without increasing the length of your path by ...
-3
votes
1answer
28 views
Connectivity of weighted graphs [closed]
I want to know is there the connectivity of a weighted graph? Are there the references?
3
votes
1answer
23 views
How to model references in an ontology
I am interested in creating an ontology which will model arguments (among other things). For example, a triple in the ontology might be
...
