Questions tagged [path]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
35 views

Path Through Graph That Minimizes Node Attributes

I have a directed graph (DAG) containing many nodes, all with various attributes (node attributes not edge attributes). I have a single target (finish) node and a set of source (start) nodes. I want ...
laurence 's user avatar
7 votes
3 answers
140 views

Finding a set of edges $E$ such that every $s$-$t$-path contains at least 2 edges from $E$

Given an undirected graph $G$ and two vertices $s$ and $t$, i want to find a minimum set of edges $E$ in $G$ such that every (simple) $s$-$t$-path contains at least 2 edges from $E$. Is this problem ...
tgnome's user avatar
  • 153
12 votes
1 answer
1k views

How to find a "short" walk that visits all vertices of a strongly connected directed graph

I am interested in the following algorithmic problem: Given a strongly connected directed graph $G$, I want a "short" (see below for what I mean by short) walk that starts with an arbitrary ...
Michal Dvořák's user avatar
2 votes
0 answers
54 views

Are there $r$ pairwise edge-disjoint $k$-sets of internally disjoint $s$-$t$-paths? Complexity

Given an undirected graph, two vertices $s$ and $t$, and two integers $k$ and $r$, then a $k$-set of internally disjoint $s$-$t$-paths is defined to be a set of exactly $k$ $s$-$t$-paths that share no ...
tgnome's user avatar
  • 153
6 votes
0 answers
167 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 ...
tgnome's user avatar
  • 153
0 votes
0 answers
12 views

Collaborative Multi Agent Path planning on directional and non-planar graph

