patternMinor
What is the goal of studying all those NP-complete problems?
Viewed 0 times
thethosegoalwhatallstudyingcompleteproblems
Problem
So i'm currently reading a lot of things about graph NP-complete problems, and it seems that the goal of a lot of researchers is to find new results about their complexity, results like "independent set is 1.593 approximable for graphs which doesn't contains K4 K5 P3 as a minor" (this is probably a wrong result i just invented something which looks like a result we could find in a paper), approximation algorithms, parameterized complexity etc ...
But i'm wondering : what really is the goal to study independent set, vertex cover, hamiltonian circuit etc ... ? Do they have real case application ? Is there any software that uses independent set algorithms ?
Or is it only for the theory ? To discover something new in the P vs NP problems ?
To sum up : are NP-complete problems (and i'm particularly interested in NP-complete graph problems) useful in the reality ?
PS : sorry if the title may seem offensive, it is not, i know a lot of searchers study things which does not have much applications in reality, i want to know if it is the case for np-complete problems
But i'm wondering : what really is the goal to study independent set, vertex cover, hamiltonian circuit etc ... ? Do they have real case application ? Is there any software that uses independent set algorithms ?
Or is it only for the theory ? To discover something new in the P vs NP problems ?
To sum up : are NP-complete problems (and i'm particularly interested in NP-complete graph problems) useful in the reality ?
PS : sorry if the title may seem offensive, it is not, i know a lot of searchers study things which does not have much applications in reality, i want to know if it is the case for np-complete problems
Solution
No one are offended by that question, and it's an important question to
ask.
When working in graph theory, we don't believe that proving hardness
results for independent set on $\{K_4, K_5, P_3\}$-minor-free graphs are
"important". However, it is interesting to see why a certain
forbidden minor puts a problem from being, e.g. polynomial time
solvable, to NP-complete. It is then important that that is the
focus.
Here is an interesting problem:
Does edge deletion to claw-free graphs admit a polynomial kernel?
Why is it interesting? Because we know almost everything else about
kernels and edge deletion to $H$-free graphs. This one is interesting
because it is notoriously hard. And hopefully, once this is solved, we
will understand more about the interplay between $H$-free graphs, edge
deletion, and polynomial kernels.
But I want to also mention that, yes, there are indeed applications that use algorithms for independent set, vertex cover, travelling salesman, etc. See for example Dependency hell is NP-complete.
Fast forward to industry. After quitting academia and joining
industry as a developer, I have more than once been able to tell people
that what they are working on is NP-complete, and to provide insight
into a problem that I got from studying these problems in a theoretic
setting.
I have written and published my share of "unusable" algorithms, but it's
not expected that people can take algorithms and plug-and-play them into
their system. What they can take is the insight we provide in
structures, heuristics, as well as hardness. Sometimes a problem is
only hard on graphs that have large grids as minors, and if you suddenly
see that your data is "tree-like", then you might have some tricks to
share with your future industry-colleagues.
ask.
When working in graph theory, we don't believe that proving hardness
results for independent set on $\{K_4, K_5, P_3\}$-minor-free graphs are
"important". However, it is interesting to see why a certain
forbidden minor puts a problem from being, e.g. polynomial time
solvable, to NP-complete. It is then important that that is the
focus.
Here is an interesting problem:
Does edge deletion to claw-free graphs admit a polynomial kernel?
Why is it interesting? Because we know almost everything else about
kernels and edge deletion to $H$-free graphs. This one is interesting
because it is notoriously hard. And hopefully, once this is solved, we
will understand more about the interplay between $H$-free graphs, edge
deletion, and polynomial kernels.
But I want to also mention that, yes, there are indeed applications that use algorithms for independent set, vertex cover, travelling salesman, etc. See for example Dependency hell is NP-complete.
Fast forward to industry. After quitting academia and joining
industry as a developer, I have more than once been able to tell people
that what they are working on is NP-complete, and to provide insight
into a problem that I got from studying these problems in a theoretic
setting.
I have written and published my share of "unusable" algorithms, but it's
not expected that people can take algorithms and plug-and-play them into
their system. What they can take is the insight we provide in
structures, heuristics, as well as hardness. Sometimes a problem is
only hard on graphs that have large grids as minors, and if you suddenly
see that your data is "tree-like", then you might have some tricks to
share with your future industry-colleagues.
Context
StackExchange Computer Science Q#127618, answer score: 5
Revisions (0)
No revisions yet.