Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

0
votes
0answers
4 views

Finding the shortest path for synchronized pawns in a maze

I've been trying to wrap my head around this problem, and I just cant get it. We have an a × b matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, denoted ...
4
votes
3answers
720 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 ...
1
vote
1answer
111 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-...
4
votes
2answers
72 views

Find maximal subgraph containing only nodes of degree 2 and 3

I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
1
vote
1answer
287 views

Finding all paths from s to t in linear time

I was looking at the following algorithm which prints all the paths from node s to node t and I have some questions I don't ...
1
vote
1answer
16 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$ ...
0
votes
0answers
14 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. ...
2
votes
1answer
351 views

Distance vector in a weighted graph

I got a weighted, connected and directed graph $G$. There is a vector called the distance vector $Dv \in \mathbb{N}^n$ in which $Dv_i$ is the shortest distance from $1$ to $i$. All edge weights are ...
4
votes
0answers
32 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 ...
-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?
1
vote
0answers
76 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 ...
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
37 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 ...
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 ...
14
votes
2answers
622 views

Compute a max-flow from a min-cut

We know that computing a maximum flow resp. a minimum cut of a network with capacities is equivalent; cf. the max-flow min-cut theorem. We have (more or less efficient) algorithms for computing ...
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} \...
1
vote
0answers
25 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 ...
3
votes
1answer
64 views

Building maze to maximize shortest path, may be given waypoints and teleports

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (...
3
votes
2answers
452 views

Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time

Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm. For a fixed starting vertex $s$, the ...
1
vote
1answer
44 views

Matrix of a graph and computational complexity

Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ ...
1
vote
2answers
688 views

Find a node with maximum distance from query node in a tree

I solved this problem from codechef: problem link and now I want to change it a bit. Instead of find out the distance between node $u$ and $v$ I want to answer $k$ queries of the form: find node $u$ ...
3
votes
2answers
201 views

Algorithms for procedural generated mazes

For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important). There are many Maze generation algorithms, but they only work on a ...
1
vote
1answer
114 views

Merge Leaf labeled trees

I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible. Can somebody please help me to ...
0
votes
1answer
177 views

How to deal with cost variation in a dynamic graph when applying Dijkstra

What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I ...
1
vote
1answer
211 views

Find a path that contains specific nodes without back and forward edges

I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...
25
votes
7answers
38k views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
0
votes
1answer
159 views

A path modification problem in directed graphs

We start with a given finite directed graph. It could represent transitive relations such as: data transfer paths in social networks, transportation connections, etc. Let us use the notation A->B ...
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
29 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 ...
2
votes
1answer
65 views

Embedding trees of diameter four is NP-hard

Suppose that $T$ is a tree of diameter four and $G$ is a graph. Deciding, whether $T$ can be injectively mapped to $G$ is NP-hard (there is a simple reduction from the problem of finding an ...
1
vote
0answers
15 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 ...
5
votes
0answers
53 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
50 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 ...
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
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 ...
0
votes
1answer
306 views

Predecessor-subgraph property

In the proof of the predecessor subgraph property (page 14 of the following notes) http://www.cs.sfu.ca/CourseCentral/307/binay/shortestpath.pdf $d[v_i] \geq d[v_{i-1}]+w(v_{i-1},v_{i})$ is assumed ...
1
vote
1answer
43 views

proof that BFS remains total after adding edge to graph

I'm trying to prove that if $G$ is a connected graph, then $BFS(u\in G)$ is total (i.e. it visits all the vertices of $G$). The inductive proof consists in 2 cases: (i) Prove that $\rm{BFS}$$(u \in \...
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 ...
3
votes
1answer
64 views

Can a cycle be represented by L1 metric?

Let G be a graph that forms a cycle on $n$ vertices, with non-negative weights on the edges. Can you give each vertex v a vector $\mathbb{R}^m$ (for some $m\in \mathbb N^+$) such that the L1 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
votes
1answer
28 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 ...
3
votes
2answers
249 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 ...
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
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.
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$ $...
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
1answer
12 views

optimal flow for index multiple source and destination in directed graph

I am facing the similar problem to max flow in multiple source-destination directed graph (which has a familiar solution of connecting all the sources to one source and the same for the destination, ...
6
votes
1answer
109 views

Finding a negative cycle in a bipartite graph

The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where ...
20
votes
2answers
4k views

NP completeness proof of a spanning tree problem

I am looking for some hints in a question asked by my instructor. So I just figured out this decision problem is $\sf{NP\text{-}complete}$: In a graph $G$, is there a spanning tree in $G$ that ...
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 ...