Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

Filter by
Sorted by
Tagged with
10
votes
0answers
61 views

Maximum matching with social distancing

Let $G = (X\cup Y, E)$ be a bipartite graph. Suppose $X$ contains people, $Y$ contains seats in a theatre, and each edge $(x,y)$ has a weight representing how much person $x$ is willing to pay for ...
0
votes
0answers
21 views

Finding the minimized absolute difference of shortest paths of two different starting vertices

I am relatively new to algorithms and I hoped you can help me with the following question. The question can be summarized as follows: Given two different starting vertices, A and B, and a destination ...
0
votes
1answer
176 views

True/False: If v is a leaf in every spanning tree resulting from DFS(s), then v is a leaf in every spanning tree resulting from BFS(s)

Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph. True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning ...
1
vote
0answers
27 views

Determining the number of reachable vertices from every vertex in a directed acyclic graph

Let $G = (V, E)$ be a directed acyclic graph, which is quite sparse (in the examples I have in mind, $|E| \approx 10|V|$ or so). For each vertex $v \in V$, let $f(v)$ be the number of vertices ...
1
vote
0answers
39 views

Exact and approximate agorithms for independent set probem in large graphs

I have a problem which could be stated as follows: Given an unweighted undirected graph $G=(V, E)$ and positive integer $k \leq |V|$, I need to find a subset of vertices $R \subseteq V$ such that $|R| ...
3
votes
0answers
64 views

Coloring nodes and edges in node-weighted graph

I have a graph $G$ with $n$ nodes and $O(n)$ edges. Each of the nodes has a positive integral weight at least 2, such that sum of all weights is at most $O(n)$. We want to color the nodes and edges ...
1
vote
1answer
126 views

Algorithm for finding MST in linear time

Are there any algorithm for finding MST of given graph $G$ in linear time? I found this paper at this link But I can't understand it running time is linear or not.
1
vote
1answer
47 views

Find MST after decrease weight of some edges

We are given an undirected weighted graph $G=(V,E)$ that contains at most $2n$ edges, as well as an MST of $G$. If we decrease the weight of exactly $n$ edges, is it possible to compute an MST of $G$ ...
1
vote
0answers
29 views

Linear programming and network flow

I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, ...
1
vote
0answers
34 views

Finding a path that passes through a given vertex

This is a homework question. Let $G = (V, E)$ be an undirected graph. Let $u, v, w \in V$, find a path from $u$ to $w$ that passes through $v$. I know that I can solve this by running BFS on $u$ and ...
1
vote
1answer
28 views

Vertex cover in a special graph

We say that an undirected graph $G=(V, E)$ is special if for every vertex $v\in V$ and edge $\{u, w\}\in E$, it holds that $\{v, u\}\in E$ or $\{v, w\}\in E$. In other words, a graph is special if for ...
0
votes
0answers
11 views

Find a matching of a bipartite graph that uses all vertices in the left set

I have a bipartite graph already divided into a left and right set, and I would like to find a matching that uses all of the vertices in the left set. To phrase this problem less abstractly, I have a ...
0
votes
1answer
41 views

Why do we consider the + |V| in big-O notation in the time complexity of BFS

It is agreed upon that the time complexity of BFS is $O(|V| + |E|)$. Breath first search usually is used within a connected component. The connected component with the least $|E|$ given a fixed $|V|$ ...
1
vote
0answers
17 views

Visiting vertices on a graph using DFS and BFS

I have this graph that I created and am wondering how DFS and BFS would work on something like this. I made this graph undirected and am going off the premise that if possible, a vertex should be ...
2
votes
0answers
25 views

The practical importance of Graph Isomorphism Problem

It is known that Graph Isomorphism is important in chemistry (studying molecule structures) and in chip design. Are there other applications of significant practical importance, and how much money is ...
1
vote
0answers
66 views

How to find the shortest path that visits all nodes of a non-complete graph (repeating nodes allowed)?

Let $G$ be a non-complete weighted (only positive weights) undirected connected graph. I'm trying to find a path such that it visits all nodes at least once (repeating nodes is allowed), and it's the ...
0
votes
0answers
74 views

