Mixing
Longest path between 2 given vertices in undirected unweighted graph
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Consider undirected unweighted graph. My problem is to find the longest simple path between two given vertices or its approximation.
I was thinking of solution like this - Find the shortest simple path using Dijkstra's algorithm. For every 2 vertices, which are neighbors on that path, simulate that edge between them is missing and try to find another path between them using Dijkstra's algorithm. Then apply it again on newly created path until we are not able to increase size of the path.
I think that this would work but it has very high time complexity.
Can anyone help me with better algorithm or does anyone know any approximation to this problem ?
Thank you.
graph-theory algorithms approximation path-connected
asked Jul 16 at 18:25
User5468622
113
 |Â
show 1 more comment
up vote
0
down vote
favorite
Consider undirected unweighted graph. My problem is to find the longest simple path between two given vertices or its approximation.
I was thinking of solution like this - Find the shortest simple path using Dijkstra's algorithm. For every 2 vertices, which are neighbors on that path, simulate that edge between them is missing and try to find another path between them using Dijkstra's algorithm. Then apply it again on newly created path until we are not able to increase size of the path.
I think that this would work but it has very high time complexity.
Can anyone help me with better algorithm or does anyone know any approximation to this problem ?
Thank you.
graph-theory algorithms approximation path-connected
asked Jul 16 at 18:25
User5468622
113
I presume you are given the initial and final vertices. If so, I suspect you'll need to use a traditional branch-and-bound or tree search algorithm such as $A^*$, since even a single edge can make a path's length maximal.
– David G. Stork
Jul 16 at 18:30
2
if this was possible in polynomial time then we would be able to check if a graph is hamiltonian in polynomial time.
– Jorge Fernández
Jul 16 at 18:44
@JorgeFernández I forgot to write that those 2 vertices are given. Thank you for correction DavidG.Stork
– User5468622
Jul 16 at 19:14
it does not matter
– Jorge Fernández
Jul 16 at 19:17
What kind of approximation error would be appropriate?
– Sudix
Jul 16 at 19:31
 |Â
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Consider undirected unweighted graph. My problem is to find the longest simple path between two given vertices or its approximation.
I was thinking of solution like this - Find the shortest simple path using Dijkstra's algorithm. For every 2 vertices, which are neighbors on that path, simulate that edge between them is missing and try to find another path between them using Dijkstra's algorithm. Then apply it again on newly created path until we are not able to increase size of the path.
I think that this would work but it has very high time complexity.
Can anyone help me with better algorithm or does anyone know any approximation to this problem ?
Thank you.
graph-theory algorithms approximation path-connected
asked Jul 16 at 18:25
User5468622
113
Consider undirected unweighted graph. My problem is to find the longest simple path between two given vertices or its approximation.
I was thinking of solution like this - Find the shortest simple path using Dijkstra's algorithm. For every 2 vertices, which are neighbors on that path, simulate that edge between them is missing and try to find another path between them using Dijkstra's algorithm. Then apply it again on newly created path until we are not able to increase size of the path.
I think that this would work but it has very high time complexity.
Can anyone help me with better algorithm or does anyone know any approximation to this problem ?
Thank you.
graph-theory algorithms approximation path-connected
asked Jul 16 at 18:25
User5468622
113
edited Jul 16 at 19:20
asked Jul 16 at 18:25
User5468622
113
asked Jul 16 at 18:25
User5468622
113
asked Jul 16 at 18:25
User5468622
113
113
I presume you are given the initial and final vertices. If so, I suspect you'll need to use a traditional branch-and-bound or tree search algorithm such as $A^*$, since even a single edge can make a path's length maximal.
– David G. Stork
Jul 16 at 18:30
2
if this was possible in polynomial time then we would be able to check if a graph is hamiltonian in polynomial time.
– Jorge Fernández
Jul 16 at 18:44
@JorgeFernández I forgot to write that those 2 vertices are given. Thank you for correction DavidG.Stork
– User5468622
Jul 16 at 19:14
it does not matter
– Jorge Fernández
Jul 16 at 19:17
What kind of approximation error would be appropriate?
– Sudix
Jul 16 at 19:31
 |Â