I am trying to implement a multi-agent path planning algorithm that works on non-planar graphs and large agents (that is, collisions may at the intersection of two edges and at points where the edges ...
CubeArrow's user avatar
3 votes
1 answer
37 views

Trajectories with collisions

Say that I have a plasma gun: It's easy to compute the trajectory of the plasma ray starting from the gun. However, another ray may come from afar: As everybody knows, plasma rays are deviated when ...
cdupont's user avatar
  • 131
2 votes
0 answers
64 views

What is the depth distribution of a random binary tree with n nodes?

Assume I generate a random binary tree with a bounded height with $n$ nodes. For a given key we measure the length of its path (the maximum can be $n-1$). So my Question is what is the distribution of ...
Jungle's user avatar
  • 21
0 votes
0 answers
12 views

Existence of a Path from Initial to Accepting Configuration in Turing Machine Runs: A Reduction-Based Proof

Is it possible to show, by reduction(Reduction in the length of the path and the running time), that for a Turing machine M and an input X, there exists a run in which M accepts X if and only if there ...
Lupital's user avatar
0 votes
1 answer
98 views

Pathfinding in a known maze with step limitations, points of interest and more

I hope this is the correct subpage of SE, if not please direct me to the more appropriate place. Imagine the following scenario: You are put into a random but known position inside a given maze. The ...
Plagiatus's user avatar
  • 101
1 vote
1 answer
135 views

Finding a family of graphs that displays a certain characteristic

I've read that the number of distinct paths in a graph can be exponential in relation to the number of vertices, later I encountered a problem which I spent some time trying to solve on my own. The ...
Aishgadol's user avatar
  • 355
2 votes
1 answer
58 views

EvoPathfinding - Stuck in local optimal

I am using a Genetic Algorithm framework to solve a path-finding problem. Specifically, given the following 32x32 maze: ...
ex1led's user avatar
  • 121
3 votes
1 answer
300 views

Show all chains per user

Some time ago I had in one of the big tech interviews the following question that I still don't know how to approach it. You have a chains of reservations from AirBnb: ...
Andrei T's user avatar
4 votes
1 answer
367 views

Approximation ratio on (1, 2)-metric Travelling Salesman Problem (TSP)

I encountered a problem, where I am given a (fully-connected) graph within a metric space, where each edge weight is either 1 or 2. My task is to prove that the following greedy algorithm gives a $\...
NiRvanA's user avatar
  • 159
0 votes
1 answer
27 views

2VertexDisjointPaths ≤p SimpleCycle

Given the following problems: 2VertexDisjointPaths: Given: a directed Graph $G$ und vertices $s1, s2, t1, t2$. Question: Do paths $p1$ from $s1$ to $t1$ and $p2$ from $s2$ to $t2$ exist if $p1$ and $...
HelloCS's user avatar
2 votes
0 answers
41 views

Finding a circle within a circle

Let $G=(V,E)$ be undirected, and let $s,t\in V$ and $C\subseteq E$ be a circle that contains $s$ and $t$. Assuming $s$ and $t$ are on the circle $C$, we are given a set of edges $F\subseteq E$ which ...
Eric_'s user avatar
  • 445
4 votes
0 answers
58 views

Algorithm to find equivalent classes of homotopic pathes on a grid with obstacles

Given a $n \times n$ grid with some walls and two cells $a$ and $b$, I want to compute the non-homotopics paths from $a$ to $b$ on this grid. A path is a sequence of adjacent cells (diagonal does not ...
Johan's user avatar
  • 141
0 votes
1 answer
154 views

Point Cloud Complete 3D Area Coverage Path Finding Algorithm

So I have a point cloud, of a 3D object, as an input which I received from a 3D scanner. I would like to generate a path which covers the entire object, meaning I would like to come up with a complete ...
ariel1987's user avatar
0 votes
1 answer
138 views

Find most vertices in a directed tree where no path of length less than 3 connects any pair

Given a directed tree $T = (V, E)$, we need to find a set of vertices $A \subseteq V$ such that for every two vertices $v,u \in A$ either there is no path between them or the path between them is of ...
Mohamad S.'s user avatar
1 vote
1 answer
500 views

How to find lightest path in directed weighted graph where each edge has a color

We're Given a directed graph $G = (V, E)$ and a weight function $\omega : E \rightarrow \mathbb{Z}$. Each edge is colored with one of these colors: Red, Green, Blue. Given two vertices $s,t \in V$, ...
Mohamad S.'s user avatar
1 vote
0 answers
72 views

Finding optimal path for a reproduction problem

Given a finite set of lists with elements ($e_1, e_2,..., e_7$) and $e_i = True, False$. It is possible to create a new list by taking two lists and apply the $\land$ operator on both lists ($e_i$ in ...
Okano's user avatar
  • 61
0 votes
2 answers
31 views

Adding Links to Reduce Diameter

Given an unweighted graph $G$, the problem is to add links to the graph with total minimum cost such that the diameter of the graph becomes at most a constant $k$? The cost of adding a link $(u,v)$ is ...
Brian's user avatar
  • 129
1 vote
1 answer
72 views

Find the k length path that maximize a node associate metric

Let's say I have : a Graph g v vertices. Each vertex is associated to a cost c. A special vertex called the starter vertex or vs. I want to find the path p of length 10 (for example), that start ...
hans glick's user avatar
1 vote
2 answers
259 views

Find every edge for which every s,t-path in a DAG goes through that edge

Given a connected sourced/sinked directed acylic graph $G = (V, E \subseteq V^2, s \in V, t \in V)$, we want to enumerate the edges $e \in \mathsf{Bottleneck}(G) \subseteq E$ for which every $s$,$t$-...
taktoa's user avatar
  • 364
1 vote
0 answers
28 views

Forward Path scoring mechanism

...
sten's user avatar
  • 139
2 votes
1 answer
54 views

Reducing infinite paths of a transition system to its set of sets of states

Consider a transition system defined by $\langle S,T \rangle$, where $S$ is a set of states and $T \subseteq S \times S$ is a set of transitions, where $T$ is total, i.e. for every state $s$ there is ...
Sindri P.'s user avatar
1 vote
1 answer
583 views

Longest path in a strongly connected component

So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component. My idea is: In a strongly connected component ...
pk00's user avatar
  • 27
2 votes
1 answer
286 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 ...
giorgioh's user avatar
  • 317
0 votes
1 answer
223 views

Maximum Capacity Path Problem with constraints

I was trying to develop an algorithm for maximum capacity problem with constraints but couldn't figure out the necessary changes required for correct output. The problem is: Given an undirected graph ...
Puneet's user avatar
  • 52