Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
801
questions
0
votes
1
answer
71
views
Budgeted Independent Vertex Cover
Suppose that we are given a graph $G = (V,E)$ and a number $n$. The problem is to find an independent set $I$ with $|I| = n$, such that number of vertices covered by $I$ is maximized (that is, the ...
- 111
1
vote
1
answer
229
views
NP-completeness of problem based on non-arbitrary instance
To prove that a problem is NP-complete, one has to show that it is both (a) in NP and that it is (b) NP-hard by reducing a known NP-complete problem to it in polynomial time.
Regarding the reduction, ...
- 113
2
votes
0
answers
26
views
Is it NP-hard to determine if the player can win in this 'spread-cut' game on graph?
There is a graph with two special nodes, s and t. In the beginning, only s is marked. The only player's task is to keep t from being marked.
In each turn, the player can choose an edge to cut. Then, ...
2
votes
1
answer
56
views
Selecting a submatrix of a binary matrix NP hard?
I have the following problem and I am wondering if it is NP Hard or not.
Let $A$ be a binary matrix whose rows and columns are indexed by the sets $\mathcal{I}=1,...,m$ and $\mathcal{J}=1,...,n$.
A ...
- 23
1
vote
1
answer
41
views
How can we find a shortest closed walk passing through all vertices?
How can we find a walk with the minimal length starting from a vertex $v$, passing through all vertices and returning back to $v$?
We allow vertices and edges to be repeated along the walk. The ...
- 165
0
votes
0
answers
31
views
Hardness of the bin packing problem
I have been reading up on the bin packing problem. In the bin packing problem, we are given $n$ items with sizes $a_1,a_2,\dots, a_n$ such that
$$
1 > a_1 \geq a_2 \geq \dots \geq a_n > 0
$$
The ...
0
votes
0
answers
18
views
Solving a weighted minimum dominating set problem with its unweighted counterpart?
Question
Is it possible to find a solution to the weighted minimum dominating set problem, by solving a (related), unweighted minimum dominating set?
Elaboration
In essence, can one convert a ...
- 123
2
votes
2
answers
596
views
Is it NP-hard to decide the existence of n subsets picked from n lists of subsets the union of which contains at most s elements?
You are given $n$ lists. The $i$-th list contains $k_i$ subsets of $\{1, \ldots, m\}$. You are also given an integer $s$. You should decide whether it's possible to pick up exactly one element (that ...
2
votes
1
answer
76
views
Is the following binary quadratic integer programming NP-Hard？
I'am trying to prove the following binary quadratic integer programming problem NP hard.
$$
\min \frac{\sum\limits_{i=1}^m(u_i-\bar u)^2}{m}\text{ , where }u=Q x,Q\in\mathbb{R}^{m\times n}\\
s.t. \...
- 23
0
votes
0
answers
54
views
Finding a Polynomial Time algorithm for the 3-SAT Problem
Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause :
Ai = (xr $\lor$ xs $\lor$ xt)
where 1 $\le$ r,s,t $\le$n and ...
0
votes
0
answers
25
views
Envy-Free Allocation is NP-Hard
If we consider the class fair division problem where we have a set of $n$-agents and a set $M$ of $m$-items, where each agent has a valuation function defined on the set of items $$v_i : 2^m \...
- 31
0
votes
1
answer
72
views
Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier
For this question I figure we need to define a system of linear inequalities which I thought could be something like this : a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X
a1x1 + a2x2 + ... + ...
0
votes
1
answer
78
views
System of equalities and inequalities is NP-hard using a reduction from 3COLORING
We are require to show that a problem where the input is a system of equalities and inequalities, each involving polynomials of degree at most 2 (with integer coefficients) in n real variables x1, x2,...
- 25
0
votes
1
answer
26
views
Can you transform 3sat (or equivalent) into another satisfiability problem that increases the ratio of solutions to non-solutions
Say I have f(x1,x2,x3,...) where the output is either 0 for all inputs (unsatisfiable) or a variable boolean output of 0 or 1 depending on the input (satisfiable). Let's not consider functions that ...
4
votes
2
answers
93
views
Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)
Given two problems, $A$ and $B$, that are NP-hard. Is either one of the following is true?
$A \leq_m$ B
$B \leq_m$ A
In other words, is there always a relationship between any two arbitrary NP-hard ...
- 245
1
vote
1
answer
31
views
Disjoint Subset Sum Reduction (NP-Complete)
I am using past materials to review for an upcoming assignment and came across this question:
Disjoint Subset Sum:
Input: A set of integers S and a goal g(in the set of natural numbers)
Output: YES if ...
0
votes
1
answer
37
views
Prove that the problem MATCH is NP-complete
The problem MATCHED is defined as follows: given an infinite set S of strings of arbitrary length over the alphabet {0, 1}, determine if there exists a character of length n over the alphabet {0, 1} ...
0
votes
0
answers
85
views
Does there exist an FPTAS for bin packing problem?
We know that there does not exist an FPTAS for the bin packing problem because it is a strongly NP-HARD problem, as the 3-partitioning problem which is strongly np-hard, can be reduced to the bin ...
2
votes
1
answer
28
views
Partition a family of sets to maximize cumulative overlap and cardinality
My problem is this: I have a list of $n$ items $N$ (think of them as the natural numbers $1,\dots,n$) and $m$ subsets of $N$ $S_1,\dots,S_m$ which may overlap. The objective is to find a partition of ...
0
votes
1
answer
76
views
Possible reduction from SUBSET-SUM
Given is a multiset $S$, a finite set $T = \{t_1, t_2, t_3\}$, and an integer $k \in \mathbb{N}$.
Let $v(t_j)$ be a set of values $\in \mathbb{R^+}$ of length $|T|$ that can be assigned to $s_i$, and $...
1
vote
1
answer
90
views
3-Dimensional Matching $\leq$ $_{p}$ subset sum Explanation
excuse me, could someone explain to me the reduction of the problem 3-dimensional matching to subset sum? I was reading Jon Kleinberg's design algorithms book and when I came across this reduction I ...
- 11
1
vote
1
answer
41
views
No parameterised reduction for a problem indicates FPT or not?
I am currently working on parameterized complexity, especially on the hard proofs. There is a problem that I am currently working on, denoted by $P$ and a parameter $x$, I discovered that there is no ...
0
votes
2
answers
76
views
How to show a language is in NP?
(I reorganized my question.)
We have a function $f$ mapping the integers $\{1, . . . , 2^k\}$ ONTO the integers $\{1, . . . , 2^k \}$ such that when these integers are represented in binary, and $f$ ...
- 3
0
votes
2
answers
86
views
Why is there no polynomial time verifier for N Queens
The N-Queens in question is referring to the one where it is interested in finding all solutions for some natural number n. I just read about the idea of a verifier being an algorithm that verifies ...
0
votes
0
answers
21
views
Finding the shortest 3-regular subgraph in a 6-regular graph
I am a research scholar currently working in computational complexity. As part of my research work, I need to understand the existence of various types of subgraphs in regular graphs. In particular, I ...
-1
votes
2
answers
49
views
Is One Way TSP NP-Complete?
I know that finding the optimal solution to One Way TSP (TSP but the salesman does not have to return to his original city) is NP-Hard, but is it NP-Complete? I ask this because I recently found a ...
1
vote
0
answers
24
views
Suggestion for tools/libraries for multi-output boolean circuit minimization?
I am interested in the following problem
Input: A boolean function F with n boolean inputs and m boolean outputs.
Output: A circuit C implementing F such that C has as few gates as possible.
The ...
0
votes
0
answers
23
views
Is $L(M_{A_{TM}⤭})$ NP-Hard?
Let $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$, clearly it is NP-Hard.
Let $M_{A_{TM}}$ be the DTM that recognizes $A_{TM}$.
Define $M_⤭$ to be the TM obtained from $M$ by swapping the accept ...
- 37
0
votes
1
answer
33
views
Is $\overline{A_{TM}}$ co-NP Hard?
I know that $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$ is NP-Hard:
By showing a polynomial time reduction - $A \le_p A_{TM}$:
Let $A \in NP$, then there exists a $NTM$ that decides $A$ in ...
- 37
0
votes
1
answer
28
views
Polynomially many instances imply a polynomial reduction?
I have a language $L$ which is NP-hard and I have another language $L_1$, s.t. if I take an instance $q$ of the decision problem corresponding to $L$, and if one of polynomially many instances, $f_1(q)...
- 103
0
votes
0
answers
33
views
Is this minimizing problem NP-hard?
We have $c$ arrays of positive integers, named $j[1],j[2],j[3]..,j[c]$. We know that the length of $j[i]$ is $c-i+1$. In addition, the sum of the numbers of $j[i]$ is greater than or equal to the sum ...
0
votes
1
answer
124
views
Is this sorting problem NP-complete?
Consider array $A=(a_1,a_2,...,a_n)$ such that $a_i$s are positive integers. Moreover, we have $k$ binary tuples, each with length $n$. In each iteration, we choose one of those tuples, and decrease ...
2
votes
0
answers
33
views
Problems with proof of NP-completness of SAT following Cooks original paper
I am currently in the process of trying to understand the original proof of NP-completeness of SAT given in the seminal paper by Cook [COOK71] and have struggled with a few of the details of the proof ...
- 121
1
vote
1
answer
43
views
Constant value NP-complete vs W[1]-hard
I am a research scholar currently working in parameterized algorithms. I am studying the complexity of a problem (say $P$) for $\Delta_{10}$ graphs and was able to provide a reduction from a known NP-...
0
votes
1
answer
41
views
Computing distance to clique in FPT time
I am a research scholar, and I currently work in parameterized algorithms. My current work involves proving that a problem is FPT for the parameter distance to clique. Although it is known that ...
0
votes
0
answers
85
views
Has this problem related to bin-packing and knapsack been studied?
There is a problem I recently encountered in my work which is related to the knapsack and bin packing problems. But I couldn't find the exact problem anywhere.
Say you have some suitcases. Each of ...
- 295
1
vote
1
answer
29
views
Reduction from $2$-Partitioning to (simple) pairwise $2$-Partitioning
I'm currently stuck showing $NP$-hardness of a problem of mine.
An instance of my problem (I call it (simple) pairwise $2$-Partitioning) is given by the following:
Given a set of tupels $B=\{(b_1,1),\...
- 161
-1
votes
1
answer
42
views
Prove the NP-hardness of problem
Prove the $NP$-hardness of $CONNECTEDNESS$ - the problem of counting over an oriented graph $G$ and two vertices
$s$ and $t$ the number of subgraphs of $G$ in which from $s$ to $t$ can be traversed by ...
- 1
2
votes
1
answer
60
views
Is this varient of longest increasing nested sets problem NP-hard？
There are two types of sets $\mathcal{X} = \{X_{1}, X_{2}, \ldots, X_{n_{1}} \}$ and $\mathcal{Y} = \{Y_{1}, Y_{2}, \ldots, Y_{n_{2}}\}$ such that $X_i, Y_j \subseteq [m]=[\mathrm{poly}(n)]$ and $n = ...
- 613
0
votes
2
answers
47
views
Searching for the largest bipartite subgraph
OpenAI's Chat-GPT told me:
There is no known exact algorithm for finding the largest bipartite subgraph in a graph in polynomial time. This problem is generally believed to be NP-hard, which means ...
- 59
0
votes
0
answers
118
views
Reduction from LONGEST PATH to HAMILTONIAN PATH
LONGEST PATH is the decision problem asking if a simple path of at least $K$ edges exists in a graph $G$.
The reduction from ...
- 3
0
votes
1
answer
99
views
4DM is NP-complete
Is 4DM NP-complete?
An instance of 4DM consists of four disjoint sets X, Y, W and Z of size k, and a set Q of quadruples $Q = \{ (x, y, w, z) \mid x ∈ X, y ∈ Y, w ∈ W, z ∈ Z \}$
Question: Is there a ...
- 37
-3
votes
1
answer
66
views
How to prove that this is NP complete
I have the following problem: Given an undirected graph with n vertices v1,…,vn, a positive integer weight on each edge, and a n×n symmetric matrix Rij. The objective is to find a subset S of the ...
1
vote
1
answer
126
views
Sorting a collection of tuples using merge rearrangements
Given a collection of tuples $X=\{(x_1,y_1),\dots,(x_n,y_n)\}$, where elements
$x_i, y_i \in R_{\geq 0}$ are non-negative real values. The collection $X$ is
sorted if $x_i \leq x_{i+1}$ and $y_i \leq ...
- 123
1
vote
1
answer
32
views
Reducing problems to solve easier problems
Is there any instance where a problem $A$ can be reduced to a problem $B$ where $B$ is easier to solve than $A$?
I've been learning about NP-Hardness recently and seems that the answer is no. Whenever ...
- 13
0
votes
1
answer
65
views
How to prove that this problem is NP Complete
I have a problem set about NP Completeness proofs and I'm struggling to approach this problem:
An organizer would like to arrange all the participants in a
circle where neighboring two students must ...
1
vote
1
answer
163
views
Show problem is NP-hard
I'm preparing for my exam and I got stuck on the following problem:
The gardening problem:
We have access to a set of different types of seeds and a number of plant pots.For each plant pot, there is ...
- 21
1
vote
1
answer
106
views
Single machine scheduling with profit and deadline constraints
The problem is described as such:
Given $n$ tasks $\{J_1, \ldots , J_n\}$where each task has a deadline and a ‘profit’.
So for some $i \in \{1,\ldots , n\}$, $J_i=\{t_i,p_i\}$ where $t_i$ is the ...
- 316
1
vote
1
answer
28
views
In NP-hardness, can any category reduce to itself? How can you intuitively explain which categories reduce to the others?
I'm trying to understand how problems in NP-hardness reduce to one another. As I understand it now, if X reduces to Y, Y is at least as hard as X.
What I think that means, and would like confirmed or ...
- 11
0
votes
2
answers
76
views
Reduction from SUBSET SUM to COIN CHANGING
The COIN-CHANGING problem is NP-complete, but I am having difficulty finding a proof for its NP-hardness in the form of a reduction from another NP-complete problem ...
- 3