show 1 more comment
I presume you are given the initial and final vertices. If so, I suspect you'll need to use a traditional branch-and-bound or tree search algorithm such as $A^*$, since even a single edge can make a path's length maximal.
– David G. Stork
Jul 16 at 18:30
2
if this was possible in polynomial time then we would be able to check if a graph is hamiltonian in polynomial time.
– Jorge Fernández
Jul 16 at 18:44
@JorgeFernández I forgot to write that those 2 vertices are given. Thank you for correction DavidG.Stork
– User5468622
Jul 16 at 19:14
it does not matter
– Jorge Fernández
Jul 16 at 19:17
What kind of approximation error would be appropriate?
– Sudix
Jul 16 at 19:31
I presume you are given the initial and final vertices. If so, I suspect you'll need to use a traditional branch-and-bound or tree search algorithm such as $A^*$, since even a single edge can make a path's length maximal.
– David G. Stork
Jul 16 at 18:30
I presume you are given the initial and final vertices. If so, I suspect you'll need to use a traditional branch-and-bound or tree search algorithm such as $A^*$, since even a single edge can make a path's length maximal.
– David G. Stork
Jul 16 at 18:30
2
2
if this was possible in polynomial time then we would be able to check if a graph is hamiltonian in polynomial time.
– Jorge Fernández
Jul 16 at 18:44
if this was possible in polynomial time then we would be able to check if a graph is hamiltonian in polynomial time.
– Jorge Fernández
Jul 16 at 18:44
@JorgeFernández I forgot to write that those 2 vertices are given. Thank you for correction DavidG.Stork
– User5468622
Jul 16 at 19:14
@JorgeFernández I forgot to write that those 2 vertices are given. Thank you for correction DavidG.Stork
– User5468622
Jul 16 at 19:14
it does not matter
– Jorge Fernández
Jul 16 at 19:17
it does not matter
– Jorge Fernández
Jul 16 at 19:17
What kind of approximation error would be appropriate?
– Sudix
Jul 16 at 19:31
What kind of approximation error would be appropriate?
– Sudix
Jul 16 at 19:31
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
0
down vote
This (finding the longest path between two vertices in a graph even with the length of each edge being 1 or $-infty$) is NP-hard though.
If you could do this, then you could find whether the resulting graph has a Hamiltonian path. (If $G$ has a Hamiltonian path, then for one of the only $O(n^2)$ pairs of vertices $u$ and $v$, there is a path w $n$ vertices starting at $u$ and ending at $v$.) OR in fact a Hamiltonian cycle. (If $G$ has a Hamiltonian cycle, then for one of the only $O(n^2)$ edges $uv$ of $G$, there is a path w $n$ vertices starting at $u$ and ending at $v$ in $G setminus uv$.)
See also:
Finding a longest path on a weighted graph - solvable deterministically and in polynomial time?
[I thought this question sounded familiar, I gave the same answer here too.]
answered Jul 17 at 1:24
Mike
1,675110
Thank you for your answer. Do you know any approximation to this problem ?
– User5468622
Jul 17 at 18:49
ac.els-cdn.com/S0196677403000932/…
– Mike
Jul 18 at 16:12
I used google to find this. But from this link it looks like even finding a path of length $Omega(log^2 n)$ where $n$ is the number of vertices, looks quite challenging, for general graphs. But for "real-world" applications and graphs not so large, maybe a heuristic would do? Depends on the size/additional structure you can glean from the graphs.
– Mike
Jul 18 at 16:14
Thank you for your answer.
– User5468622
Jul 19 at 14:10
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
This (finding the longest path between two vertices in a graph even with the length of each edge being 1 or $-infty$) is NP-hard though.
If you could do this, then you could find whether the resulting graph has a Hamiltonian path. (If $G$ has a Hamiltonian path, then for one of the only $O(n^2)$ pairs of vertices $u$ and $v$, there is a path w $n$ vertices starting at $u$ and ending at $v$.) OR in fact a Hamiltonian cycle. (If $G$ has a Hamiltonian cycle, then for one of the only $O(n^2)$ edges $uv$ of $G$, there is a path w $n$ vertices starting at $u$ and ending at $v$ in $G setminus uv$.)
See also:
Finding a longest path on a weighted graph - solvable deterministically and in polynomial time?
[I thought this question sounded familiar, I gave the same answer here too.]
answered Jul 17 at 1:24
Mike
1,675110
Thank you for your answer. Do you know any approximation to this problem ?
– User5468622
Jul 17 at 18:49
ac.els-cdn.com/S0196677403000932/…
– Mike
Jul 18 at 16:12
I used google to find this. But from this link it looks like even finding a path of length $Omega(log^2 n)$ where $n$ is the number of vertices, looks quite challenging, for general graphs. But for "real-world" applications and graphs not so large, maybe a heuristic would do? Depends on the size/additional structure you can glean from the graphs.
– Mike
Jul 18 at 16:14
Thank you for your answer.
– User5468622
Jul 19 at 14:10
add a comment |Â
up vote
0
down vote
This (finding the longest path between two vertices in a graph even with the length of each edge being 1 or $-infty$) is NP-hard though.
If you could do this, then you could find whether the resulting graph has a Hamiltonian path. (If $G$ has a Hamiltonian path, then for one of the only $O(n^2)$ pairs of vertices $u$ and $v$, there is a path w $n$ vertices starting at $u$ and ending at $v$.) OR in fact a Hamiltonian cycle. (If $G$ has a Hamiltonian cycle, then for one of the only $O(n^2)$ edges $uv$ of $G$, there is a path w $n$ vertices starting at $u$ and ending at $v$ in $G setminus uv$.)
See also:
Finding a longest path on a weighted graph - solvable deterministically and in polynomial time?
[I thought this question sounded familiar, I gave the same answer here too.]
answered Jul 17 at 1:24
Mike
1,675110
Thank you for your answer. Do you know any approximation to this problem ?
– User5468622
Jul 17 at 18:49
ac.els-cdn.com/S0196677403000932/…
– Mike
Jul 18 at 16:12
I used google to find this. But from this link it looks like even finding a path of length $Omega(log^2 n)$ where $n$ is the number of vertices, looks quite challenging, for general graphs. But for "real-world" applications and graphs not so large, maybe a heuristic would do? Depends on the size/additional structure you can glean from the graphs.
– Mike
Jul 18 at 16:14
Thank you for your answer.
– User5468622
Jul 19 at 14:10
add a comment |Â
up vote
0
down vote
up vote
0
down vote
This (finding the longest path between two vertices in a graph even with the length of each edge being 1 or $-infty$) is NP-hard though.
If you could do this, then you could find whether the resulting graph has a Hamiltonian path. (If $G$ has a Hamiltonian path, then for one of the only $O(n^2)$ pairs of vertices $u$ and $v$, there is a path w $n$ vertices starting at $u$ and ending at $v$.) OR in fact a Hamiltonian cycle. (If $G$ has a Hamiltonian cycle, then for one of the only $O(n^2)$ edges $uv$ of $G$, there is a path w $n$ vertices starting at $u$ and ending at $v$ in $G setminus uv$.)
See also:
Finding a longest path on a weighted graph - solvable deterministically and in polynomial time?
[I thought this question sounded familiar, I gave the same answer here too.]
answered Jul 17 at 1:24
Mike
1,675110
This (finding the longest path between two vertices in a graph even with the length of each edge being 1 or $-infty$) is NP-hard though.
If you could do this, then you could find whether the resulting graph has a Hamiltonian path. (If $G$ has a Hamiltonian path, then for one of the only $O(n^2)$ pairs of vertices $u$ and $v$, there is a path w $n$ vertices starting at $u$ and ending at $v$.) OR in fact a Hamiltonian cycle. (If $G$ has a Hamiltonian cycle, then for one of the only $O(n^2)$ edges $uv$ of $G$, there is a path w $n$ vertices starting at $u$ and ending at $v$ in $G setminus uv$.)
See also:
Finding a longest path on a weighted graph - solvable deterministically and in polynomial time?
[I thought this question sounded familiar, I gave the same answer here too.]
answered Jul 17 at 1:24
Mike
1,675110
edited Jul 17 at 1:35
answered Jul 17 at 1:24
Mike
1,675110
answered Jul 17 at 1:24
Mike
1,675110
answered Jul 17 at 1:24
Mike
1,675110
1,675110
Thank you for your answer. Do you know any approximation to this problem ?
– User5468622
Jul 17 at 18:49
ac.els-cdn.com/S0196677403000932/…
– Mike
Jul 18 at 16:12
I used google to find this. But from this link it looks like even finding a path of length $Omega(log^2 n)$ where $n$ is the number of vertices, looks quite challenging, for general graphs. But for "real-world" applications and graphs not so large, maybe a heuristic would do? Depends on the size/additional structure you can glean from the graphs.
– Mike
Jul 18 at 16:14
Thank you for your answer.
– User5468622
Jul 19 at 14:10
add a comment |Â
Thank you for your answer. Do you know any approximation to this problem ?
– User5468622
Jul 17 at 18:49
ac.els-cdn.com/S0196677403000932/…
– Mike
Jul 18 at 16:12
I used google to find this. But from this link it looks like even finding a path of length $Omega(log^2 n)$ where $n$ is the number of vertices, looks quite challenging, for general graphs. But for "real-world" applications and graphs not so large, maybe a heuristic would do? Depends on the size/additional structure you can glean from the graphs.
– Mike
Jul 18 at 16:14
Thank you for your answer.
– User5468622
Jul 19 at 14:10
Thank you for your answer. Do you know any approximation to this problem ?
– User5468622
Jul 17 at 18:49
Thank you for your answer. Do you know any approximation to this problem ?
– User5468622
Jul 17 at 18:49
ac.els-cdn.com/S0196677403000932/…
– Mike
Jul 18 at 16:12
ac.els-cdn.com/S0196677403000932/…
– Mike
Jul 18 at 16:12
I used google to find this. But from this link it looks like even finding a path of length $Omega(log^2 n)$ where $n$ is the number of vertices, looks quite challenging, for general graphs. But for "real-world" applications and graphs not so large, maybe a heuristic would do? Depends on the size/additional structure you can glean from the graphs.
– Mike
Jul 18 at 16:14
I used google to find this. But from this link it looks like even finding a path of length $Omega(log^2 n)$ where $n$ is the number of vertices, looks quite challenging, for general graphs. But for "real-world" applications and graphs not so large, maybe a heuristic would do? Depends on the size/additional structure you can glean from the graphs.
– Mike
Jul 18 at 16:14
Thank you for your answer.
– User5468622
Jul 19 at 14:10
Thank you for your answer.
– User5468622
Jul 19 at 14:10
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853698%2flongest-path-between-2-given-vertices-in-undirected-unweighted-graph%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I presume you are given the initial and final vertices. If so, I suspect you'll need to use a traditional branch-and-bound or tree search algorithm such as $A^*$, since even a single edge can make a path's length maximal.
– David G. Stork
Jul 16 at 18:30
2
if this was possible in polynomial time then we would be able to check if a graph is hamiltonian in polynomial time.
– Jorge Fernández
Jul 16 at 18:44
@JorgeFernández I forgot to write that those 2 vertices are given. Thank you for correction DavidG.Stork
– User5468622
Jul 16 at 19:14
it does not matter
– Jorge Fernández
Jul 16 at 19:17
What kind of approximation error would be appropriate?
– Sudix
Jul 16 at 19:31