# Questions tagged [np-complete]

Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science

472 questions
1answer
17 views

### A standard way to reduce a k-SAT to 0-1 Integer Linear Programming

I was searching for a standard (a published paper) for which it reduces a k-SAT to a 0-1 ILP (Integer Linear Programming), but couldn't find any :( I know how to reduce a SAT problem to an ILP ...
1answer
53 views
+50

### What is a language “expressible” in second/first-order logic?

This paragraph in the wikipedia page of the P vs NP problem tries to explain a characterization of languages in P and those in NP, however this characterization is not very clearly stated. Indeed, ...
0answers
15 views

### Reducing knapsack problem to a inversed knapsack problem

1)Suppose we have a common 0-1 knapsack problem. Given a set of n items numbered from 1 up to n, each with a weight w_i and a value v_i, along with a maximum weight capacity W. Here we need to select ...
0answers
11 views

### Domination problem is NPC

I call the problem as DOM. Given a graph $G$ and an integer $d$, Decision problem DOM - "Does there exists a dominating set of size less than or equal to 'd' in G? " DOM is NP Complete problem. But, ...
0answers
50 views

### Reduce Hamiltonian Path Decision Problem To Hamiltonian Cycle Decision Problem

Person A requires that he determine whether or not a particular graph G = (V,E) has a Hamiltonian path from vertex a to vertex b. His colleague Person B has implemented a function that takes an ...
1answer
33 views

### igraph - Minimum vertex set origin for destination

Part igraph question, part graph theory question. I have a digraph from a set of origin vertices (warehouses) to destination vertices (customers). A given origin vertex has edges only to a limited ...
1answer
96 views

### Is the following problem NP-complete?

Let $G=(V,E)$ be a directed graph and let $p_{ji}$ be the minimum path weight from $j$ to $i$; Then I can obviously save the path weights in a matrix $P$ similar to an edge weight matrix; Now the ...
0answers
38 views

### Closest string attempted algorithm. [closed]

In theoretical computer science, the closest string is an NP-hard computational problem, which tries to find the geometrical center of a set of input strings. To understand the word "center", ...
1answer
69 views

### Using the reduction of 3-SAT to 3-COLOR, explain why complexity proofs by reduction work.

I'm reading about the proof that 3-COLOR is in NP-Hard, by reduction of 3-SAT to 3-COLOR (as listed here for example: http://cs.bme.hu/thalg/3sat-to-3col.pdf). And here's a passage from Wikipedia, ...
1answer
35 views

### approximation algorithm for TSP and P=NP

