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
1answer
28 views

Difference between Recursion Tree & Binary Tree

What's the difference? is a Recursion tree private case of Binary tree?
2
votes
1answer
187 views

The number of connected components in the context of cyclomatic complexity

Cyclomatic Complexity is defined with reference to the control flow graph of the program through this formula (borrowed from Wikipedia): ...
2
votes
3answers
251 views

For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes

in my notes I have one fact: in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at ...
1
vote
1answer
54 views

Determine if there's a $P_3$ as an induced subgraph in a graph $G$

Given a graph $G$ on $n$ vertices with $m$ edges, show an algorithm that determines if there's a $P_3$ as an induced subgraph in $G$ in $O(m+n)$ time. ($P_3$ is the path on 3 vertices). What I was ...
0
votes
0answers
49 views

LCA for directed graph with cycles

I am trying to find the lowest common ancestor of 2 nodes in a graph with more than 250000 nodes and ...
0
votes
1answer
58 views

Another version of the 3-coloring decision problem?

Given a graph $G$, is there a 3-coloring with colors $c1$, $c2$ and $c3$ such that at most $k$ nodes are given the color $c1$ and that no two adjacent nodes are given the same color? Is there a ...
0
votes
1answer
57 views

Number of vertices of a graph in vertex cover of size $m$

Let $G$ have a vertex cover of size at most $m$ and let the degree of $G$ be bounded by $k$. Then $G$ has at most $m(k+1)$ vertices. Note: Remove all vertices of degree $0$. Answer: The idea is to ...
2
votes
1answer
37 views

shortest path in color-weighted graphs

I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum ...
1
vote
1answer
94 views

Can the loops be in any order in the Floyd-Warshall algorithm?

I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page: ...
2
votes
1answer
120 views

Comparing two algorithms for all-pairs shortest paths

I read in my notes: If we use Dijkstra $|V|$ times ($|V|$ number of vertices) for finding all-pairs shortest paths in graph $G$, we get time complexity for Dijkstra algorithm as $O(VE+ V^2 \log V)$, ...
0
votes
1answer
80 views

4 Vertex Cover Problem is not NP Complete why?

With Given Graph $G$ why finding that $G$ has a vertex cover of at most $4$ is in $P$ and Not in NP Complete. it means there us poly-time algorithm for this problem !!?
1
vote
1answer
74 views

Time complexity of the travelling salesman problem (Recursive formulation)

