# Questions tagged [graphs]

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

3,364 questions
Filter by
Sorted by
Tagged with
22 views

### Minimum edge weight k-sized partition on interval graph with triangle inequality

Suppose you have a weighted graph $G = (V, E \subseteq V^2, w \in E \to \mathbb{R}^+)$, where $w$ satisfies the triangle inequality $w(x, y) + w(y, z) \ge w(x, z)$, and suppose that $(V, E)$ is an ...
14 views

### NP Complete Clique Variation

I have the following problem I am trying to prove NP Complete. Tutors have two jobs- grading exams and homework help. Suppose we have a set of $n$ tutors. Each of them can tutor any amount of $m$ ...
24 views

### graph theory proof or disproving

I was requested to prove or disprove the following statement if a graph is conncted does it necessarily means that E>(V-1)(V-2)/2 v represents vertex and E the edges I think I need to disprove it ...
24 views

### what happens to max flow if we decrease the capacity of every edge by some constant?

Given a graph $G = (V,A)$, with source $s$, sink $t$, edge capacity larger than 1 (but not all equal), I know that if we decrease the capacity of one edge by 1, the $s,t$-maximum flow decreases by at ...
29 views

### Finding vertex coverage that is also independent set

Given a graph G and integer k, find a vertex coverage set of size k that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea ? ...
162 views

### Removing vertices from a labelled graph

Let $G$ be an undirected graph with each vertex labeled with an integer. Is there an algorithm to remove a subset of vertices such that in the resulting graph with deleted vertices no vertices with ...
34 views

### Network Flow - Minimum flow in a network

I have a directed graph G=(V,E) with a source s$\in V$ and a sink t$\in V$. There is a minimum capacity (lower bound) l $_{e}$ for each edge in G. There are no upper bounds on the edges. In a course ...
41 views

### Shortest path from $s$ to $v$ in unweighted simple directed graphs

Let $G=(V,E)$ be an unweighted simple directed graph. Some of the edges are colored red. Let $E'⊆E$ denote the set of red edges. Given a vertex $s∈V$,suggest an efficient algorithm for finding the ...
27 views

### How to check whether given $k$ vertices make a $k$-clique in an undirected graph $G$ efficiently

Let $G=(V, E)$ be an undirected graph with vertex set $V$ and edge set $E$. Let $V'=\{v_1, v_2, ..., v_k\}$ be a subset of $V$ where degree of each $v_i$ is bigger than or equal to $k$. Is there a way ...
28 views

### Which Graph Algorithm should I use to find all possible groups in a graph?

I have the following situation: (Alex, Bob) (Alex, Charlie) (Debra, Erika) Imagine that each row in the list represents a friendship. Alex is friends with Bob. Alex is friends with Charlie. And ...
58 views

### Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)

Given undirected and connected graph $G = (V,E)$. Prove for any DFS run: for any $u,v \in V$ if $u.d>v.d$ then $u.d − v.d ≥ δ(u,v)$ $δ(u,v)$-distance of a shortest path (not necessarily unique) in ...
54 views

### What's the best algorithm to find the shortest path between 2 vertices in a graph?

Considering an undirected and unweighted graph, what's the best algorithm to find the shortest path between two vertices?
16 views

### I want to create an unsigned 8-bit adder/substractor and implement it in a logic circuit [closed]

I am having a hard time trying to implement an adder for 8-bits unsigned numbers with 1's complement but without using VHDL since I am new to this kind of stuff. But I know that I should use 8 full ...
11 views

23 views

### Prove G have a single MSP

We have undirected connective, weighted graph $G = (V,E)$. we also know that for every $e,e'$ in $E$, $w(e)≠w(e')$. Prove that $G$ has a single MSP. Ideas?
16 views

### Practice question on the applications of flows and cuts

This question is from Erickson's textbook on algorithms, p. 376, question 18. Faced with the threat of brutally severe budget cuts, Potemkin University has decided to hire actors to sit in ...
29 views

### Weight of minimum spanning tree of G and T

We have undirected weighted connective graph $G=(V,E)$, We also have a minimum spanning tree $T$ of $G$. Let $v$ be some vertex. We have new graphs, $G'$ and $T'$. $G'$ and $T'$ are same $G$ and $T$, ...
27 views

### Divide Minimum Spanning Tree into Equal (Disconnected) Chunks [closed]

Does anybody know an efficient algorithm for dividing Minimum Spanning Tree (MST) into equal in size disconnected sub-trees? I'm not saying that it is a particularly hard task, but maybe there exist ...
161 views

### Inviting an optimal subset of persons such that all friends of a person invited are invited

Let's say that you want to invite a person $u$ in party $P$. The person $u$ will join the party if and only if all the friends of $u$ will join the party as well. Otherwise, $u$ will reject your ...
27 views

### How Tarjan algorithm work for the 2-SAT

Tarjan's algorithm for 2-SAT is based on the truth: a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation. But I ...
19 views

### Creating capacity graph for a list of flights?

I have a list of flights and for each flight, I have information like source, destination, flight capacity, arrival time, departure time. There are only 8 distinct values that are populated in the ...
15 views

