Are there any efficient algorithms to solve longest path problem in networks with cycles?When are Decision Diagrams the right way to model and solve a problem?Combinatorial Optimization: Metaheuristics, CP, IP — “versus” or “and”?Relationship between the Assignment Problem and the Stable Marriage ProblemAlgorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location
Are there any efficient algorithms to solve longest path problem in networks with cycles?
Why do textbooks often include the solutions to odd or even numbered problems but not both?
How would modern naval warfare have to have developed differently for battleships to still be relevant in the 21st century?
How can I politely work my way around not liking coffee or beer when it comes to professional networking?
Vanishing of certain coefficients coming from Coxeter groups
How long would it take to cross the Channel in 1890's?
How does a blind passenger not die, if driver becomes unconscious
Can White Castle?
Hand soldering SMD 1206 components
Are all instances of trolls turning to stone ultimately references back to Tolkien?
Why is the voltage measurement of this circuit different when the switch is on?
Can ADFS connect to other SSO services?
Why is the high-pass filter result in a discrete wavelet transform (DWT) downsampled?
How was Hillel permitted to go to the skylight to hear the shiur
Require advice on power conservation for backpacking trip
Did Karl Marx ever use any example that involved cotton and dollars to illustrate the way capital and surplus value were generated?
Underbar nabla symbol doesn't work
Find the probability that the 8th woman to appear is in 17th position.
What's currently blocking the construction of the wall between Mexico and the US?
Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)
How do I turn off a repeating trade?
Trainee keeps missing deadlines for independent learning
Iterate MapThread with matrices
Should I prioritize my 401(k) over my student loans?
Are there any efficient algorithms to solve longest path problem in networks with cycles?
When are Decision Diagrams the right way to model and solve a problem?Combinatorial Optimization: Metaheuristics, CP, IP — “versus” or “and”?Relationship between the Assignment Problem and the Stable Marriage ProblemAlgorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location
$begingroup$
I have a directed social network and as a preprocessing step i need to calculate longest path lengths for each node. Longest path problem is np hard as far as i know but i've seen dynamic programming methods for DAGs. Is there such a method for general networks with cycles. All arc weights are one.
combinatorial-optimization
asked 8 hours ago
Evren GuneyEvren Guney
241 bronze badge
New contributor
Evren Guney is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I have a directed social network and as a preprocessing step i need to calculate longest path lengths for each node. Longest path problem is np hard as far as i know but i've seen dynamic programming methods for DAGs. Is there such a method for general networks with cycles. All arc weights are one.
combinatorial-optimization
asked 8 hours ago
Evren GuneyEvren Guney
241 bronze badge
New contributor
Evren Guney is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I have a directed social network and as a preprocessing step i need to calculate longest path lengths for each node. Longest path problem is np hard as far as i know but i've seen dynamic programming methods for DAGs. Is there such a method for general networks with cycles. All arc weights are one.
combinatorial-optimization
asked 8 hours ago
Evren GuneyEvren Guney
241 bronze badge
New contributor
Evren Guney is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I have a directed social network and as a preprocessing step i need to calculate longest path lengths for each node. Longest path problem is np hard as far as i know but i've seen dynamic programming methods for DAGs. Is there such a method for general networks with cycles. All arc weights are one.
combinatorial-optimization
combinatorial-optimization
asked 8 hours ago
Evren GuneyEvren Guney
241 bronze badge
New contributor
Evren Guney is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 hours ago
Evren GuneyEvren Guney
241 bronze badge
New contributor
Evren Guney is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 hours ago
Evren GuneyEvren Guney
241 bronze badge
New contributor
Evren Guney is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 8 hours ago
Evren GuneyEvren Guney
241 bronze badge
asked 8 hours ago
Evren GuneyEvren Guney
241 bronze badge
241 bronze badge
New contributor
Evren Guney is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Evren Guney is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
There is no theoretically efficient method, unless P=NP.
The Hamiltonian Path Problem is the problem of determining whether there exists a path in an undirected or directed graph that visits each vertex exactly once. This problem is NP-complete (see link).
If you could determine the longest path efficiently, you could do so for every starting point and ending point. If for any pair the length is equal to the number of points minus one, you have proven that there exists an Hamiltonian path. If not, then there is no Hamiltonian path.
It follows that determining the longest path must be NP-hard.
answered 6 hours ago
Kevin DalmeijerKevin Dalmeijer
832 bronze badges
New contributor
Kevin Dalmeijer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
As observed by Kevin Dalmeijer, you cannot expect an efficient method unless $P=NP$.
Since you're asking explicitly for dynamic programming: define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$. Values $C$ satisfy
beginalign*
C(s,t,V)=
begincases
max_uin N^-(t)setminus V C(s,u,Vcupt)+d_ut, & textif $sneq t$ and $N^-(t)setminus Vneq emptyset$,\
-infty, & textif $sneq t$ and $N^-(t)setminus V=emptyset$,\
0, & textif $s=t$,
endcases
endalign*
where $N^-(t)$ is the set of predecessors of vertex $t$, and $d_uv$ is the distance between $u$ and $v$. Computing $C$ for fixed $s$ takes time $O(n^22^n)$ and space $O(n2^n)$ and $C(s,t,emptyset)$ gives the longest path between $s$ and $t$.
answered 4 hours ago
Marcus RittMarcus Ritt
1,8093 silver badges24 bronze badges
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Evren Guney is a new contributor. Be nice, and check out our Code of Conduct.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f641%2fare-there-any-efficient-algorithms-to-solve-longest-path-problem-in-networks-wit%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There is no theoretically efficient method, unless P=NP.
The Hamiltonian Path Problem is the problem of determining whether there exists a path in an undirected or directed graph that visits each vertex exactly once. This problem is NP-complete (see link).
If you could determine the longest path efficiently, you could do so for every starting point and ending point. If for any pair the length is equal to the number of points minus one, you have proven that there exists an Hamiltonian path. If not, then there is no Hamiltonian path.
It follows that determining the longest path must be NP-hard.
answered 6 hours ago
Kevin DalmeijerKevin Dalmeijer
832 bronze badges
New contributor
Kevin Dalmeijer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
There is no theoretically efficient method, unless P=NP.
The Hamiltonian Path Problem is the problem of determining whether there exists a path in an undirected or directed graph that visits each vertex exactly once. This problem is NP-complete (see link).
If you could determine the longest path efficiently, you could do so for every starting point and ending point. If for any pair the length is equal to the number of points minus one, you have proven that there exists an Hamiltonian path. If not, then there is no Hamiltonian path.
It follows that determining the longest path must be NP-hard.
answered 6 hours ago
Kevin DalmeijerKevin Dalmeijer
832 bronze badges
New contributor
Kevin Dalmeijer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
There is no theoretically efficient method, unless P=NP.
The Hamiltonian Path Problem is the problem of determining whether there exists a path in an undirected or directed graph that visits each vertex exactly once. This problem is NP-complete (see link).
If you could determine the longest path efficiently, you could do so for every starting point and ending point. If for any pair the length is equal to the number of points minus one, you have proven that there exists an Hamiltonian path. If not, then there is no Hamiltonian path.
It follows that determining the longest path must be NP-hard.
answered 6 hours ago
Kevin DalmeijerKevin Dalmeijer
832 bronze badges
New contributor
Kevin Dalmeijer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
There is no theoretically efficient method, unless P=NP.
The Hamiltonian Path Problem is the problem of determining whether there exists a path in an undirected or directed graph that visits each vertex exactly once. This problem is NP-complete (see link).
If you could determine the longest path efficiently, you could do so for every starting point and ending point. If for any pair the length is equal to the number of points minus one, you have proven that there exists an Hamiltonian path. If not, then there is no Hamiltonian path.
It follows that determining the longest path must be NP-hard.
answered 6 hours ago
Kevin DalmeijerKevin Dalmeijer
832 bronze badges
New contributor
Kevin Dalmeijer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 6 hours ago
Kevin DalmeijerKevin Dalmeijer
832 bronze badges
New contributor
Kevin Dalmeijer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered 6 hours ago
Kevin DalmeijerKevin Dalmeijer
832 bronze badges
answered 6 hours ago
Kevin DalmeijerKevin Dalmeijer
832 bronze badges
832 bronze badges
New contributor
Kevin Dalmeijer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Kevin Dalmeijer is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
$begingroup$
As observed by Kevin Dalmeijer, you cannot expect an efficient method unless $P=NP$.
Since you're asking explicitly for dynamic programming: define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$. Values $C$ satisfy
beginalign*
C(s,t,V)=
begincases
max_uin N^-(t)setminus V C(s,u,Vcupt)+d_ut, & textif $sneq t$ and $N^-(t)setminus Vneq emptyset$,\
-infty, & textif $sneq t$ and $N^-(t)setminus V=emptyset$,\
0, & textif $s=t$,
endcases
endalign*
where $N^-(t)$ is the set of predecessors of vertex $t$, and $d_uv$ is the distance between $u$ and $v$. Computing $C$ for fixed $s$ takes time $O(n^22^n)$ and space $O(n2^n)$ and $C(s,t,emptyset)$ gives the longest path between $s$ and $t$.
answered 4 hours ago
Marcus RittMarcus Ritt
1,8093 silver badges24 bronze badges
$endgroup$
add a comment |
$begingroup$
As observed by Kevin Dalmeijer, you cannot expect an efficient method unless $P=NP$.
Since you're asking explicitly for dynamic programming: define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$. Values $C$ satisfy
beginalign*
C(s,t,V)=
begincases
max_uin N^-(t)setminus V C(s,u,Vcupt)+d_ut, & textif $sneq t$ and $N^-(t)setminus Vneq emptyset$,\
-infty, & textif $sneq t$ and $N^-(t)setminus V=emptyset$,\
0, & textif $s=t$,
endcases
endalign*
where $N^-(t)$ is the set of predecessors of vertex $t$, and $d_uv$ is the distance between $u$ and $v$. Computing $C$ for fixed $s$ takes time $O(n^22^n)$ and space $O(n2^n)$ and $C(s,t,emptyset)$ gives the longest path between $s$ and $t$.
answered 4 hours ago
Marcus RittMarcus Ritt
1,8093 silver badges24 bronze badges
$endgroup$
add a comment |
$begingroup$
As observed by Kevin Dalmeijer, you cannot expect an efficient method unless $P=NP$.
Since you're asking explicitly for dynamic programming: define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$. Values $C$ satisfy
beginalign*
C(s,t,V)=
begincases
max_uin N^-(t)setminus V C(s,u,Vcupt)+d_ut, & textif $sneq t$ and $N^-(t)setminus Vneq emptyset$,\
-infty, & textif $sneq t$ and $N^-(t)setminus V=emptyset$,\
0, & textif $s=t$,
endcases
endalign*
where $N^-(t)$ is the set of predecessors of vertex $t$, and $d_uv$ is the distance between $u$ and $v$. Computing $C$ for fixed $s$ takes time $O(n^22^n)$ and space $O(n2^n)$ and $C(s,t,emptyset)$ gives the longest path between $s$ and $t$.
answered 4 hours ago
Marcus RittMarcus Ritt
1,8093 silver badges24 bronze badges
$endgroup$
As observed by Kevin Dalmeijer, you cannot expect an efficient method unless $P=NP$.
Since you're asking explicitly for dynamic programming: define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$. Values $C$ satisfy
beginalign*
C(s,t,V)=
begincases
max_uin N^-(t)setminus V C(s,u,Vcupt)+d_ut, & textif $sneq t$ and $N^-(t)setminus Vneq emptyset$,\
-infty, & textif $sneq t$ and $N^-(t)setminus V=emptyset$,\
0, & textif $s=t$,
endcases
endalign*
where $N^-(t)$ is the set of predecessors of vertex $t$, and $d_uv$ is the distance between $u$ and $v$. Computing $C$ for fixed $s$ takes time $O(n^22^n)$ and space $O(n2^n)$ and $C(s,t,emptyset)$ gives the longest path between $s$ and $t$.
answered 4 hours ago
Marcus RittMarcus Ritt
1,8093 silver badges24 bronze badges
answered 4 hours ago
Marcus RittMarcus Ritt
1,8093 silver badges24 bronze badges
answered 4 hours ago
Marcus RittMarcus Ritt
1,8093 silver badges24 bronze badges
answered 4 hours ago
Marcus RittMarcus Ritt
1,8093 silver badges24 bronze badges
1,8093 silver badges24 bronze badges
add a comment |
add a comment |
Evren Guney is a new contributor. Be nice, and check out our Code of Conduct.
Evren Guney is a new contributor. Be nice, and check out our Code of Conduct.
Evren Guney is a new contributor. Be nice, and check out our Code of Conduct.
Evren Guney is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Operations Research Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f641%2fare-there-any-efficient-algorithms-to-solve-longest-path-problem-in-networks-wit%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
