# Questions tagged [np-complete]

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

161 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2k views

### Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
146 views

### Covering a complete graph with n copies of an arbitrary graph: NP-complete?

Given a complete graph $G$, an arbitrary graph $H$, and a positive integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that their union is $G$, and each of them ...
839 views

### Fastest known algorithm for $3$-$\mathrm{Partition}$ problem

$3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known ...
39 views

### Why the Cook-Levin reduction is not a parsimonious reduction?

In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is ...
260 views

### Reduce factoring to solving quadratic equations

The problem of solving quadratic equations is as follows: Suppose you are given a set of quadratic equations and are asked to find $0$-$1$ values for the variables such that all equations are ...
44 views

### Misunderstanding SS22 Sequencing to Minimize Tardy Tasks

I was reading "COMPUTERS AND INTRACTABILITY. A Guide to the Theory of NP-Completeness", and I am stuck at this part (page 236, SS22): In the second paragraph, 3rd line, the authors said that: "The ...
84 views

### Find a minimum-cost pair of arc-disjoint paths, both within a given restricted distance

Is there a polynomial algorithm that can find a pair of arc-disjoint paths in a directed graph that has a minimum total cost, subject to the condition that both paths are within the same distance. ...
552 views

### 2 Dimensional Subset Sum: looking for information

I do not know if this problems exists with a different name, if it is, I could not find it. The problem is this: Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ ...
27 views

### Strongly connected subgraph that contains no negative cycles

Is there an efficient algorithm that solves the following decision problem: Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected ...
59 views

### Partition into paths in a Directed Acyclic Graphs

I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths. When $b_i=1$ for all the ...
43 views

### Convex quadratic approximation to binary linear programming