### Decomposition of graph to subgraphs according to parallel edges

I am supposed to calculate all-pair shortest path lengths of a graph. However, I first need the graph to be decomposed/expanded to a simple one based on the presence of parallel edges. If N parallel ...
41 views

### Maximum value of arbitrage

I'm trying to solve this from The Algorithm Design Manual: 6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time ...
38 views

### Proving that max flows of undirected graph and equivalent directed graph are equal

There is an undirected graph $G$. A graph $H$ is constructed by changing each edge $(a,b)$ in $G$ to a pair of directed edges $(a,b)$ and $(b,a)$. How to prove that the maximum flow in $H$ is equal to ...
21 views

### Graph of size n with girth >2k and minimum degree more than n^1/k

I'm stuck at a proof about Graphs in the context of Graph Spanners. A Lemma says: Let $G$ be a graph with $n$ vertices and $m$ edges. If $G$ has girth more than $2k$, then $m\leq n^{1+\frac{1}{k}}$. ...
70 views

### Enumerate all paths of length 3 in a given tree T

Kind help with an algorithm or any refrence to enumerate all paths of length 3 in a given tree T in the shortest possible time.
29 views

### A heuristic for finding an edge cycle cover

I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph. In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-...
131 views

### How to find a path that connects all the dots in the matrix?

I have a matrix that consists of 0, 1, 2. 0 - dot. 1 - block. 2 - start dot (initial position in the path). I have to create a path from the start dot, that connects all the dots in the matrix and ...
17 views

### Counting nodes within K distance from set of given nodes in a tree [duplicate]

I was going through this article https://www.geeksforgeeks.org/count-nodes-within-k-distance-from-all-nodes-in-a-set/ The question says: Given an undirected tree with some marked nodes and a positive ...
18 views

### Scapegoat Trees: Why are they only loosely a-height-balanced?

From Wikipedia: Even a degenerate tree (linked list) satisfies this condition if α=1, whereas an α=0.5 would only match almost complete binary trees. A binary search tree that is α-weight-...
71 views

### Modifying digraph to make it strongly connected

I came across this problem and have not been able to find a solution. Given directed graph $G$, devise an algorithm to find the minimum number of edges to flip/change/transplant such that the ...
24 views

### You're walking in a maze,you must visit all reachable squares of distance k. The performance of the algorithm is measured by the total distance walked

The maze is a 2D Grid of known width and height. it's composed of squares: a Wall or a room. You cannot walk into walls. from each room you can only get to adjacent rooms. ( you can't teleport) You ...
64 views

### How to find maximum matching edges in undirected tree

Let $B$ be an undirected tree with $|V|$ nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime $\mathcal{O}(|V|)$. My approach: ...
35 views

### Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?

So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
31 views

### Shortest paths from a source in weighted graph with only one negative weighted edge

Of course assuming there aren't any negative cycles. I saw this question somewhere. And i saw a complicated solution which says to build three such graphs and connect between them in a very ...
33 views

### How to build a set of closed chains with a sequence of different vertices?

I have a set of many bi-directional links like A-B, A-C, B-C, A-D, C-D, D-E, etc. I need to find a set of many closed chains with a sequence of different vertices (...
46 views

### Number of maximal cliques in a graph where the largest induced cycle is $C_4$

So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general, it is exponential. I am trying to determine whether the number ...
16 views

### Showing that a directed graph that has a cycle belongs to NL [closed]

DCG = { G | Directed graphs that contains a cycle } How can I proof that DCG belongs to NL?
24 views

### Intuition behind min cut in a flow network? Whether it's baseball elimination or project selection

I was wondering if someone can give me a general definition of a min-cut besides it being the max flow of a network. For example, in the baseball elimination problem, if we wanted to find out if ...
84 views

### Prove or disprove - graph doesn't exists

So, we have a directed graph G whose basis graph is connective. I was asked to prove or disprove If its possible that for every DFS run on G, the output will be two trees containing all G vertices . ...
25 views

41 views

### Computing a pre-topological sort using a BFS/a queue

Computing a topological sort in a DAG using a queue simply amounts to putting the nodes with indegree 0 in a queue, and going through the queue removing these nodes from the graph and adding the nodes ...
14 views

### Whic representation of graph is preferred, anjacency matix or adjacency list? [closed]

I have a graph in which vertices are 100 and edges are more than 300. If I want to represent this graph in either adjacency matrix or adjacency list, which graph representation will be preferred? My ...
36 views

### Doubt on Karger's Algorithm for Min-Cuts

I am learning Karger's algorithm for Min-Cuts.I have been solving 1 problem on it. The first part of the problem asks us to run Karger's Algorithm on a given graph. I have no problem doing that. My ...
25 views

### Finding stages in routing algorithm

I have an undirected graph where I need to find routes of minimum cost in a point to multi-point, but where cost can be reduced by creating intermediate "packs" of routing terminals. I am currently ...
27 views

### Number of spanning trees in undirected simple graph

What is the number of spanning trees in an undirected simple graph? My attempt: Let $m$ be the number of edges in a simple graph, and let $n$ be the number of vertices. Then number of spanning ...