New answers tagged np-hard
0
As we define v′ if it is in T and is in S
I think you're misinterpreting the definition of $v$:
For each $v \in T$, define $v'=v$ if $v\in S$ or as its neighbor in $S$ otherwise
$v'$ is always defined; it's just a question of what it's defined to be. The above definition means that, if $v \in S$, $v'$ is defined to be $v$, and if $v \notin S$, $v'$ is ...
2
The other answers are correct, but f I may add an observation: it seems like you are conflating classes of problems and particular instances. There are a number of instances that can be solved in polynomial time in classes that are NP-hard in general. For instance, Boolean satisfiability is NP-hard in general, since it reduces to 3SAT. However, there are a ...
5
If the answer to the first question were to be yes, then $P=NP$, as stated in nir shahar's answer. This has not been done.
"The easiest NP hard problem"
However you next asked if any NP-hard problems have been solved in close to polynomial time, for which you might love to learn about what has been called "The easiest NP hard problem" ...
4
Strictly speaking, as the other answers explain, no. A polynomial-time algorithm for an NP-hard problem is not known nor expected to exist. But I think your underlying question is whether or not there are examples of natural NP-hard problems that are, in some sense, easier to solve than some other NP-hard problems.
There are several flavors in which you can ...
10
By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then $P=NP$. So, short answer is - no.
However, its possible to think instead of solving the problems fully, to approximate a solution, or to solve them randomly. There are attempts at attacking from those points of view, but they are not perfect at all. ...
2
It is NP-Hard as others have said, but... sometimes there is an easier way to solve it. You can do a Lagrangian relaxation to essentially remove the NP-hardness solve that problem, and then use that as an initial guess for the original problem. Pekny and Miller essentially did something like to for the Asymmetric Traveling Salesman problem. They reduced it ...
1
Let $G$ be a graph with $2n$ vertices, and choose any node $v$. The edges touching $v$ have weight $n$, and all other edges have weight $-1$. Note that any Hamiltonian cycle in $G$ will have two edges touching $v$ (which add up to $2n$) and $2n-2$ edges of weight $-1$, so the total weight of the cycle is exactly $2$.
Therefore, if $G$ has a hamiltonian cycle,...
0
If $k$ is a fixed known value and does not depend on the graph, then I doubt it would be possible to do it efficiently:
Verifying if a graph has a cycle of size $k$ can be done by checking all potential paths of size $k$ and verify if one is indeed a cycle. Since there are at most $\begin{pmatrix}n\\k\end{pmatrix}(k-1)! = O(n^k)$ such path in a graph of ...
18
This problem (more formally its decision version) is NP-complete.
NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be NP hard.
In the JSP, we have $n$ jobs $J_1, J_2, ..., J_n$. Within each job there is a set of operations $O_1, O_2, ..., O_n$ which need to be processed in a ...
6
Thanks to "user2357112 supports Monica" for pointing out issues! Now fixed.
Let's formulate the decision problem form of this problem, which I'll call Tree Scheduling (TS):
Given a number $k$, and a rooted tree with
tasks $t_1, \dots, t_n$ for vertices, each having some integer duration $l_i$ and requiring some resource $r_i$ from a set $S$ of ...
14
What you are describing is a planning and scheduling problem. Kautz and Selman pioneered the use of Boolean satisfiability and SAT solvers to attack such problems in the early 1990's. SATPLAN, STRIPS, and PDDL are good search terms for further research. There seem to be several planner implementations that take world descriptions written in STRIPS and ...
2
Recognizing that a path is a Hamiltonian path is easy. Finding one in the first place may be hard (the number of candidates is large).
The defining property of problems in NP is that verifying a solution is "easy" (in P). Your problem is one part of verifying a solution of a Hamiltonian path problem. (You also have to verify that the path is a ...
2
Color the vertices in $V \setminus X$ with $2k$ colors at random. With probability $e^{-2k}$, the $V \setminus X$ vertices of your $k$ disjoint triangles will be highlighted.
Suppose without loss of generality that $X = [m]$.
Using dynamic programming, determine for each subset $S \subseteq [2k]$ and $i \in [m]$ whether there exist $|S|/2$ disjoint triangles ...
1
There is no general rule that they necessarily need to be NP-complete in general.
For the specific examples you list, I expect the answer will be that each of those specific examples are NP-complete, but I haven't tried to prove or verify that; that's just speculation.
Top 50 recent answers are included
