Suppose we have a NP-Complete decision problem like independent set or finding matching in graph theory and we change the greatness or smallness of the condition of that problem i.e. change the direction of the inequality in the problem's definition ($ \ge$ or $\le $). For example in independent set problem when the condition is $|V'| \ge k$ and I change it into $|V'|\le k $. Are problems modified in this way still NP-complete?

  • $\begingroup$ No. They become trivial. For example, in independent set, you can take $V'=\emptyset$ and it will always verify $|V'|\le k$. So since your algorithm just has to tell you if such a $V'$ exists, it can simply always answer "yes". $\endgroup$ – xavierm02 Mar 3 '17 at 17:32
  • $\begingroup$ @xavierm02 Please don't post answers as comments. $\endgroup$ – David Richerby Mar 3 '17 at 18:13
  • $\begingroup$ By the way, note that finding matchings is in P, even in non-bipartite graphs. $\endgroup$ – David Richerby Mar 3 '17 at 19:02
  • $\begingroup$ Yes , that's true , I mean the minimum maximal matching problem that is NP-Complete $\endgroup$ – Hamed.K Mar 3 '17 at 22:07

It depends on the problem. For, say, clique or independent set, the problems become trivial if you change the direction of the inequality: $\emptyset$ is always a clique/independent set of size $\leq k$.

On the other hand, the travelling salesman problem remains NP-complete if you ask for a tour of length at least $d$ instead of at most $d$. To see this, suppose that you want a tour of graph $G$ of length at most $d$. Let $m$ be the length of the longest edge in $G$, and let $G'$ be the graph that's identical to $G$ except that, if an edge has length $\ell$ in $G$, then it has length $m-\ell$ in $G'$. Now, any tour of length $t$ in $G$ corresponds to a tour of length $nm-t$ in $G'$ (where $n$ is the number of vertices), so $G$ has a tour of length at most $d$ if, and only if, $G'$ has a tour of length at least $nm-d$.

  • $\begingroup$ Yes , you are right , but what is your opinion about the minimum maximal matching and it's direction of inequality ?? $\endgroup$ – Hamed.K Mar 3 '17 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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