3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What is a problem that is only hard on graphs that have large grids as minors? $\endgroup$
    – alphacapture
    Commented Oct 28, 2023 at 20:25
  • $\begingroup$ @alphacapture This was written three years ago, I don't know exactly what I was thinking, but I was probably thinking about problems on planar graphs that admit fast algorithms on bounded treewidth graphs. $\endgroup$
    – John Kemeny
    Commented Oct 28, 2023 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.