Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
0 votes
0 answers
32 views

Bipartite Matching with a Partition Constraint over the Vertices

Let $G = (X,Y,E)$ be a bipartite graph and let $X_1,\ldots,X_r$ be a partition of $X$. For some $i \in \{1,\ldots, r\}$ and $E' \subseteq E$ we say that constraint $X_i$ is covered by some $E'$ if ...
John's user avatar
  • 392
0 votes
1 answer
79 views

Polynomial time algorihtms for two variants of the decision version of longest walk problem

I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm. As I understand it, the longest path problem doesn't allow repetition of edges....
user1868607's user avatar
  • 1,017
1 vote
1 answer
60 views

Shorter than target vector path algorithm

Consider a generalisation of the shortest path problem on directed graphs with weights in $\mathbb{Q}^k$. Formally, the input is a graph, a source state $s$, a target state $t$, and an objective ...
user1868607's user avatar
  • 1,017
0 votes
2 answers
84 views

strong NP-completeness of multi-dimensional Equal-Subset-Sum

I want to show that the multi-dimensional Equal-Subset-Sum is NP-complete in the strong sense: Given a set of $d$-dimensional vectors of non-negative integers, does there exist two distinct nonempty ...
caduk's user avatar
  • 101
0 votes
0 answers
44 views

Unbounded Knapsack: Does Increasing capacity increase optimal value?

Our decision problem is as follows: given weights $\mathbf{w}$, values $\mathbf{v}$, and capacities $C_1$ and $C_2$, where $C_1 < C_2$, does the optimal value of unbounded knapsack with the above ...
happyfeet's user avatar
12 votes
2 answers
690 views

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Do we know any problem that satisfies the following criteria? It is polynomial-time solvable on trees. It is NP-complete when restricted to graphs of treewidth 2. The problem can be encoded only ...
Prafullkumar Tale's user avatar
0 votes
2 answers
212 views

Shortest path with permutations and fixed dimension

I'm thinking of extensions of the shortest path problem which are solvable in polynomial time. One way to do this is to consider the shortest path problem on a weighted directed graph with weights on $...
user1868607's user avatar
  • 1,017
5 votes
1 answer
132 views

Shortest path with affine updates and fixed dimension

One may look at the shortest path problem on a weighted directed graph with weights on $\mathbb{Q}$ as the problem of minimizing a rational value $x$ which is updated at each edge of the graph with ...
user1868607's user avatar
  • 1,017
4 votes
3 answers
287 views

A Travelling Salesman variant where the next distance depends on distance travelled so far

The travelling salesman problem can be seen as a problem of selecting a permutation on $\{1,\ldots,n\}$ of minimun length, where the length of a permutation $\sigma$ is determined by pairwise ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
80 views

On The Complexity of Block-Interchange Distance for Binary Strings

The block-interchange distance problem is defined as finding the minimal number of subsequences swaps to apply to an input string to turn it into a desired string. It is a well studied tractable ...
Daniel García's user avatar
7 votes
1 answer
326 views

Is sorting NP-complete?

SORTING problem. Input: A poset which corresponds to a partially sorted list of different numbers. Output: Number of pairwise comparisons needed (in the worst case) to get a completely sorted array. ...
domotorp's user avatar
  • 14.1k
4 votes
1 answer
209 views

Is Optimal Swap Sorting NP-Hard?

Given an array of integers with duplicates, find the minimum number of swaps to sort the array. According to this question, the problem is NP-Complete but the reference given proves NP-Completeness ...
Daniel García's user avatar
0 votes
0 answers
28 views

Compute a feasible schedule for scheduling on identical parallel machines?

I am considering the offline version of identical parallel machine scheduling with arrival time and deadlines while allowing preemption and no assumption regarding the agreeability of the arrival and ...
Walid Hanafy's user avatar
2 votes
0 answers
88 views

Complexity of finding a room-partitioning

