# Questions tagged [graphs]

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

2,241 questions
Filter by
Sorted by
Tagged with
1answer
38 views

### Winning strategy using Dynamic Programing

Let $G=(V,E)$ be a DAG and let $v_0\in V$. Alice and Bob are playing a game in which every player has his own turn and Bob is starting. In every turn $i$, the player is picking an edge $e=(v_i,x)$, ...
2answers
76 views

### Why isn't an edge-map graph implementation used in practice?

Wikipedia states that three different graph implementations that are used in practice: Adjacency Lists Adjacency Matrix Incidence Matrix While I was learning about these structures, another ...
0answers
14 views

### Check valid flow in a graph

For a flow network $G=(V,E)$ where $s,t \in V$ and capacities $c_e>0$ for $e \in E$. A flow $f$ is given. How can I check whether of not $f$ is a valid flow within the network?
0answers
21 views

### How to update graph modularity in Louvain algorithm to find best community?

There is Louvain algorithm that searches communities in a graph using modularity metrics. As far as I know the most of the implementations of this algorithm use generalised metric version proposed by "...
1answer
43 views

### How to merge a lot of trees into one single graph?

I have a few different trees, which resemble what the AST that compilers often deal with. For example: tree 1 ( (a, b), (c, d) ) Imagine that each tree split represents the function "add", then ...
0answers
22 views

### Forming groups of people such that no group has two people that dislike each other

I had an assignment for the graph theory unit of my data structures course. The problem was given as follows: Every person in a class has at least one other person that they dislike and will not ...
0answers
9 views

### Is Edmonds' Matroid partitioning algorithm optimal w.r.t lexicographical order?

We all know that, given a matroid $(E, \mathcal{I})$, Edmonds' Matroid partitioning algorithm will result in a tuple of $E$-covering, pairwise-disjoint independent sets $(I_1, ..., I_k)$ with optimal (...
1answer
25 views

### how to maximise the no of edges selected in the graph in form of cycles of unbounded length?

Recently i started looking the perfect cycle cover algorithm related to kidney exchange problem where it is considered as NP-Complete for cycles restricted to a length>2. However if cycles are not ...
1answer
33 views

### Normal colorings of cubic graphs to SAT