Recovering graph given degrees and connectivity information

I have a graph and don't know how nodes in it are connected to each other. I know the number of nodes in the graph. I know the degree of each node in the graph. I know that given any node $A$ that ...
1
vote
1answer
41 views

m-ary tree relation between vertices and leaves

A full $m$-ary tree with $n$ vertices and $i$ internal vertices has $n = m \cdot i + 1$ vertices and $l = (m − 1)i + 1$ leaves. How can I prove it? I know that $m$-ary tree is a rooted tree such that ...
1
vote
1answer
30 views

Linear deterministic algorithm for finding spanning tree T with minimal maximum edge

Given an undirected connected graph $G = (V, E)$ with weights $w : $E → $R$$^+$, define for a spanning tree T the value $λ$(T) = $max_e$∈$T${w(e)} (the maximal edge weight in T ). I need to find a ...
0
votes
0answers
43 views

Shortest path with color constraints

Find shortest path in directed graph (blue and red nodes) that never visits 3 red nodes in a row in $O(V+E)$ time. Not really sure how to approach this.
0
votes
0answers
17 views

Computer network graph design

In the following question, we need to suggest a graph design and a routing algorithm. Routing from $A$ to $B$ is done by returning an edge sequence in the graph that will lead us from $A$ to $B$ ...
1
vote
1answer
34 views

Do Adjacency Lists from Binary Trees go both ways?

From my reading and research it appears it's one way, however my lecturer states that it goes both ways in his examples. Let me show you what i mean by this. He claims that a binary tree built from a ...
0
votes
1answer
26 views

Finding the homomorphism between two homomorphic graphs: what is the name of this problem?

The "graph homomorphism problem" can be stated as: given two graphs $G$ and $H$, determine if there exists a homomorphism $f$ such that $f: G \rightarrow H$. This is a famous problem that is ...
3
votes
1answer
53 views

N points with maximum sum distance

Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100. To calculate the sum of ...
0
votes
0answers
32 views

Dijkstra algorithm for DAG