i recently read an article about approximation algorithms for solving the TSP problem. One of the first theorems in this article states: if there is an α-approximation algorithm for the TSP (...
0answers
50 views

### Is Elliptic Curve Discrete Logarithm Problem NP-Hard or NP-Complete

I have trouble classifying Elliptic Curve Discrete Logarithm Problem as NP-Hard or NP-Complete. Where does ECDLP belong? Any brief comprehensive answer is encouraged. Thanks.
0answers
101 views

### Proof of Validity of My Polynomial Time Algorithm for $co-NP$ Complete Problem

I posted an algorithm yesterday, that purported to solve the co-NP Complete 'Boolean Tautology Problem' in polynomial time. Link to the algorithm : polynomial time algorithm In that post, I presented ...
1answer
33 views

### Sudoku solution size

We know an $n$-Sudoku puzzle is with $n \times n$ subgrids consisting of $n \times n$ cells; you will fill it with numbers from $1$ to $n^2$. Candidate solution have size polynomial in $n$, and can ...
0answers
11 views

### Faster boolean expression satisfaction

Few months ago I started to code message filtering for email. The filters are basically set of boolean operators, for example OR(Has(a), NOT(OR(Has(b),Has(c))), AND(Has(e), Has(f)))..., that decide ...
1answer
27 views

### how to find a solution of an np complete problem given a solution to another np complete problem?

Is it correct to say that give a solution (with any time complexity) to an NP-Complete problem it can be modified in some way so that it can solve all NP-Complete problems? If yes, then how can that ...
0answers
60 views

### Is this kind of “Gerrymandering” NP-complete?

Consider the following simplified form of "Gerrymandering": You have $n^2$ squares arranged as an $n\times n$ matrix. Each square is marked with either $0$ or $1$ which means a "voter preference" ...
1answer
97 views

### Reduction from 3-SAT to MAX 2SAT

For some time I've been trying to understand reduction of 3-SAT to MAX 2-SAT. I reviewed most of most popular books about computational complexity (Thomas Cormen, Papadimitriou) but I can't find an ...
1answer
35 views

### Is the generalized assignment problem with un-capacitated agents NP-hard?

I am working on a generalized assignment problem which I typed below. I know it is shown to be NP-hard. I am wondering whether the problem is still NP-hard when the capacity of the agents are assumed ...
0answers
53 views

### Filling a big rectangle with small rectangles

There are N numbers; their values are A1, A2, ..., An respectively, their sum is S. There is a big rectangle which area is S. You need to draw N number small rectangle which area is its value. ...
0answers
13 views

### How to solve $PARTITION$ using this optimization problem?

$PARTITON=\{<S>:\:S\:is\:a\:finite\:set\:of\:whole\:numbers\:and\:\exists T\subseteq S \:such \:that \sum T=\sum (S-T)\} \:$ The summation for $T$ for example is to sum all the numbers in $T$ ...
0answers
119 views

### How can I prove that clust-p is NP-complete?

CLUST-P: Instance: A a non-empty set, α : A × A → N, p, s ∈ N Question: Does A have a partition, A1, A2, . . . , Ap, such that max α(u,v) <=s, u,v∈Ai ∀1 <= i <= p? It is obvious that A ...
2answers
81 views

### Minimum transactions to settle debts among friends

You are given $n$ integers $x_1,x_2,\dots,x_n$ satisfying $\sum_{i=1}^n x_i=0$. A legal move is to choose an integer $a$ and two indices $i,j$, and to increase $x_i$ by $a$ and decrease $x_j$ by $a$. ...
0answers
60 views

### Number of divisors of a number - in NP?

I'm trying to show that the language $\{(m,n) | m \space \text{has exactly} \space n \space \text{divisors}\}$ is in NP. The input $(m,n)$ is in binary. The non-deterministic Turing machine for the ...
1answer
24 views

### satisfying boolean n variable DNF formula

I have an n variable boolean DNF formula and an input set,z consisting of n-tuples. Each tuple consists of truth/false assignment to n variable. the number of tuples in Z is not fixed, obviously <= ...
0answers
14 views

### Reduction of Steiner Tree to Maximum Weight Connected Subgraph

I want to proof that the MWCS is an NP-hard problem by proofing that its decision version is NP-Complete. Below I have my proof so far and I hope people can give comments whether it can be formulated ...
0answers
52 views

### Set cover problem NP completeness

I have a quick question about Set cover problem. In Wikipedia, < https://en.wikipedia.org/wiki/Set_cover_problem >, they are saying "The decision version of set covering is NP-complete, and the ...
1answer
53 views

### Show that the 3-color problem is in P when the input graph is a tree.

This one is from university assignment. I am completely stuck on this one and I searched the internet but couldn't find a explanation. Show that the 3-color problem is in P when the input graph is ...
0answers
22 views

### Partition Problem Variant

I'd like to ask to solve a variant of set partition problem. Suppose we have some items $V = \{1, \cdots, n\}$ and a subadditive cost function $f: 2^V \to R^{+}$. For any partition $P$ of $V$, define ...
0answers
11 views

### Complexity of maximizing sum of fractional functions under cardinality constraint

Considering the following optimization problem: $max_{x} \ \sum_{i=1}^n \frac{W_i}{D_i - z_i},\quad s.t.\ \sum_{i=1}^n z_i \leq k,z_i\in[0,k]$, where $W_i$ and $D_i$ are postive constants and $z_i$ ...
1answer
68 views

### Maximizing the total number of feasible constraints of a linear program

I have an optimization problem with $N$ linear inequality constraints and $K$ real valued parameters (e.g. $0.2\alpha_1+0.5\alpha_2\geq 0$, $K=2$) and no objective function. Here $N$ is much larger ...
1answer
38 views

0answers
25 views

### NP-hardness proof of a model with a convex objective

Let $T=(V,E)$ denote a tree. Each node $j \in V$ in the tree has a known attribute $c_j$. From T, construct a bi-directional graph $G' = (V, E')$ where $E' = \{(j,k), (k,j)| (j,k) \in E\}$. Simply, ...
0answers
68 views

### A Language in CNF with distinct variables per clause and each variable appears in at most three literals is in P

Let A be a language defined thus A = {φ | φ is in CNF, with three literals, comprising distinct variables, per clause; and each variable appears in at most three literals; and φ is satisfiable} . ...
1answer
34 views

### NP Completeness of a Graph Problem, Proof Required

I have a graph problem that I would like to prove NP-completeness. It is outlined below: A graph problem compromising of two graphs, say $G_1(V_1,E_1)$ and $G_2(V_2,E_2)$ such that $V_i$ and $E_i$ ...
1answer
37 views

### Why is showing that ILP in NP not trivial

I have a question regarding the topic of showing that ILP is in NP What is the problem with Guess and Check? Guess a solution and then check if it is optimal. Or further: Calculate a solution via ...
1answer
37 views

### Is the n-Queens problem only np-complete for the task of finding all setups or also for finding any solution?

I have read on Wikipedia that the n-Queens problem is NP-complete when it comes to finding all possible solution implies it that finding one possible solution is also NP-complete?
1answer
25 views

### Big-O for $\Sigma_{i = 1}^{N} i \times \binom{N}{i}$ [closed]

How to solve Big-O for $\Sigma_{i = 1}^{N} i \times \binom{N}{i}$? Can I simply say it is in $O(N!)$?
1answer
33 views

### GI-Completeness of graph isomorphism with connected graphs

The Wikipedia page for Graph Isomorphism lists connected graphs as GI-complete. The citation has a paywall, and I have not been able to find any NP-complete algorithms for isomorphism of connected ...
0answers
82 views

### How to prove a submodular maximization problem is NP-hard

We know that a submodular maximization problem of the form $$\mathcal{P}: \,\, \mathop {\max }\limits_S f\left( S \right)$$ where $f(S)$ is a submodular set function, is NP-hard (Claim 1). This ...
1answer
152 views

### Properly stating a decision problem for a Hamiltonian cycle problem

I'm running an algorithms seminar and I'm trying to express the Hamiltonian cycle problem in a new way that is exciting to students. I know that many of them play a game called Hearthstone and I'm ...
0answers
38 views