Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.
2
votes
1answer
51 views
Converting math problems to SAT instances
What I want to do is to turn a math problem I have to solve into a Boolean Satisfiability problem and then solve it using a SAT Solver. I wonder if someone knows a manual, guide or anything that will ...
4
votes
1answer
80 views
Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?
Given a directed graph with the following attributes: - a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. - additionally a set of nodes having bidirectional ...
-1
votes
1answer
31 views
Reducing from Hamiltonian Cycle problem to the Graph Wheel problem cannot be proved vice versa [closed]
I saw a proof by Saeed Amiri,
We will add one extra vertex v to the graph G and we make new graph G′, such that v is connected to the all other vertices of G. G has a Hamiltonian cycle if and only if ...
2
votes
1answer
89 views
Strategic vertex labeling
We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0. The problem is to ...
-1
votes
2answers
101 views
Wheel subgraph problem [duplicate]
In the following two threads I specified the question in the wrong way (easier to solve that way).
Proving that finding wheel subgraphs is NP-complete
Reducing from Hamiltonian Cycle problem to the ...
0
votes
1answer
25 views
Doubts related to set cover NP-complete problem
I have some doubts related to the set cover ${\sf NP}$-complete problem. I am trying to show that a problem is ${\sf NP}$-complete, so I am trying to transform the Set Cover problem to it.
I am ...
0
votes
1answer
146 views
Reducing from Hamiltonian Cycle problem to the Graph Wheel problem [duplicate]
EDIT: This question is different from the other in a sense that unlike it this one goes into specifics and is intended to solve the problem. In the previous post, the only answer was a hint. In this ...
2
votes
1answer
32 views
Reduction from Vertex Cover to an Independent Set problem
Assume there exists some algorithm that solves vertex cover problem in time polynomial in terms of $n$ and exponential for $k$ with the run time that looks like this $O(k^2 55^k n^3)$. Can we claim ...
5
votes
1answer
91 views
NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?
I have seen some problems that are NP-hard but polynomially solvable in fixed dimension.
Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer ...
1
vote
1answer
30 views
reducing Max3SAT to Max2sat
I want to reduce $MAX3SAT$ to $MAX2SAT$ ...
MAX-n-SAT : given $\phi $ n-CNF formula and number k does $\phi$ has an assignment that satisfy k clauses?
1
vote
2answers
59 views
k-path problem - P, NP or NPC?
I need to determine which complexity class this problem belongs to:
Given a graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of length $k$ exist between thesee two ...
2
votes
1answer
72 views
How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE?
Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET:
INDEPENDENT SET VALUE
Input: An undirected graph G.
Output:The size of the largest ...
3
votes
1answer
66 views
Prove NP-completeness of deciding satisfiability of monotone boolean formula
I am trying to solve this problem and I am really struggling.
A monotone boolean formula is a formula in propositional logic where all the literals are positive. For example,
$\qquad (x_1 \lor x_2) ...
0
votes
1answer
41 views
Reduction from 3-SAT to a graphe problem
I have a question, i was trying to reduce 3-SAT to a particular graph problem and i'm not quite sure about a thing i used in the reduction.
In fact the reduction build a bipartite graph, the edge ...
0
votes
2answers
150 views
Proving that finding wheel subgraphs is NP-complete
Can you help me with this problem ?
Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ ...
-2
votes
0answers
50 views
Convert undirected graph to a directed graph [duplicate]
is it possible to convert G to a directed graph by assigning directions to each
of its edges so that every node in C has indegree 0 or outdegree 0, and every other
node in G has indegree at least 1?
...
1
vote
1answer
57 views
Prove NP-completeness of deciding whether there is an edge-tour of at most a given length
We are given a graph G, integer b < |E|, and subset F in E. The problem is to detect whether there is a cycle in the graph with length at most b and includes each edge in F. Prove that this is NP ...
-1
votes
0answers
31 views
In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges [duplicate]
In a directed graph, the indegree of a node is the number of incoming edges and
the outdegree is the number of outgoing edges. Show that the following problem
is NP-complete. Given an undirected graph ...
7
votes
1answer
103 views
Pebbling Problem
Pebbling is a solitaire game played on an undirected graph $G$ , where
each vertex has zero or more pebbles. A single pebbling move consists
of removing two pebbles from a vertex $v$ and adding ...
-1
votes
2answers
85 views
How to show a problem is NP-complete [closed]
So I'm pretty clueless when it comes to NP complete problems. I'm having a hard time understanding how 3SAT's applied to reduce a problem. Could someone enlighten me a bit?
EDIT: It seems like I ...
2
votes
1answer
59 views
Asymptotic bounds on number of 3SAT formulas with unique solutions
A set is sparse if it contains polynomially bounded number of strings of any given string length $n$ otherwise it is dense. All known NP-complete sets are dense. It was proven that P=NP if and only if ...
1
vote
1answer
16 views
Set cover problem and the existence of such cover
In the set cover problem we want to find in the $\mathbb{S} \subset 2^\mathbb{U}$ the subset $\{s_i\}_{1..k}$, such that $\cup s_i = \mathbb{U}$ for given $K$, where $k \le K$.
But how to reduce the ...
3
votes
1answer
83 views
How does the problem of having a coffee-machine close relate to vertex cover?
Meeting rooms on university campuses may or may not contain coffee machines. We would
like to ensure that every meeting room either has a coffee machine or is close enough to a
meeting room ...
1
vote
2answers
95 views
Show that the following problem is NP-complete
In a directed graph, the indegree of a node is the number of incoming edges and
the outdegree is the number of outgoing edges. Show that the following problem
is NP-complete. Given an undirected graph ...
2
votes
1answer
35 views
Is the 0-1 Knapsack problem where value equals weight NP-complete?
I have a problem which I suspect is NP-complete. It is easy to prove that it is NP. My current train of thought revolves around using a reduction from knapsack but it would result in instances of ...
-3
votes
1answer
170 views
NP-Complete Proof [closed]
$n$ people live in a house and wish to share their expenses equally. Their respective
expenses before settling are $x_1, x_2, \ldots, x_n$. Assume that all of these are greater than 0. They agree to ...
6
votes
2answers
108 views
Can one show NP-hardness by Turing reductions?
In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions.
Is that possible? How exactly? I thought this was only possible by ...
3
votes
1answer
140 views
Do any decision problems exist outside NP and NP-Hard?
This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard.
In order to be in NP, problems have to have a ...
4
votes
0answers
95 views
Fastest known algorithm for 3-Partition problem
3-Partition problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P}=\mathsf{NP}$. I'm looking for the fastest known exact ...
1
vote
1answer
71 views
How to analyze the Steiner tree problem?
I have a problem where I am supposed to analyze the Steiner tree problem by doing the following 3 steps.
1) Look up what the Steiner tree problem is.
2) Find a ...
1
vote
2answers
74 views
Polynomial time reductions using binary search
There are many NP-complete decision problems that ask the question whether it holds for the optimal value that OPT=m (say bin packing asking whether all items of given sizes can fit into m bins of a ...
7
votes
1answer
113 views
How hard is a variant of Sudoku puzzle?
Sudoku is well known puzzle which is known to be NP-complete and it is a special case of more general problem known as Latin squares. A correct solution of the $N \times N$ square consists of filling ...
1
vote
1answer
119 views
Proving NP Completeness of a subset-sum problem - how?
So I'm trying to understand P/NPC problems. The one I'm trying to tackle now is subset sum (we have a collection of integers $S$ and a $k$ param: is there a subset of $S$ that sum of all it's elements ...
3
votes
1answer
56 views
Prove Matrix Correspondence is NP-complete
Consider the following problem. Given a $m \times n$ integer matrix $A$ and a $p \times q$ integer matrix $B$, do there exist one-to-one functions
$$r:\{1,2,...,m\} \rightarrow \{1,2,...,p\}$$
...
3
votes
1answer
125 views
Prove finding a near clique is NP-complete
An undirected graph is a near clique if adding an additional edge would make it a clique. Formally, a graph $G = (V,E)$ contains a near clique of size $k$ where $k$ is a positive integer in $G$ if ...
7
votes
4answers
79 views
Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded?
Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded?
What difference does it make if the input of a ...
2
votes
2answers
103 views
NP-complete and polynomial time reduction
A decision problem is NP-complete if it is in NP and all other problems in NP can be reduced to it by a reduction that runs in polynomial time. Why it is important to require that the reduction runs ...
5
votes
1answer
98 views
$1+\epsilon$ approximation for inapproximable problems
I am currently confused by the following situation:
1) The metric $k$-center problem is inapproximable in polynomial time within $2-\epsilon$ unless $P=NP$.
2) The metric $k$-center problem can ...
3
votes
1answer
69 views
min-cut with extra condition
I have a undirected graph with no edge costs. A subset of the nodes are labeled $c_1, c_2, ..., c_k$ and one node is labeled $K$. I want to find the minimum cut of the graph with the extra condition ...
2
votes
1answer
59 views
Why is MAX-2SAT in NP?
Max-2-SAT is defined as follows. We are given a 2-CNF formula and a
bound k, and asked to find an assignment to the variables that
satisfies at least k of the clauses.
I can understand the ...
6
votes
3answers
159 views
Is there a efficient test for if an NFA accepts a subset of another NFA?
So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $S \cap \bar{R} $, then test if this language is ...
5
votes
2answers
168 views
Doron ZEILBERGER's P = NP computer proof
In 2009 Doron has published a paper stating "Using 3000 hours of CPU time on a CRAY machine, we settle the notorious P vs. NP problem in the affirmative, by presenting a “polynomial” time algorithm ...
1
vote
2answers
129 views
Is 2-DNF is NP-complete?
I want to know whether the 2-DNF problem is NP-complete or not? If it is NP-complete, can anyone provide a proof?
6
votes
1answer
118 views
Showing that minimal vertex deletion to a bipartite graph is NP-complete
Consider the following problem whose input instance is a simple graph $G$ and a natural integer $k$.
Is there a set $S \subseteq V(G)$ such that $G - S$ is bipartite and $|S| \leq k$?
I would ...
9
votes
2answers
330 views
Are there subexponential-time algorithms for NP-complete problems?
Are there NP-complete problems which have proven subexponential-time algorithms?
I am asking for the general case inputs, I am not talking about tractable special cases here.
By sub-exponential, I ...
2
votes
1answer
68 views
How do I explain that a polynomial time reduction is in fact polynomial time?
I have as an assignment question to show that $QuadSat=\{\langle\phi\rangle\mid\phi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$\}$ is $\sf NP$-Complete.
My solution is as ...
1
vote
1answer
40 views
Polynomial time reductions
I'm having a very hard time understanding what's what.
$$L_{1}\leq_{p}L_{2}$$
If $L_2$ is stated to be in $\textbf{NP}$, is it necessarily true that $L_1$ is $\textbf{NP}$-Complete? I need to show ...
5
votes
1answer
62 views
Hardness of Approximating 0-1 Integer Programs
Given a $0,1$ (binary) integer program of the form:
$$
\begin{array}{lll}
\text{min} & f(x) & \\
\text{s.t.} &A\vec{x} = \vec{b} & \quad \forall i\\
&x_i\ge 0 & \quad \forall ...
2
votes
0answers
36 views
Experimental Survey on Different Heuristics for Knapsack Problem
I am looking for a good survey/study of experimental results of heuristics for Knapsack problem (or implemented libraries in java/c++). Any help is appreciated!
3
votes
2answers
89 views
Weak and strong completeness
What does a pseudo-polynomial algorithm tell us about the problem it solves? I don't see how running time improves if the algorithm is exponential in the input length and polynomial in the input ...
