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
Why is the voltage measurement of this circuit different when the switch is on?
Is it damaging to turn off a small fridge for two days every week?
Sci fi short story, robot city that nags people about health
3D Crossword, Cryptic, Statue View & Maze
Is this one of the engines from the 9/11 aircraft?
Impossible darts scores
Why aren't cotton tents more popular?
If I wouldn't want to read the story, is writing it still a good idea?
Is adding a new player (or players) a DM decision, or a group decision?
In the Marvel universe, can a human have a baby with any non-human?
Should my manager be aware of private LinkedIn approaches I receive? How to politely have this happen?
Hot coffee brewing solutions for deep woods camping
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?
Vanishing of certain coefficients coming from Coxeter groups
What is the origin of Scooby-Doo's name?
First-year PhD giving a talk among well-established researchers in the field
Is my Rep in Stack-Exchange Form?
Why cruise at 7000' in an A319?
“D’entre eux” to mean “of them”
Employer wants to use my work email account after I quit
Why do some games show lights shine thorugh walls?
Computing a trigonometric integral
Why do textbooks often include the solutions to odd or even numbered problems but not both?
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 9 hours ago
Evren GuneyEvren Guney
242 bronze badges
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 9 hours ago
Evren GuneyEvren Guney
242 bronze badges
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 9 hours ago
Evren GuneyEvren Guney
242 bronze badges
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 9 hours ago
Evren GuneyEvren Guney
242 bronze badges
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 9 hours ago
Evren GuneyEvren Guney
242 bronze badges
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 9 hours ago
Evren GuneyEvren Guney
242 bronze badges
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 9 hours ago
Evren GuneyEvren Guney
242 bronze badges
asked 9 hours ago
Evren GuneyEvren Guney
242 bronze badges
242 bronze badges
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 8 hours ago
Kevin DalmeijerKevin Dalmeijer
932 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 5 hours ago
Marcus RittMarcus Ritt
1,8193 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 8 hours ago
Kevin DalmeijerKevin Dalmeijer
932 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 8 hours ago
Kevin DalmeijerKevin Dalmeijer
932 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 8 hours ago
Kevin DalmeijerKevin Dalmeijer
932 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 8 hours ago
Kevin DalmeijerKevin Dalmeijer
932 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 8 hours ago
Kevin DalmeijerKevin Dalmeijer
932 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 8 hours ago
Kevin DalmeijerKevin Dalmeijer
932 bronze badges
answered 8 hours ago
Kevin DalmeijerKevin Dalmeijer
932 bronze badges
932 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 5 hours ago
Marcus RittMarcus Ritt
1,8193 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 5 hours ago
Marcus RittMarcus Ritt
1,8193 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 5 hours ago
Marcus RittMarcus Ritt
1,8193 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 5 hours ago
Marcus RittMarcus Ritt
1,8193 silver badges24 bronze badges
answered 5 hours ago
Marcus RittMarcus Ritt
1,8193 silver badges24 bronze badges
answered 5 hours ago
Marcus RittMarcus Ritt
1,8193 silver badges24 bronze badges
answered 5 hours ago
Marcus RittMarcus Ritt
1,8193 silver badges24 bronze badges
1,8193 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
