Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
1,258
questions with no upvoted or accepted answers
37
votes
0
answers
647
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$ ...
- 371
20
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.♦
- 154k
16
votes
2
answers
801
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 ...
- 261
12
votes
0
answers
895
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
120
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
225
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 ...
11
votes
0
answers
370
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,934
10
votes
0
answers
87
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 ...
- 5,790
10
votes
0
answers
197
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
236
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
9
votes
0
answers
196
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 ...
- 105
9
votes
0
answers
221
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
9
votes
1
answer
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 ...
- 261
8
votes
1
answer
345
views
Optimality of DSATUR on interval graphs
The DSATUR algorithm is a greedy graph coloring algorithm. It consists of applying the usual greedy coloring algorithm, considering vertices in reverse lexicographic order of (number of different ...
- 12.3k
8
votes
0
answers
414
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. ...
- 121
8
votes
1
answer
277
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$.
...
- 131
8
votes
0
answers
189
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
200
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,458
8
votes
0
answers
141
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
230
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
211
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
242
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
210
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
146
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, ...
- 339
7
votes
0
answers
118
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
215
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,249
7
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 ...
- 478
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
364
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 ...
- 699
7
votes
0
answers
196
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 ...
- 261
7
votes
1
answer
274
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
95
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
540
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\...
- 151
6
votes
0
answers
117
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
383
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
550
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
411
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
93
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,279
6
votes
0
answers
425
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
775
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
131
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 \...
- 364
5
votes
0
answers
213
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
5
votes
0
answers
419
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,421
5
votes
0
answers
199
views
What is the current fastest algorithm for finding the maximum common subgraph?
First of all, it's my first time in #ComputerScience at StackExchange so, my apologies if I'm making some newbie mistake when asking this question.
So, I'm currently researching algorithms for ...
- 101
5
votes
0
answers
343
views
How to convert a dependency graph to series-parallel representation?
I'm given a finite partial order, in the form of a dependency graph between items, and I'd like to have it in series-parallel form (Wikipedia).
So formally, given a finite partial order $\le$ on a ...
5
votes
0
answers
73
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 ...
- 51
5
votes
0
answers
464
views
How to apply ant colony optimization to the TSP but repeating nodes and edges
I'm learning the Ant Colony Optimization Algorithm and I would like to apply it to a variation of the TSP problem (find the path that start from a node, crosses all nodes and finish in the initial ...
- 101
5
votes
0
answers
168
views
MST that contains a shortest $s,t$-path
Consider the problem in which we have an (undirected) graph $G=(V,E)$, weight function $w:E\to\mathbb N$ and a pair of vertices $s,t\in V$, and are required to determine whether there exists an MST $T$...