According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (...
0
votes
0answers
19 views

Min-plus matrix and Shortest path variation

I was solving a problem in which given a directed weighted graph with no self loops (adjacency matrix),I had to find minimum path of length at least K between ever pair of nodes. One method is : let ...
0
votes
0answers
49 views

what is the time complexity of Leiden Algorithm?

I am not able to find out the time complexity of the Leiden Algorithm. Can anyone here help me? https://doi.org/10.1038/s41598-019-41695-z.
1
vote
1answer
56 views

Number of maximal cliques in graphs without common neighbourhoods

Let's consider a graph $G(n)$ of $n$ vertices such as no two vertices in $G$ have the same exact neighbors (different open neighbourhoods to be more specific; I wonder if this kind of graphs have ...
-1
votes
2answers
86 views

Write a pseudo code for a Graph algorithm

Given a DAG $G=(V, E)$ and a function $f(v)$ which maps every vertex to a unique number from 1 to $|V|$, I need to write a pseudo code for an algorithm that finds for every $v\in V$ the minimal value ...
1
vote
1answer
61 views

Time complexity of Tsp using DP

this is the recursion formula for problem : C(i,S) = min { d(i,j) + C(j,S-{j}) } In fact, when I tried to implement it as a code, the following code came to my ...
0
votes
0answers
30 views

How to find the mincut of this flow network?

I am trying to find the minimum cut of this flow network, but I feel like I have the cut wrong. Based off this post, I should try to find all reachable vertices in the residual network once there are ...
3
votes
1answer
46 views

What is the “shortest path heuristic” for the Steiner problem in graphs?

I keep encountering citations of the following article: Takahashi and A. Matsuyama, “An approximate solution for the Steiner problem in graphs,” Math. Japonica, vol. 24, no. 6, pp. ...
0
votes
0answers
65 views

Maximum matching to find the minimum edge cover

Suppose that I have an edge cover for the graph $G=(V,E)$ with non-isolated nodes to be a subset of $E^1$ of $E$ such that every vertex $v∈ V$ is incident to some edge in $E^1$. The size of an edge ...
0
votes
1answer
69 views

Shortest Path with a twist

We are given a Graph G where, s ∈ V and t ∈ V. w:E such that w represents the time from u to v. We have to calculate shortest path between s to t with a twist. The twist is the turbocharger which can ...
1
vote
1answer
31 views

What is the duality between path cover and flow?

Let there be a bipartite directed graph $G=(V,E)$. Let's say we have a path cover of the graph. In some texts it is said that this path cover "induces" a flow on $G$. What does this mean? ...
0
votes
0answers
32 views

Number of Hamilton paths in graphs

I am trying to find a fast algorithm that can compute the number of hamiltonian paths in an undirected graph. I saw this on the web, but it sounds like this finds all hamiltonian paths starting from ...
0
votes
0answers
16 views

What exactly are ancestors in DAG

I am new to graph theory and confused with ancestors definition in DAG(or in general graph). For example in the following DAG 1--->2--->3<---4<---5 If ...
1
vote
1answer
93 views

Is Dual Graph of a Triangulation of a Polygon Tree?

I have read that; if a polygon contains a hole in it, then the dual graph of a triangulation of the polygon not have to be a tree. But could not get it exactly. How is it possible, what is the ...
2
votes
1answer
186 views

Bellman Ford facts and specific question

The Bellman-Ford algorithm checks all edges in each step, and if for each edge the following: $d(v)>d(u)+w(u,v)$ holds, then $d(v)$ will be updated. $w(u,v)$ is the weight of edge $(u, v)$ and $d(u)...
3
votes
0answers
18 views

Spanning hypertree which connects the vertices as slowly as possible

I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, ...
0
votes
1answer
51 views

MST and some facts via an example

$M$ is an MST of the Weighted Graph - $GR$. Let $A$ be a vertex of $GR$ then $M-${$A$} is also MST of $GR-${$A$}. Let $A$ be a leaf of $M$ then $M-${$A$} is also MST of $GR-${$A$}. If $e$ is a edge ...
0
votes
0answers
30 views

Bellman Ford Algorithm in One Sweep

I'm trying to find an efficient algorithm (running time of O(|V|*|E|)) that finds for any graph an order of the edges that allows Bellman-Ford algorithm to run in a single sweep (iteration). I was ...
0
votes
3answers
121 views

What is the difference between directed graph and bidirectional graph?

Is the graph above bidirectional? The image in wikipedia confused me a lot, before I heard about something called as bidirectional graph, I would say the above one a directed graph, but I am not sure ...
1
vote
0answers
53 views

Proving that every graph has an order such that Bellman Ford can run in one iteration

I need to prove that for every given graph, that doesn't contain negative cycles, there is an order of edges so that Bellman-Ford algorithm will finish running after one iteration. I could only solve ...
0
votes
0answers
82 views

What's the fastest time complexity algorithm for finding maximal paths in an unweighted directed graph?

I see a lot of interest online to the problems of finding shortest paths, longest paths, and all simple paths. I'm interested in implementing a state-of-the-art algorithm to find all (simple) maximal ...
1
vote
1answer
43 views

Prove $|d_{s}(u)-d_{s}(v)|\leq1$ in BFS

Trying to prove the following problem: Given a graph $G=(V,E)$ and vertex $s\in V$, prove that: $\forall (u,v)\in E,\ |d_{s}(u)-d_{s}(v)|\leq1$ where $d_s(v)$ is the shortest path from $s$ to $v$ in ...
2
votes
1answer
112 views

How to define a path between two sets of vertices?

In section 17.2 of the book "Combinatorial optimization polyhedra and efficiency" by Schrijver, he describes the Hungarian method for maximum weight matching in bi-partite graphs (with ...
0
votes
0answers
12 views

How to check the existence of a split sandwich in polynomial time

I've been reading the Graph Sandwich Problems from Golumbic, Kaplan and Shamir paper and can't figure out the algorithm to check if a split sandwich exists. I'm assuming that I should not be searching ...
0
votes
0answers
47 views

Maximum cardinality matching of maximum weight

Given a graph, I want to find the matching with the maximum size in terms of edges, but among those matchings, given a real weight function on the edges, the one with the maximum weight. Is there an ...
2
votes
0answers
16 views

Hungarian method: seemingly different algorithms from different sources?

When I look online for examples of the Hungarian method for solving the min-weight assignment problem, for example here, it involves iterating on the cost matrix; subtracting entries from the rows and ...
2
votes
1answer
16 views

What is a disequality path in the context of equality graphs?

A path consisting of a number of disequality edges and a single equality edge A path consisting of equality edges A path consisting of a number of equality edges and a single disequality edge A ...
0
votes
1answer
142 views

Analysis of updating vertex and one example?

I see the following image on google: And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should ...
2
votes
1answer
54 views

Min weighted edge cover - is the greedy algorithm sub-optimal?

The post here: Solving the min edge cover using the maximum matching algorithm provides a way to obtain the min edge cover from a maximum matching by greedily adding edges on top of the maximum ...
1
vote
1answer
23 views

Concept of M-augmenting path to find a larger matching than $M$

I'm reading section 16.1 of the book, Combinatorial optimization, Polyhedra and efficiency by Schrijver. Here, he starts with a matching $M$ and describes a path $P$ that is $M$-augmenting if: The ...
2
votes
1answer
42 views

2-Approximation algorithm for for messages across a cyclic network

Question There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) ...
1
vote
0answers
74 views

Strong orientation graph algorithm with Robbins' theorem

I've been asked a question that goes something like this: Using depth-first search and Robbins' theorem, design and analyze an efficient algorithm to construct a strong orientation of a given ...
0
votes
1answer
26 views

Cut edge and cut vertices

If $e = \{u, v\}$ is a cut edge with $\deg(u)$ and $\deg(v)$ both at least 2, then $u$ and $v$ are cut vertices. I want to prove or disprove this statement, but don't know how to proceed. I do know ...
1
vote
1answer
47 views

Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints

I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'⊂V$ such that $R⊂V'$, $N[V']=V$, $∀v'∈V '[∃r∈R ($path($r', v'$)$)]$ that ...
2
votes
1answer
95 views

Min weighted edge cover: don't follow proof in Schrijver

I'm reading section 19.3 of Combinatorial Optimization by Schrijver where he details an algorithm for finding the min-weight edge cover. His method works for general graphs, but I'm particularly ...
1
vote
1answer
50 views

3Col reduction Variation, Special edges

I have a question concerning NP reduction. My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding ...
0
votes
1answer
55 views

Undirected graph whose BFS and DFS trees have roots of degree 2

Draw a graph on $5$ vertices that satisfies all of the following conditions: $G$ is an undirected connected graph. For every node $v∈V$, in the spanning tree received by BFS($v$), $\deg v=2$. For ...
5
votes
0answers
130 views

Finding the Hamiltonian cycle that uses the least amount of straight lines

How can i find the Hamiltonian cycle on an nxn grid that uses the least amount of stright lines (curves left/right as much as possible)? Here's an example we have devised for 8x8: Here is an example ...
0
votes
0answers
22 views

Delete edges (to make it oriented) preserving the strongly connected property

A directed graph is said to be oriented if for all edges (i, j), (j, i) is not an edge. In other words, the binary relation defined by the edges is asymmetric. Given a strongly connected directed ...

1
3 4
5
6 7
81