Assuming we have a K-Partite DAG (edges are directed from one level to the next) with edge weights either 0, 1 or 2. We are looking for the shortest path between a node from group 0 to group k-1 (path ...
0
votes
0answers
23 views

Varient of Traveling Salesman Problem

I am trying to solve a variant of the traveling salesman problem. In this variant, the nodes have a state which is required to go in order. Specifically, first is order food, second is give food, and ...
0
votes
1answer
35 views

Find the directed subgraph with least edges that preserves connectivity

I have a directed graph $G$ with a set of nodes $N$ and a set of edges $E$ with the following property : if $(A\to B)\in E$ and $(B\to C)\in E$, then $(A\to C)\in E$, for all nodes $A,B,C$. I would ...
3
votes
1answer
212 views

Finding the most profitable path

I will be working on a project soon and as I'm clearly not a star (see what I did?) in CS, I'm not sure what to think about this. To put it simply, the problem is the following: We want to go from ...
0
votes
0answers
32 views

Similarity between two sequences

I have two sequences whose similarity I want to measure. Lets say sequence 1 is: abcd and sequence 2 is: badc. These sequences are always of the same length and they contain exactly the same non-...
0
votes
1answer
22 views

Edmonds-Karp shortest path vs largest bottleneck

Depending on where I look, some places (https://courses.engr.illinois.edu/cs473/sp2009/notes/19-maxflowalgs.pdf) describe EK algorithm as choosing the st path with ...
0
votes
0answers
35 views

In a connected graph, determine all nodes reachable with a "edge-simple" path from node A to node B

I'm asked to write an algorithm which determine all points which appear in a "edge-simple" path connecting node A and node B, i-e a path which doesn't go 2 times in the same edge, but it can ...
1
vote
0answers
21 views

Determining whether DAG is semi-connected

I have been asked to write an algorithm which determine whether a DAG is semi-connected. (Recall that a DAG is semi-connected if for any pair of vertices $x,y$, there is either a path from $x$ to $y$ ...
0
votes
0answers
35 views

An approximation algorithm for partitioning metric completed graph

Given complete metric weighted graph $G=(V,E)$ with $n$ vertices. Are there an algorithm that partition $G$ into to disjoint part $(C_1,C_2)$ that sum of heaviest edge $e\in C_1$ and heaviest edge $e'...
1
vote
1answer
29 views

Is the clique problem polynomial-time solvable still in unit disk graphs allowing different sized disks?

Clark et al. proved that the clique problem is polynomial-time solvable in unit disk graphs. Does anyone know if this result holds still if the disks are allowed to be different sizes? Or do such &...
3
votes
1answer
57 views

Weighted maximum match for intervals

Say I have two sets of intervals sorted by time $I_1=[(x_1, y_1),... (x_n, y_n)]$ and $I_2 = [(a_1, b_1)... (a_m, b_m)]$. where $x, y, a, b$ are times in seconds. None of the intervals within $I_1$ ...
1
vote
1answer
34 views

Assigning balls to bins with constraints

Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with ...
2
votes
1answer
31 views

On the relation between several graph parameters

Recently, I came across several parameters of graphs. So I know in general graphs, it might be hard to compare between them, but I'd like to try and see which upper/lower bounds can be made. Some ...
0
votes
0answers
150 views

Problems/properties of dynamic graphs with strong lower bounds

I know from [1] that the lower bound for the maximum hitting time of simple random walk on a dynamic graph is $\Omega(2^n)$. Smoothed analysis has been applied to the maximum hitting time [3] and ...
4
votes
1answer
32 views

Attempting to verify the colorability using Wigderson's Algorithm

The algorithm of Wigderson (see here) can color a graph that is known to be $3$-colorable in $O\left( \sqrt{\left| V \right|} \right)$ colors. This is done in $O\left( |V| + |E|\right)$ time. For ...
2
votes
1answer
80 views

Currently best approximation for graph coloring

As we all know it is $NPH$ to check whether $G=(V,E)$ is $k$-colorable or not. It is also hard to find the chromatic number of $G$. But I'd like to ask what are some good (or best known) approximation ...
1
vote
1answer
81 views

How should i face the cluster editing problem?

The mentioned problem: Cluster Editing Problem. I need to code this problem but i can't understand the algorithm behind it, even when i try to search for resources about graphs into the web; can ...
2
votes
1answer
47 views

Upper-bounding the out-going degree of a graph

Given a graph $G=(V,E)$, I'm looking for a way to orient its edges in a way that will bound its out degree. For example, I can bound the graph's out-degree by $\approx 2\cdot a(G)$, where $a(G)$ is $G$...
1
vote
1answer
49 views

Maximum flow in integer flow network

Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of ...
1
vote
1answer
22 views

Is the first distance that gets assigned to a node in BFS always the shortest distance?

Consider the following bfs pseudo code that calculates distances of all nodes from $s$ in graph $G=(V,E)$. I know that if $G$ was undirected and unweighted, then the above bfs would calculate correct ...
2
votes
0answers
47 views

Variation of the gas station problem

Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $u$ the car ...
1
vote
1answer
53 views

Traversing a directed graph with negative weights

Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
1
vote
1answer
45 views

Algorithm to find the path with minimum bending points on a square grid board

Let's suppose we have a square grid board like the one shown in the picture below: I'm wondering how I can find the path with minimum number of "bending" points (like the ones shown in red) ...
1
vote
1answer
41 views

Given a source and destination, find the path with minimum stress level in a Graph

I faced this problem in a hiring challenge which is now over. I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't ...
2
votes
1answer
50 views

Proof that any algorithm who builds a spanning tree using Cut and Cycle properties is an MST

The Kleinberg and Tardos Algorithm makes the following claim without proof: Any algorithm that builds a spanning tree by repeatedly including edges when justified by the Cut Property and deleting ...
0
votes
1answer
43 views

Boolean formula for graph 3COL

For a given undirected graph $G=(V,E)$ I'm trying to construct a boolean polynomially computable formula $\varphi$ with the following property: $\varphi$ is satisfiable $\iff$ vertices of $G$ can be ...

1 2
3
4 5
87