Questions tagged [graphs]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
31 views

Minimum Ratio Spanning Tree

Problem statement: Given an undirected graph $G = (V, E)$ with edge $e_i$ having two associated positive values $c_1, c_2$. Find a spanning tree $ST$ such that (ratio of the spanning tree): $$\frac{...
0
votes
0answers
46 views

Finding a shortest path in graph

If each edge of a graph $G$ is unweighted or has equal weights, then the shortest path between two nodes in that graph is the path that contains the fewest number of edges. Such a path can be obtained ...
0
votes
1answer
47 views

graphs - finding a shortest path length not achievable by breadth first search

supposedly for some graphs there exists valid shortest path lengths between two nodes of the graph that cant be constructed by breadth first search. what defines these shortest paths that breadth ...
3
votes
2answers
57 views

Minimally extend a tree such that there are no bridges in the new graph

We are given an undirected tree on which we should add the minimum number of edges such that there are no bridges in the new graph. An edge $e$ is a bridge if the graph with that edge removed is no ...
1
vote
0answers
14 views

Probabilistic switching between breath-first and depth-first

I am reading Artificial Intelligence: Making Machines "Think" by Neill Graham. He gives an overview of graph search using either the breadth-first (BF) or depth-first (DF) search algorithms, and ...
0
votes
0answers
59 views

2-sat and vertex cover [duplicate]

I've been recently dealing with the classical problem of finding the minimum vertex cover in a bipartite graph. The common approach is to set direction to all edges and run DFS from all vertices of ...
4
votes
1answer
100 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
59 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
3answers
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
votes
2answers
239 views

Vertex cover of bipartite graph

A vertex cover 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. From codeforces, ...
1
vote
1answer
31 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$ ...
4
votes
3answers
855 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
51 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
54 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
15 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
45 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 ...
2
votes
2answers
63 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
33 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
165 views

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
10 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
18 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
40 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
78 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
179 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
50 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
74 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
50 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
21 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
379 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
45 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
69 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
87 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
62 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
45 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
78 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
95 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
41 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
566 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
16 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 ...
5
votes
2answers
583 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
91 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
45 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
169 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
121 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
52 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 ...
1
vote
0answers
62 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
108 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 ...