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
2
votes
3answers
62 views

Shortest path between any origin to any destination through some way stations

How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm? You can visit those way stations ...
0
votes
0answers
40 views

What is the most efficient way to solve a workshop scheduling problem?

I am trying to design an algorithm to solve a workshop scheduling problem. The problem is as follows: I have to schedule a workshop consisting of a finite number of time slots, and a finite number of ...
2
votes
1answer
44 views

Existence of path under weight and value budgets

Consider the following problem: Input: An undirected graph $G = (V, E)$, each edge has a non-negative weight $w_i$ and a non-negative value $v_i$. There are two vertices to represent start point $s$...
0
votes
0answers
13 views

Online bipartite matching problem for task assignment

I have $n$ drivers, each one has a balance (in Us dollars), availability status (true if he is not working already) and number of accomplished tasks in the current ...
2
votes
1answer
29 views

Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial

This question is about section 2.3 of Wilf's ``Algorithms and Complexity'' https://www.math.upenn.edu/~wilf/AlgoComp.pdf in which he analyses the complexity of a recursive computation of the ...
2
votes
0answers
45 views

Optimizing De Boor's algorithm

According to De Boor's algorithm, a B-Spline basis function can be evaluated using the formula: $$ B_{i,0} = \left\{ \begin{array}{ll} 1 & \mbox{if } t_i \le x < t_{i+1} \\ 0 &...
3
votes
2answers
45 views

Graphs of maximum degree three

I'm learning an algorithm for graphs of maximum degree three. My question is: should the graph of that type have at least one vertex with degree three. For example if the maximum degree of some ...
1
vote
0answers
11 views

complexity of computing fractional edge-chromatic number of an edge-weighted graph

Let $(G,w)$ be an edge-weighted graph, where the weights $w(e)$ are assumed to be rational. My question is: What is the complexity of computing $\chi'_f(G,w)$, the fractional edge-chromatic number of ...
1
vote
1answer
52 views

Minimum distance of nodes from a set of two nodes

In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
0
votes
0answers
21 views

UnionFind different version performance

I am studying the Union Find data structure using this material written by Sedgwick et al. I am specifically interested in the versions they call QuickFindUF, <...
0
votes
0answers
37 views

Is it NP-complete to test if a graph contains $t$ $k$-cliques?

Let $(G,t,k)$ - a graph with $t$ cliques with $k$ vertices (there are $t$ cliques of size $k$ in graph $G$), for $t,k > 100$. How to prove that $(G,t,k)$ is NP-complete? It is obvious that it is ...
3
votes
2answers
64 views

Minimize number of DFS searches in a graph

I got a weird homework question about graph. A helicopter is going to land on an island to check the n houses after an earthquake. Some of the two-way roads connecting the houses are destroyed ...
1
vote
0answers
21 views

How to Track Connected Components in a Graph when Deleting Nodes

Suppose you have a graph G, and you want to support the following operations: addNode(Node n) addEdge(Node n1, Node n2) ...
0
votes
2answers
35 views

Spanning trees on disconnected graphs

Can anyone please help me out with my query: can disconnected graphs have minimum spanning trees?
0
votes
0answers
28 views

Is retrospective inference NP-hard?

Here is a minimal working example of the question: Consider a network with nodes arranged in a pyramid: $1$ node in the first row, $1+d$ nodes in the second, $1+2d$ nodes in the third, and so on, ...
1
vote
1answer
29 views

Determining the number of walks between two vertices in a graph

Given a graph G and a set of vertices $(v_1, v_2)$. How can you determine whether there is $\textit{one}$ unique walk between $v_1$ and $v_2$?
2
votes
1answer
47 views

Bellman-Ford - is number of interations greater than diameter?

Diameter of a connected, undirected graph is the smallest natural number d, so that between any two vertices of the graph exist path of length at most d. Prove or disprove: in Bellman-Ford is ...
1
vote
1answer
44 views

Is the number of shortest paths between every two vertices at most 4*n^3?

In every weighted graph with $n$-vertices with negative weights, with $n > 10$, a weight can't appear $n$-times in graph, there are between every two vertices at most $4n^3$ shortest paths. I'm ...
0
votes
2answers
43 views

First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS

I am trying to state, whether the statement is true: During a DFS/BFS, first time visited nodes form a spanning tree, that has the same number of edges whether you use DFS or BFS. Is it true? What I ...
1
vote
1answer
27 views

Tarjan's Algorithm failure case, what am I missing?

I'm having a little trouble with Tarjan's Algorthm. So here's my problem: I have a graph such that these nodes are directionally-connected as shown: ...
0
votes
1answer
43 views

The cheapest path in the graph [duplicate]

I am supposed to decide, if the statement is true or false and use arguments for my answer. In every weighted n-vertices graphs: with no negative weighted edges, with n>10, in which every weighted ...
1
vote
0answers
45 views

Finding negative cycle using Bellman Ford

Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph. The wanted complexity is O(|V|*|E|). I was thinking about using Bellman-Ford to solve the ...
3
votes
2answers
113 views

Single-source shortest paths with even weight

I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even. In another words, we have to find the ...
1
vote
0answers
75 views

Maximum size of BFS open set on a grid

