Skip to main content

New answers tagged

3 votes

Complexity of 2-coloring with extra constraints

The problem is NP-complete by a reduction from not-all-equal 3-satisfiability (NAE3SAT): Let $$\Phi = \bigwedge_{i=1}^n (l_{i,1} \lor l_{i,2} \lor l_{i,3})$$ be an instance of NAE3SAT. We construct a ...
badboul's user avatar
  • 107
0 votes

is the set of all numbers that sum up a subset sum problem a one way function?

The existence of one way functions is an open problem. As is whether the subset sum problem is solvable with a polynomial time algorithm.
Mikko Pitkonen's user avatar
4 votes

why is there the need for a reduction between clique and multicoloured clique?

The main point of considering the Multicolored Clique problem is that the input of Multicolored Clique already comes with a $k$-coloring which facilitates parameterized reductions to other problems. ...
Christian Komusiewicz's user avatar
6 votes
Accepted

How to prove that a problem is not smoothed-polynomial?

With respect to smoothed analysis, the only case that I am aware of is the paper by Beier and Vöcking (Typical Properties of Winners and Losers in Discrete Optimization. SIAM J. Comput. 35(4): 855-881,...
Bodo Manthey's user avatar
2 votes
Accepted

Hardness of the Metric TSP for the Maximum Metric

It is NP-hard, here's a proof. In [1], it is shown that the Hamiltonian path problem is NP-hard on induced subgraphs of the infinite grid (i.e. graphs that are defined by taking a set of integer ...
Laakeri's user avatar
  • 1,821

Top 50 recent answers are included