This problem is related to ”Normal coloring of cubic graphs (part 1) - a previous post. We repeat the definitions, slightly modified so as to get to the point (we define normal edge 5 colorability, ...
0answers
27 views

### Which computational framework lies behind the Chinese “Social Credit System”?

BACKGROUND The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...
1answer
61 views

### Algorithm to compute sum of cost of all path between pair of unique vertices of a tree

Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices. Thus, there are total nC2 or n(n-1)/2 such ...
1answer
83 views

### Enumerate all paths in a given series-parallel graph

Series parallel graph is well-known and widely used. It has a single source and a single destination. The graph can be formed by means of recursive serial or parallel composition. I have a graph ...
1answer
35 views

### Normal colorings of cubic graphs (part 1)

Edit 2019 June 27 Question 3 is new ... Definition A normal $k$-coloring of a cubic graph (3-regular graph) is a proper coloring of the edges with $k$ colors such that each edge an its adjacent ...
1answer
33 views

### Thorup : What is the meaning of super distance?

While reading Thorup's Algorithm to solve SSSP problem, I have one point that I can't understand: super distance. It says: "For each vertex we have a super distance $D(v)\geq d(v)$" $d(v)$ must ...
1answer
60 views

### Forcing an edge to be in S-T min-cut

Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e. So, I tried couple of steps, first, ...
0answers
56 views

### Maximum weighted matching for directed (non-bipartite) graphs

This post concerns mainly non-bipartite graphs. Edmonds (1961) have proposed the Blossom algorithm to solve the maximum matching problem for undirected graphs. The best implementation of it is due ...
1answer
39 views

### Maximum Flow in a Network

Let $N = (V, E)$ be a network in which the capacity of each edge is either $12$ or $18$. Prove or disprove: The value of a maximum flow for $N$ can’t be $56$. I'm trying to figure out how to ...
2answers
26 views

### How can maximum number of minimum cuts of a graph be exactly $n \choose 2$?

According to my instructor, $n\choose 2$ is the maximum number of minimum cuts we can have on a graph. To prove this, he showed the lower bound using an n-cycle graph. To prove the upper bound, he ...
2answers
38 views

### Solving the min edge cover using the maximum matching algorithm

To solve an instance of an edge cover, we can use the maximum matching algorithm. Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least ...
2answers
87 views

### Reducing Graph Reachability to SAT (CNF)

So I came across this problem in my textbook. I was wondering how to develop a reduction from the Graph Reachability problem to SAT (CNF) problem. (i.e. formula is satisfiable iff there exists a path ...
2answers
38 views

### What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
0answers
33 views

### Given complete graph, find optimal path with two costs on each edge

We are given complete graph, such that each edge has two costs $a \text{ and } b$. We should find path that passes through each node once and has minimum total cost. Cost of a path is the maximum of ...
2answers
52 views

### What is the graphic TSP?

I'm not sure if I understand the following definition of the (well-known apparently) Graphic TSP, also known as graph-TSP : ...graph-TSP, that is, the traveling salesman problem where distances ...
1answer
129 views

### Matching Algorithm - How to maximize matched quantity with unique matching rules?

Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules: \begin{aligned} A\leftrightarrow B\\ C\leftrightarrow D\\ B+C\leftrightarrow F\\ D+A\...
0answers
28 views

### count all possible paths of length n in an undirected graph with use of dynamic programming [duplicate]

Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths of a given length n from a given start node, so that fjor every path applies: a) no vertex ...
1answer
46 views

### Shortest path in a incomplete graph

I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
0answers
68 views

### Assign weights to the edges in a DAG so that, for all S and T, all paths from S to T have equal weight

I have a DAG, and on each edge, I have a minimum and maximum weight. I would like to assign (or determine it's impossible to assign) exact weights to each edge so that Each edge's weight is between ...
2answers
65 views

### Count paths of length $n$ that a player can take

I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move ...
0answers
59 views

### divide and conquer algorithm for finding a 3-colored triangle in an undirected graph with the following properties?

In an undirected Graph G=(V,E) the vertices are colored either red, yellow or green. Furthermore there exist a way to partition the graph into two subsets so that |V1|=|V2| or |V1|=|V2|+1 where the ...
1answer
158 views

### how to find total paths in a graph which have only one vertex common with a given path

Assume I have a undirected graph $G$ without cycles (i.e., a forest) and I am provided with pair of nodes $a$ and $b$. How can I find the total number of paths in the graph that do not share any edge ...
1answer
27 views

### Partitioning a graph with specific constraints

We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills ...
1answer
30 views

### How to construct an ordinary matching from a fractional matching?

Given a graph $G=(V,E)$. A fractional matching, say $f$, assigns every edge $e \in E$ to a fraction $f(e) \in [0,1]$, with the constraint: for $v \in V$, $\sum_{e \ni v}f(e) \leq 1$. My question ...
1answer
137 views

### Algorithm for fewest number of moves with artificial minimum

I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum. To summarize, I built an undirected graph with edges ...
1answer
69 views

### Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph?

A minimum-spanning-tree (MST) path is always $V-1$ edges and a Hamiltonian Cycle (HC) is always $V$ edges. Because the HC has an extra edge we could say that in general, the weight of every ...
1answer
31 views

### How to build tree from graph with specific property

We are given connected undirected graph of $n$ nodes and $m$ edges. On each node one integer(value) from $0$ to $n-1$ is written. We need to build tree such that for each node $i$, all nodes in the ...
1answer
36 views

### Finding the maximum disjoint weight in a weighted node graph

I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the ...
1answer
21 views

### Current value of flow in a network

Confused about a question regarding flow networks. Question is: Given the network below, what is the current value of flow in this network? Does the current flow of a network refer to the maximum ...
1answer
28 views

### Given N vertices and M edges find if two nodes are in the same connected component?

Given a set of $n$ people and $m$ friendship relations between those people (relation is between two persons) we need to suggest a data structure that supports the division of those people into ...
1answer
35 views

### Transitive Closure vs Reachability in Graphs

I am facing the most curious situation with [my current information of] transitive closure algorithms. Specifically, is what follows not an algorithm for finding the transitive closure of a graph <...
0answers
20 views

### What algorithms are there to build a junction tree of a graph?

A junction tree of a graph is a tree that represents the graph, so that certain information about the graph is encoded in the tree. What algorithms are there to build a junction tree of a graph?
1answer
30 views

### Graph ordering with smallest max vertex “discrepancy”

Consider an undirected graph $G=(V,E)$ and a bijective function $f:V \rightarrow [|V|]$ which orders the vertices by mapping them onto the first $|V|$ natural numbers. Define the cost of an ordering ...
1answer
34 views

### What algorithm will tell us how to divide-up a round robin tournament into rounds?

We are designing a tournament for a game such as soccer (football) or chess. The tournament is "round robin." By "round robin," we mean that every team gets to play against each other team exactly ...
0answers
21 views

### Single source shortest paths with even path [duplicate]

Given directed graph with non negative weights and vertex s. I need an algorithm that finds shortest paths from s to all vertices and the paths have to be even.
1answer
36 views

### What are examples of applications of the tree decomposition of a graph? [closed]

I am looking for specific applications of the tree decomposition (of a graph), because I want to motivate its existence. What are examples of problems that are more easily solvable using the junction ...
1answer
55 views

### Maximum weight vertex-disjoint paths

I have a complete (every vertex is connected by an edge to every other vertex) undirected positively weighted graph. I want to find vertex-disjoint paths in the graph whose total weight is as large ...
0answers
68 views

### Shortest path for vehicle routing problem with alternative locations

I'm currently developing an algorithm that solves the vehicle routing problem with time windows and the possibility for clients to be delivered to multiple locations. Right now, I'm trying to find ...
0answers
35 views

### Make maze connected removing minimal number of obstacles

Input consists of two numbers $n$ (number of rows) and $m$ (number of columns) with the maze consisting of $2\cdot n + 1$ rows, where each row consists of $2\cdot m + 1$ symbols: '+', '-', '|', '.' ...
0answers
19 views

### Directed weighted multigraph isomorphism algorithms

Are there known algorithms for the isomorphism problem for directed weighted multigraphs? If not, could one be created simply by adapting existing algorithms for graphs or digraphs, or is it entirely ...
1answer
66 views

### Finding a cycle in a graph with the biggest value (the sum of all edges)

I am trying to solve this problem: we have an oriented, weighted graph and we have to find a cycle with the biggest weight. Weight of a cycle is the sum of all edges forming the weight. The preferred ...
1answer
55 views

### Cannibals missionaries problem - solving usings graphs

I am trying to solve the cannibals - missionaries problem; we have the number of cannibals, the number of missionaries and the position of the boat. We are trying to transfer all of them to the other ...