Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [np-complete]

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

0
votes
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 ...
4
votes
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, ...
0
votes
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 ...
0
votes
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, ...
0
votes
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 ...
1
vote
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 ...
3
votes
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 ...
1
vote
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", ...
1
vote
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, ...
0
votes
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 (...
1
vote
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.
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
2
votes
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 ...
6
votes
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" ...
2
votes
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 ...
0
votes
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 ...
1
vote
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. ...
0
votes
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$ ...
1
vote
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 ...
4
votes
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$. ...
0
votes
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 ...
0
votes
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 <= ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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$ ...
1
vote
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 ...
0
votes
1answer
38 views

Positioning items to maximize separation subject to constraints

Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
1
vote
0answers
82 views

Is the Maximum Clique Problem for Directed Acyclic Graphs NP complete as well?

Imagine I have a graph $(V,E)$ of vertices $V$ and undirected edges $E$. Then a clique is a set of vertices $(v_1,...,v_n)$ such that that there is an edge between any pair $(v_i,v_j)$ of vertices ...
5
votes
3answers
114 views

Why can't set cover be reduced to min-cost max-flow?

Okay, so I know obviously I'm making some kind of easy mistake here, since set cover is NP-complete and min-cost max-flow is in P, but I can't figure out what the mistake is. So, given a universe $U$ ...
0
votes
0answers
12 views

Karp hardness of a module in a graph

DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property: For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
1
vote
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, ...
0
votes
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} . ...
0
votes
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$ ...
0
votes
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 ...
1
vote
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?
0
votes
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!)$?
2
votes
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 ...
1
vote
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 ...
3
votes
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 ...
0
votes
0answers
38 views

Proof for correctness of reduction from 3-SAT to quadradic equations NPC problem

A reduction from 3-SAT to quadratic equations is described as follows: Given an input expression to 3-SAT, convert it to a quadratic example as follows: $x_i \rightarrow ax_i$ ~$x_i \rightarrow a(1-...
1
vote
1answer
119 views

Does this solve boolean satisfiability problem in polynomial time?

CNF can be easily converted into a formula that uses only AND and NOT operations, using the fact that ...
3
votes
0answers
44 views

Looking for name of combinatorial problem- Permute rows and columns to minimize distance to target matrix

I am trying to find a solution (or algorithm) for the following combinatorial problem: Given an input matrix and a target matrix, find a permutation of the rows and permutation of the columns that ...
0
votes
0answers
202 views

how to convert SAT to 3SAt

My teacher showed these steps when converting SAT to 3SAT (he was working with an example). He said to construct a formula F1 ...
0
votes
0answers
27 views

NP-hardness of finding the zero norm of a sparest null vector

The abstract of the paper The Null Space Problem I. Complexity states that finding a sparsest null vector of a matrix with more columns than rows is NP-hard (actually NP-complete). I wonder whether ...
0
votes
1answer
59 views

If a NP-complete problem is not in P, then all NP-complete problems are not in P?

It is clear to me that if a NP-Hard problem is solvable in P, then all NP-Hard problem (which include NP-Complete problems) are solvable in P. But, is it also the case that if a NP-Complete problem ...
0
votes
0answers
21 views

USAT, Arora Barak's book

Here on the page 354 Arora and Barak write below the shaded area "but in fact $f(\phi)$ $\notin SAT$" and not "but in fact $f(\phi) \in SAT$" While in the last line of the shaded area they write $...