# Tagged Questions

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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) ...
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 ...
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$ ...
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? ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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\}$$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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!
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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 77, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9364688992500305, "perplexity_flag": "middle"}