Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
1,297
questions with no upvoted or accepted answers
39
votes
1
answer
775
views
Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces
I am curious whether the following problems has been studied before, but wasn't able to find any papers about it:
Given a planar graph $G$, and two vertices $s$ and $t$, find an
$s$-$t$ path $P$ ...
- 391
22
votes
1
answer
2k
views
Could min cut be easier than network flow?
Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
D.W.♦
- 164k
17
votes
3
answers
914
views
Steps that guarantee exiting a maze
Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
- 271
12
votes
0
answers
256
views
Covering a complete graph with n copies of an arbitrary graph: NP-complete?
Given a complete graph $G$, an arbitrary graph $H$, and a positive
integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that
their union is $G$, and each of them ...
12
votes
0
answers
948
views
Optimal meeting point in directed graph
Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$.
I need ...
- 221
11
votes
0
answers
131
views
Min-eigenvalue bound for a random d-regular graph
I need help proving the following fact: Let $G$ be a random $d$-regular graph with adjacency matrix $A$. The smallest eigenvalue $\lambda_n$ of $A$ should satisfy $|\lambda_n| = o_d(d)$. (In ...
- 156
11
votes
0
answers
384
views
Change in the distances in a graph after removal of a node
Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that,
$$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G \...
- 1,944
10
votes
0
answers
104
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 ...
- 6,152
10
votes
0
answers
211
views
Constructing a connected graph with given degree sequence
I am interested in constructing simple connected graphs where each vertex has a fixed number of edges (degree) ahead of time. I had originally assume I could use some modification of the Havel-Hakimi ...
- 211
10
votes
0
answers
240
views
Minimum edge deletion partitioning of a planar graph
I'm interested in the time complexity of the following problem:
Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color ...
- 153
10
votes
2
answers
1k
views
Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?
We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
- 271
9
votes
0
answers
207
views
Complexity of frog game on graphs is exponential, or can we do better?
Frog game initializes by placing one frog on every vertex of a simple connected graph $G$ with $n$ vertices. A move consists of moving all $x\gt 0$ frogs from one vertex to another non-empty vertex to ...
- 117
9
votes
1
answer
293
views
Polynomial time algorithm for finding a maximal monotone subset
Input:
Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$.
Output:
A subset $I\subset\{1,\dots,n\}$ of maximal size such that
$(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$.
...
- 141
9
votes
0
answers
225
views
How to solve the loan graph problem
The problem
A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
- 52
8
votes
0
answers
420
views
Shortest path that can be split into contiguous segments of 5 edges connecting 6 distinct nodes in an unweighted graph
The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics:
Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. ...
- 221
8
votes
0
answers
204
views
MST with possibly minimal diameter
I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph ...
8
votes
0
answers
216
views
Compute the expected size of an approximation of vertex cover
Consider the following randomized approximation algorithm of vertex cover:
Input: A graph G = (V, E).
Output: A set $C_G \subseteq V$ a vertex cover of $G$.
The algorithm:
Set $C_G := \emptyset$.
...
- 4,484
8
votes
0
answers
143
views
Problem with manipulation of colored graph
Consider a finite set of colors and a given an unweighted graph with the following properties:
1) Graph is connected.
2) All vertices of the graph has a color in the given set of colors.
3) No two ...
- 181
8
votes
0
answers
234
views
What is the best algorithm to compute ALL homomorphisms between two rooted labeled trees?
Lets consider two node-labeled rooted trees Q and D.
According to wikipedia definition ( https://en.wikipedia.org/wiki/Tree_homomorphism ) a mapping m from the nodes of Q to the nodes of D is a tree ...
- 343
8
votes
0
answers
219
views
Formulating shortest path as submodular minimization
I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.
The answer ...
- 113
8
votes
0
answers
264
views
Practical algorithms for the disjoint paths problem
Given an undirected graph $G$ and two pairs of vertices $(s_1, t_1), (s_2, t_2)$, the disjoint paths problem (DPP) asks for two vertex-disjoint paths, one from $s_1$ to $t_1$ and the other from $...
- 81
8
votes
0
answers
1k
views
Suurballe's Algorithm: Proof of Correctness
I was reading about Suurballe's algorithm on Wikipedia, for the shortest
edge-disjoint paths problem, i.e. given nodes $s$ and $t$ finding a pair of paths between these nodes, whose accumulated weight ...
- 488
8
votes
0
answers
225
views
Optimizing order of graph reduction to minimize memory usage
Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used.
That is, given ...
- 81
8
votes
1
answer
149
views
Find all the special graphs which can reduced to the shortest paths graph
I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative ...
- 237
8
votes
1
answer
1k
views
Find shortest paths in complement graph
I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, ...
- 349
7
votes
0
answers
480
views
Minimum Number of Edges Added to a DAG to get Unique Topological Order
The question is simple:
Given an unweighted directed acyclic graph, $G = (V, E)$, what is the minimum number of directed edges we need to add to $E$ such that the resulting graph $G = (V, E')$ has ...
- 4,511
7
votes
0
answers
119
views
Guided mining of common substructures in large set of graphs
Disclaimer: I'm not a CS so I basically have no idea what I'm talking about
I have a large (>1000) set of directed acyclic graphs with a large (>1000) set of vertices each; the vertices are labeled.
...
- 91
7
votes
0
answers
218
views
Computing the "at least k friends in common" graph
Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
- 2,269
7
votes
0
answers
2k
views
Stopping condition for goal-directed bidirectional search for shortest path
So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*.
So let $l(u,v)$ ...
- 658
7
votes
0
answers
380
views
Worst-case sparse graphs for Hopcroft-Karp Algorithm
Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
- 729
7
votes
0
answers
200
views
What is the proof for the lemma "For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge"?
For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
- 271
7
votes
1
answer
277
views
Building cycle in rectangle
I have to build a cycle with fixed length $n$ that includes exactly $k$ corners inside $w$ x $h$ rectangle.
For example:
$w = 5\\h=3$
$n = 12\\k = 6$
I have already found out that I need at least $...
- 83
6
votes
0
answers
111
views
Is it possible to efficiently maintain a directed graph where nodes unreachable from the root are deleted?
I have an infinite set of possible nodes $V$ and a "root node" $r \in V$. I would like to maintain a directed graph with the invariant that all nodes in the graph are reachable from $r$. ...
- 185
6
votes
0
answers
106
views
Polynomial time algorithms for graphs and cycles
For a given undirected graph $G$ , let $ c(G) $ denote the length of the longest cycle in $ G $ (by cycle, we mean a closed path without repetitions). Prove that if there exists a polynomial-time ...
- 61
6
votes
0
answers
173
views
Are there $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are internally disjoint? Complexity
Given an undirected graph, two vertices $s$ and $t$, and two integers $k$,$l$ - what is the complexity of finding $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are pairwise ...
- 153
6
votes
0
answers
96
views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
user127619
6
votes
0
answers
543
views
What could we say about that conjecture that yields P != NP?
Let $F$ be the set of all Boolean formulae.
We say that a Boolean formula $\varphi$ is positive (=monotone) if
$\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\...
- 231
6
votes
0
answers
120
views
Placing a tripod in a plane such that it partition a given set of points (with pic)
I would appreciate if anyone could help me with the following problem:
Given a set of 3n points in the plane with n > 0, is it possible to find a placement of a tripod such that each region contains ...
- 141
6
votes
0
answers
76
views
Network Reconstruction from Flow Function
Suppose that $T$ is a set of vertices in an unknown network.
We have oracle $F(X,Y)$ that returns maximum flow value between $X, Y \subseteq T$ in the unknown network.
Can we reconstruct the unknown ...
- 61
6
votes
0
answers
388
views
Trying to find a human-usable method to figure out optimal round 1 openings for this game
I'm trying to figure out optimal round 1 openings for this game: http://generals.io/.
For the purposes of this question, I've simplified some of the rules and mechanics of the game, and I assume that ...
- 111
6
votes
0
answers
216
views
Upper bound on the number of hamiltonian cycles on a $n \times n $ grid graph
What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n $ grid graph?
I did some searching and found that the number of hamiltonian cycles on a planar graph ...
- 161
6
votes
0
answers
564
views
Parallel algorithm to find if a set of nodes is on an elememtry cycle in a directed/undirected graph
I'm looking to find / develop a simple parallel algorithm that does this:
Input:
vs: list of root vertices
max_length: max cycle length
max_dist: max distance to root
Variants
one variant of ...
- 431
6
votes
0
answers
438
views
Are there Some Pairs Shortest Paths Algorithms?
I know that there are All Pairs Shortest Paths algorithms. But I am not sure if they are effective if I am trying to solve the Pairs-Shortest-Path problem for a subset of my vertexes.
The properties ...
- 161
6
votes
0
answers
94
views
Decomposition of graphs that uses centers
Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason (...
- 2,329
6
votes
0
answers
426
views
Shortest path in graph - upgrade an algorithm
We are given a graph with $n$ vertices, $m$ edges, and path edge costs of $x$. For vertices without a direct path that are distant exactly one neighbor, we can add new edge with edge cost $y$. Our ...
6
votes
0
answers
776
views
Minimum vertex-weight directed spanning tree where the weight function depends on the tree
Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$.
The weight function assigns a non-...
- 61
6
votes
0
answers
1k
views
A variation in Ford-Fulkerson algorithm
Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow.
I was thinking that when we augment a path ...
- 377
5
votes
0
answers
109
views
Minimum cost path connecting exactly K vertices
I came across a situation in real life that maps to this optimization problem:
Given a fully connected, undirected, weighted graph with $N \ge K$ vertices, find the simple path connecting exactly $K$ ...
- 51
5
votes
0
answers
135
views
Optimization on hypergraph "refinements"
Given a hypergraph $H = (V, E)$, call $H' = (V, E')$ a refinement of $H$ iff there exists a partition $p : E' \to I$ (where $I$ is an arbitrary index set) such that $E = \{\bigcup_{x \in p^{-1}(i)} x \...
- 374
5
votes
0
answers
249
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 ...
- 51