In a paper by Jack Edmonds and Laura Sanità (link: https://www.sciencedirect.com/science/article/pii/S1571065310001605) the following intriguing result is given: Given a triangulation $T$ of $3n$ ...
László Kozma's user avatar
2 votes
1 answer
76 views

Set Cover with Multiple covers

I am interested in whether a set cover instance that covers all elements $q$ times may have the property that every sufficiently small subset of this set cover will not cover the elements even once. ...
John's user avatar
  • 392
10 votes
0 answers
147 views

Is this problem on unambiguous DNFs hard?

Call a DNF formula $\varphi = \bigvee_{i=1}^n C_i$ unambiguous if for every $i\neq j$, $C_i \land C_j$ is unsatisfiable. In other words, the disjunct $C_i$ contains some literal $l$ and $C_j$ contains ...
M.Monet's user avatar
  • 1,429
3 votes
0 answers
99 views

maximum independent set in graphs with small number of edges

For the classic maximum independent set problem, a hardness of approximation result of $n^{1-\varepsilon}$ is known by [Hastad, 1996] assuming $\textsf{NP} \not \subseteq \textsf{ZPP}$, where $n$ is ...
John's user avatar
  • 392
3 votes
0 answers
89 views

What's the complexity of the "decision version" of counting the paths in a graph?

I learned that "counting the simple paths in a graph(whether directed or not)" is #P-Complete. I'm wondering what the complexity is for its decision version. Here are two types I'm ...
Wenhao Wu's user avatar
0 votes
0 answers
92 views

Complexity of Identifying SAT Problems with a Unique Solution from Satisfiable Instances

I am curious about the computational complexity involved in identifying SAT problems that have only one solution from a set of satisfiable SAT instances. input and output: input: A satisfiable cnf ...
Jxb's user avatar
  • 316
1 vote
0 answers
70 views

Hardness for find the clause for statisfiable 3-SAT problems

The 3-SAT problems are known to be NP-complete so the decision problems are believed to be non efficiently solvable unless P=NP. Yet, there are cases where the satisfiability can be answered such as ...
ironmanaudi's user avatar
3 votes
1 answer
187 views

What’s the complexity of this decision problem with bit shifting?

I’ve been wondering about the computational complexity of a problem that involves bit shifting. Let me define some notation before I present the problem. If $\langle{b}\rangle$ is a bitstring ...
Sophie Weigle's user avatar
2 votes
0 answers
26 views

Hardness of 3-Partition with Small Target Value

In the 3-partition problem, we are given a set of positive integers $a_1,\ldots,a_n$ and a target value $T$; the goal is to decide if there is a partition of the numbers to triplets such that the sum ...
John's user avatar
  • 392
0 votes
0 answers
70 views

The hardness of active learning with fixed budget

I have been looking for theoretical papers studying this question of the hardness of PAC active learning algorithms. I found a few papers studying the problem from a fixed perspective (particular ...
rivana's user avatar
  • 65
2 votes
0 answers
48 views

Is this variant of Facilities location problem a NP-hard problem?

Given a set of locations $P=\{p_1,p_2,\dots\}$ and a set of facilities $F=\{f_1,f_2,\dots\},|F|\ge k$ on a plane. We want to partition the facilities into $k$ disjoint subsets (each subset has at ...
Jingle's user avatar
  • 21
6 votes
0 answers
95 views

Certifying the promise in hard promise problems

Do we happen to know of any promise problems where the problem is both conditionally hard (say, NP-hard) while simultaneously being able to certify that the instance satisfies the given promise? For ...
Noel Arteche's user avatar
0 votes
0 answers
132 views

Could we build PSPACE-based cryptography - more secure post-quantum?

It seems not safe to exclude possibility of e.g. some next generation quantum computers being able to attack NP problems (e.g. 2WQC) - so maybe it is worth to start thinking of shifting the ...
Jarek Duda's user avatar
1 vote
0 answers
90 views

Generalization of the Hamiltonian path problem on Grid Graphs

Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function $f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$. Define the following ...
TRP's user avatar
  • 31
0 votes
1 answer
68 views

Is this edge-partitioning NP-Hard?

Let $G = (V,E)$ be an undirected graph with $m = |E|$ edges (assume that $m = 3t$ for some $t \in \mathbb{N}$). Problem: Partition $E$ to $q = \frac{m}{3}$ sets $S_1,S_2,\ldots, S_q \subseteq E$ sets ...
John's user avatar
  • 392
3 votes
0 answers
186 views

Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?

It is well-known that $\mathsf{P}\neq\mathsf{SPACE}(n)$, either for $\mathsf{SPACE}=\mathsf{DSPACE}$ or $\mathsf{NSPACE}$, and it is conjectured that both $\mathsf{P}\not\subseteq\mathsf{DSPACE}(n)$ ...
plm's user avatar
  • 131
13 votes
1 answer
269 views

Complexity of 1-or-3-in-3-SAT (odd-3-SAT)

Consider a 3-CNF formula $\Phi$, i.e., a conjunction of clauses of 3 literals. I call odd-SAT (or 1-or-3-in-3-SAT) the problem of checking whether there is an assignment of the variables such that ...
a3nm's user avatar
  • 9,269
0 votes
0 answers
34 views

Hardness of finding minimal subsets that will change the maximum of a univariate polynomial

Given a univariate polynomial of the form $p(x) = \prod_{0 \leq i \leq N}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$ (we are given all ...
Amit Bergman's user avatar
1 vote
0 answers
78 views

Hardness of maximization of a univariate polynomial (as a function of its degree)

Given a univariate polynomial of the form $p(x) = \prod_{i}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$. What is the complexity of ...
Amit Bergman's user avatar
0 votes
0 answers
67 views

Enumerating all set covers with sets of size at most two

I am working on enumerating all the set covers (need not be minimal). A branching algorithm runs in $O^*(1.2353^{|U|+|S|})$ time that branches on all the sets of size at least three. As the branching ...
Balchandar Reddy's user avatar
0 votes
0 answers
76 views

Prove that Vertex Cover is NP-Complete by reducing MaxCut to Vertex Cover

This is not the most straight forward reduction available on the internet since most people start from the fact that vertex cover is NP-complete and reduce a given vertex cover instance to MaxCut ...
Chaithanya's user avatar
1 vote
0 answers
97 views

Complexity of n-rooks completion

I am motivated by the post, Complexity of n-queens-completion. I am interested in completion problem of non-attacking rooks on a chessboard. Input: Given a chessboard of size $n*n$ with $n-k$ rooks ...
Mohammad Al-Turkistany's user avatar
5 votes
0 answers
153 views

Complexity of numerical 3-dimensional matching where the three multisets are identical

Consider the following problem: Input: one multiset $S = \{s_1, \ldots, s_n\}$ of positive integers written in unary Output: can we build $n$ triples that sum to the same value, using each element of ...
a3nm's user avatar
  • 9,269
2 votes
1 answer
145 views

clique problem in graphs with bounded degree

Is the problem of finding a clique of size $d$ in a graph of maximum degree $d$ NP-complete ($d$ part of the input)?
Michael Poss's user avatar
3 votes
1 answer
192 views

Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?

I noticed a lot of 1-player games have been shown to be NP-Hard, like Pac-Man, The World's Hardest Game, Tetris, etc. For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games: It is ...
edit's user avatar
  • 33
0 votes
1 answer
199 views

Complexity of solving a higher-order degree polynomial equation? P-problem or NP-problem or neither?

I am a mathematician and I am very new to theoretical computer science. The definition of P/NP problem I found in wiki is that: P is the set of decision problems solvable in polynomial time by a ...
tadokoro sinitiro's user avatar
9 votes
1 answer
301 views

Complexity of permanent verification

Consider the problem of permanent verification: $\bullet \ $ Given a $n\times n$ matrix $A$ with entries in $\{0,1\}$, and given $k\ge 0$, does $Per(A)=k$? Question: Is it known to be NP-hard? Should ...
Igor Pak's user avatar
  • 812
1 vote
2 answers
101 views

Is Maximum Independent Set polynomial-time solvable in $(p,1)$-colorable graphs for general $p$?

It is well-known that Maximum Independent Set (MIS) in bipartite graphs is polynomial-time solvable. What happens if we generalize the input graphs by replacing the vertices in one partite with ...
Blanco's user avatar
  • 421
0 votes
0 answers
70 views

Is this Knapsack/Subset Sum Variant NP-Hard?

The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be ...
John's user avatar
  • 392
-2 votes
1 answer
247 views

What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?

There is an ever going trend to believe that a large number of NP-Complete or NP-Hard problems can be solved using quantum heuristics. I have observed, a common trend, to take any sort of ...
Marion's user avatar
  • 183
0 votes
0 answers
90 views

When Exponential Costs are Essential for NP-Hardness?

In many NP-hard problem there is a budget constraint. Each element $e$ in the instance has a certain cost $c(e)$ and a profit $p(e)$; a feasible solution $S$ for the considered problem cannot exceed ...
John's user avatar
  • 392
4 votes
0 answers
285 views

Permutation generation problem using swaps

This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input. We're given as input ...
Mohammad Al-Turkistany's user avatar
1 vote
1 answer
183 views

3 Matroid Intersection, a Special Case

It is well known that finding a maximum cardinality (or weight) common independent set in the intersection of 3 matroids is APX-Hard. Question: Does this problem remain NP-Hard if one of the matroids ...
John's user avatar
  • 392
2 votes
1 answer
62 views

Balls in monochromatic bins

Suppose we have a collection of $m$ balls in $k$ different colors. Let $b_i$ be the number of balls with color $i$, so $\sum_{i=1}^k b_i = m$. Assume we have $n$ bins with capacities $c_1, \dots, c_n$,...
AAArAAA's user avatar
  • 23
6 votes
0 answers
102 views

Cycle packing with degree condition

Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard? Without the degree condition, the ...
TZM's user avatar
  • 133
11 votes
1 answer
454 views

Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?

Consider the following decision problem over a fixed alphabet $\Sigma$: Input: strings $s_1, \ldots, s_n$ of $\Sigma^*$ and a target string $t \in \Sigma^*$ Output: does there exist a permutation $\...
a3nm's user avatar
  • 9,269
0 votes
1 answer
71 views

Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover

As stated in the question, I'm interested in a variant of Exact Cover that is currently relevant to my research. Specifically, a variant where you are promised that if there is a Set Cover of size $k$,...
Matthew Ferland's user avatar

1
2 3 4 5
15