Munapo (2016, American Journal of Operations Research, http://dx.doi.org/10.4236/ajor.2016.61001) purports to have a proof that binary linear programming [1] is solvable in polynomial time, and hence ...
134 views

### Is this equivalent to any famous NP-complete problem?

Given the following problem. Given an $n\times n$ matrix $A := \{a_{ij}\}$. Find an $n\times n$ matrix $X := \{x_{ij}\}$, where $x_{ij} \in \{-1, 1\}$ for $i, j \in [n]$, that minimizes the ...
77 views

### Matrix covering by squares

I wonder about the following decision problem : Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$. Question: is it possible to cover all the ones of the ...
115 views

### Is Hamiltonian cycle problem on graphs with out-degree at most 3 NP hard?

I am trying to show a different form of Hamiltonian cycle problem is NP Hard. The problem is as follows. We have a directed graph and each node can have at most 3 outgoing edges. Determine if this ...
78 views

### Need help figuring out a planning/assignment problem

I'm looking to solve this planning problem. Any pointers or ideas are much appreciated! You have a number of i individuals i = { 1, 2, ..., n } that need to perform tasks. Tasks are performed in ...
1k views

### $NP = PSPACE$ and what that would mean about $PH$

So, a paper showed up on arXiv: https://arxiv.org/abs/1609.09562 The above states in the abstract that it contains a proof that $NP = PSPACE$ Since $NP \subseteq PH \subseteq PSPACE$, that would ...
66 views

### PTAS vs. exact-time sub-exponential algorithms

I have recently summarized several algorithms for the maximum disjoint set problem. This problem is NP-hard, but it has both PTAS and sub-exponential algorithms. These algorithms seem to me closely ...
111 views

### Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT

Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a ...
47 views

### Partitioning bag of sets such that each set in a group has a unique element

Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
22 views

### Complexity of finding an alternating Hamiltonian (x,y)-path in edge bicolored complete graphs

Let $G$ be a simple complete graph with an edge-2-coloring. An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its ...
79 views

142 views

### How to minimize the sum of edge weight in the graph while keep the all-pair shortest path greater than a constant?

For example, if we have a graph G = (V, E) and a subset of vertices $U \subset V$. We can set $w(e)$ where $e \in E$ to be a non-negative real number. We want to minimize the total edge weight, but ...
145 views

I often read in Complexity literature that NPā©coNP is unlikely to have any complete problems. Is that unlikelihood "proved" ? By proved, I mean that there would be a theorem that would relate the ...
134 views

### String version of even-odd partition problem

Motivated by Hardness proof of EVEN-ODD PARTITION post I came up with a string version. String even-odd partition INPUT: $(x_{1,0},x_{1,1}),\dots,(x_{n,0},x_{n,1})$, i.e., $n$ pairs of strings over ...
149 views

### Showing a problem on a specific class of graphs is NP-hard

We know that a set of problems like minimum clique cover problem, coloring problem, vertex cover, ... are NP-hard for general graphs, but may be polynomial-time solvable for some classes of specific ...
70 views

### What is the time complexity of Summing Triples with duplicates?

Summing Triples problem is strongly $NP$-complete as shown by McDiarmid. Summing Triples problem: Input: list of 3N distinct positive integers Question: Is there a partition of the list into N ...
284 views

### Maximum Number of Edge Disjoint Paths of Length k in DAG

Is it known if the problem of finding the maximum number of edge disjoint paths of length k in a DAG is in P? Or has it shown to be NP-Complete? If so, are there approximation algorithms known for it? ...
211 views

### Is this modification of the subset-sum problem NP-complete?

Suppose we have input $s_1,\dots,s_n \in \mathbb Z$ and $t \in \mathbb Z$. We want to know if there exist variables $x_1,\dots,x_n$ in which each $x_i=1/2^k$, where $k \in \{0,1,2,3,4,\dots,\infty\}$, ...
86 views

### PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks

Consider the following problem: We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1$ and a profit $p_i > 0$. There are $m$ (a fixed number) of unit-...
21 views

### A polynomial time reduction and the size of problem (exact cover)

An exact cover problem is one of the NP-complete problems. Given a family $\mathbb{I}$ of subsets of a set $[n]=\{1,\dotsc,n\}$, whether there exists a subfamily $\mathbb{I}'\subseteq \mathbb{I}$ ...
22 views

### FPTAS algorithm to find flow at each link for multi commodity flow problem?

Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the ...
30 views

### Disjoint paths in digraphs is NP-complete

In the article: S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraphs homeomorphism problem, Theoret. Comput. Sci. 10 (1980) 111ā121. link: https://www.sciencedirect.com/science/article/pii/...
37 views

### NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

In a given undirected graph $G(V,E)$, a set of $k$ paths is said to be induced if: They are vertex-disjoint. Each one is itself an induced path. No edge connects two vertices of two different paths. ...
60 views

### How to prune branches in a branch-and-bound solution for Flow Shop Scheduling?

I am implementing a Branch-and-Bound algorithm to find the optimal solution for the Flowshop Scheduling Problem, but I am stuck on the optimization phase, here is a rundown of the problem and what I ...
27 views

### Karp hardness of two vertex sets in a digraph

Given a digraph $G(V,A)$ and a number $k$, we want to find two vertex subsets $S,T\subseteq V$ such that: $|S|+|T|=k$ For every $v\notin S\cup T$, $v$ has no arcs coming to $S$, and no arcs coming ...
22 views

### Is finding a sum of two squares representation for a number computationally assymptotically equivalent to integer factorization?

I have been wondering this question because given a number $n$ with prime factors of the form $4k+3$ when we square $n$ and find a sum of two squares which should reveal these types of factors (as ...
65 views

### Highest lower bound on an NP complete problem

What is the highest time complexity lower bound that has been proven on any (non-contrived) NP complete problem?
141 views

### Maximum number of non-overlapping rectangles where each contains a minimum number of points

Given n points and 0 < p < n, find the maximum number k of rectangles such that each rectangle contains at least p points and no two rectangles overlap. Each point is distinct from every other ...
185 views

### Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...
78 views

### Grouping elements optimally other than NP-hard approach

Given a number $N$, I need to make a new array $B$ of size $n$ (index-1 based) such that the product of $B[i]-(i-1)$ for $1 \le i \le n$ is equal to $N$ and $B[n]$ is minimum and $B[i] \ge B[i-1]$ and ...
136 views

### Invertability of Karp reductions

Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$. I am interested in polynomial-time ...
74 views

### Disconnecting graph (and subgraphs) by removing fewest amount of edges - NP completeness

I am trying to prove that a certain problem is $NP$-complete. The problem is that in a given order of elements like $(a>b>c)$, $(c>d>b>a)$, there will be inconsistencies. From these ...
51 views

### Given multiple families of sets, select a set from each such that the intersection of selected sets is a correspondence

Let $X = \{x_1, ... , x_k\}$ and $Y = \{y_1, ... , y_h\}$. A subset $S \subset X \times Y$ is a correspondence if : $\forall x, \exists y, (x,y) \in S$ and $\forall y, \exists x, (x,y) \in S$ That ...
86 views

### polynomial time reducibility, if $A \in \mathbf P$ and $B \in \mathbf N$ $\mathbf P \setminus \{\emptyset,\Sigma^*\}$ and vice versa

$f: \Sigma^* \to \Sigma^*$ is a polynomial time computable function if some poly-time Turing Machine M, on every input w, halts with just $f(w)$ on its tape. Language $A$ is polynomial time reducible ...
33 views

I am doing a project on task assignment with geographic constraints which naturally leads to the following question. Let $\mathbb{N}$ denote the set of integers. Given a finite subset $A \subset \... 0answers 99 views ### Complexity of Computing Volume of Convex Polytope Given a convex polytope$\{x\in \mathbb R^n | Ax\leq b\}$where$A$is a matrix, and$b$is a vector, and inequality between two vectors (like$Ax\leq b$) means inequality between their components ($\...
Can someone explain to me in the simplest possible way, how to reduce $3SAT$ to $Vertex\:Cover$? I am following the explanation here (scroll to the bottom of page 4). I understand the basic setup of ...
Given the following NP-complete problem: PARTITION Input: A list of positive integers $a_1, a_2, \dots, a_n$. Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such ...