I have a 2D grid of infinite size that can either be 4-connected or 8-connected (as defined in https://en.wikipedia.org/wiki/Pixel_connectivity). I am implementing breadth-first search on this grid ...
2
votes
2answers
37 views

Uniqueness of minimum spanning tree

If G has a unique minimum spanning tree, does that mean the edge weights in G are also unique? if yes why and if no why?
-1
votes
1answer
69 views

Doubt in vertex connectivity less than edge connectivity [closed]

Sir i recently started graph theory. I understood the reason why edge connectivity is less than min degree(remove all vertices incident to min degree vertex). I have doubt in 2nd part of proof when ...
1
vote
0answers
71 views

Find longest path in minimum spanning tree

Given an undirected MST with positive weights how can the longest path be found? Based on the accepted answer in this question Longest path in an undirected tree with only one traversal I've ...
0
votes
1answer
53 views

Help with graph search problem

For the next problem I can not think of how to find a solution with graph searches (I thought it was backtracking but my college professor told me that I should use graph searches, which I do not know ...
2
votes
1answer
47 views

Distributed MST Construction in O(log log n) Rounds in a Clique

I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5. It shows by induction on k (phase number), that ...
1
vote
1answer
47 views

Partitioning a boolean circuit for automatic parallelization

tl;dr: I have a problem where I have a Boolean circuit and need to implement it with very specific single-thread primitives, such that SIMD computation is significantly cheaper after a threshold. I'm ...
1
vote
1answer
74 views

Define the time complexity of Kruskal's algorithm as function

I am trying to define the time complexity of Kruskal's algorithm as function dependant on: the number of vertices V the number of edges ...
3
votes
2answers
53 views

Connection between max independent set and graph coloring

Is there any connection between the size of the largest independent set in a graph, and the minimum number of colors required to color the graph? I know that we can potentially color all the vertices ...
1
vote
2answers
37 views

Chordal graph question

In the below image, the graph is being triangulated (added edges are in red). My question is simple : Is the red edge between nodes 7 and 10 necessary in order to obtain a chordal graph? (this image ...
1
vote
2answers
49 views

Maximal cliques in a multipartite graph - efficient?

I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class. Now I am looking for the optimal subset such that each of the N classes is represented ...
2
votes
1answer
50 views

Is an undirected graph consisting only two connected vertices cyclic?

I have two questions: Does acyclic/cyclic classification only apply to directed graphs? If not, does the following undirected graph have any cycle? A --- B
2
votes
1answer
47 views

shortest path tree algorithm

Suppose we are given a directed weighted graph $G=(V,E)$, a source vertex $s$ and the value of the cheapest path $\delta(s,v)$ for every $v \in V$. I want to find an algorithm for the shortest path ...
1
vote
1answer
50 views

Do the minimum spanning trees of a graph have the same number of edges with a given weight?

I'm asking about the answer here: Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight? I didn't understand the best answer here Choose edge $e \in ...
0
votes
0answers
26 views

Time complexity of finding a fixed-size matching in a hypergraph

Define a size $k$ matching in a hypergraph $H = (V,E)$ to be a collection of $k$ pairwise disjoint edges in $E$. Is anyone aware of the (best-known) time complexity of finding, for fixed $k$, a size $...
1
vote
0answers
83 views

MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

A paper was published recently in Science where the authors minimized the following function: $$E_{\text{Ising}}(s) = -\dfrac{1}{2} \Sigma_{i=1}^{N} \Sigma_{j=1}^{N} J_{i,j} s_i s_j,$$ where $...
0
votes
0answers
49 views

Perfect matching in complete, weighted graph

I'm trying to find pairs in a complete, weighted graph, similar to the one below (weights not shown). For each possible pair there is a weight and I would like to find pairs for including all ...
0
votes
0answers
17 views

Min Cut Algorithm using Randomly inserted directions

I had a question about a different randomized min cut algorithm (I don't think it is as efficient as Karger's algorithm for larger sizes of min cuts but it is more efficient for smaller ones). My ...
0
votes
0answers
27 views

Are these algorithms for detecting cycles in directional graph correct?

I want to detect whether a subset of a directional graph reachable from a given root has a cycle, and print some useful debug information about the cycle. It's not a problem if there's a cycle not ...
1
vote
1answer
54 views

Given a directed acyclic graph (DAG) - what can you say about each case?

Suppose $G$ is a DAG with $n$ vertices, and $v$ is a vertex of $G$. What can we say regarding $v$ if the following holds: A. In all topological sorts, $v$ is at the end of the list. So my initial ...
0
votes
1answer
32 views

Is a subgraph of G always connected

I am trying to figure out if given a connect graph with N nodes and A edges, its subgraphs are connected. In order word: given a graph G, can I have a subgraph of G that is not connected? Or: can a ...
1
vote
0answers
35 views

How to reduce independent set to longest path

A friend and I have tried for several hours to try and find a reduction from independent set to longest path, but the results have not been fruitful. We have tried many methods of graphing and ...
0
votes
1answer
41 views

How to create disjoint sets out of an adjacency list

I'm not a computer scientist, so please bear with me if I'm misusing some terminology. What I'm trying to do is to find the different components of an undirected graph. I have an array of pairs that ...
1
vote
1answer
22 views

Hungarian Algorithm - Bipartite Graph Approach

I have been having some difficulty making sense of the Hungarian Algorithm outlined here. It seems incomplete and/or erroneous to me. The main issue is the line: If R_T ^ Z is nonempty, then ...
2
votes
1answer
60 views

Is there a path of length $k$ between given vertex to a subset of vertices in a connected directed graph

I am trying to find an efficient algorithm that on input $ (G,s,A,k) $ returns true iff $G$ is a connected directed graph, $s$ is a vertex in $G$, $A$ is a set of vertices in $G$ and there is a path ...
-2
votes
1answer
90 views

What will be a faster algorithm that finds the maximum number of party people?

You want to organize a party and invite as many of your N friends as possible so that the following condition is met: at a party, everyone invited must know at least three other guests and must not be ...
2
votes
1answer
31 views

Is spectral radius of a graph related to its radius?

I am searching for algorithms to estimate the radius of a graph, and I found out that there are papers about the spectral radius of a graph. As far as I know, the radius of a graph is $\min_{v \in V} ...