As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [np-hard]

decision problems that are at least as hard as NP-complete problems

Filter by
Sorted by
Tagged with
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 ...
matheg's user avatar
  • 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, ...
pcko1's user avatar
  • 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, ...
Alex-Github-Programmer's user avatar
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 ...
D. Sena's user avatar
  • 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 ...
licheng's user avatar
  • 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 ...
TheCollegeStudent's user avatar
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 ...
a.t.'s user avatar
  • 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 ...
Vladislav Bezhentsev's user avatar
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. \...
OvinaSun's user avatar
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 ...
Pathlessbark8's user avatar
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 \...
Doc Stories's user avatar
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 + ... + ...
automatically's user avatar
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,...
staz6's user avatar
  • 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 ...
Benedict Bien's user avatar
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 ...
Andrew Baker's user avatar
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 ...
abby richardson's user avatar
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} ...
SARTHAK GUPTA's user avatar
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 ...
Soroush Vahidi's user avatar
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 ...
Jonas Juul Hansen's user avatar
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 $...
joachimkristensen's user avatar
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 ...
Emma3201's user avatar
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 ...
Balchandar Reddy's user avatar
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$ ...
Isak He's user avatar
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 ...
Kenny Sanders's user avatar
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 ...
Balchandar Reddy's user avatar
-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 ...
Darcy Sutton's user avatar
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 ...
Agnishom Chattopadhyay's user avatar
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 ...
Geo's user avatar
  • 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 ...
Geo's user avatar
  • 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)...
NL1992's user avatar
  • 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 ...
Soroush Vahidi's user avatar
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 ...
Soroush Vahidi's user avatar
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 ...
Thomas Tappeiner's user avatar
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-...
Balchandar Reddy's user avatar
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 ...
Balchandar Reddy's user avatar
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 ...
Rohit Pandey's user avatar
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),\...
Felix's user avatar
  • 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 ...
AnnaMark's user avatar
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 = ...
Blanco's user avatar
  • 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 ...
nuemlouno's user avatar
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 ...
al5719's user avatar
  • 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 ...
Hjm's user avatar
  • 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 ...
Anonymous Molecule's user avatar
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 ...
77H3jjuu's user avatar
  • 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 ...
Ludwig's user avatar
  • 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 ...
Anonymous Molecule's user avatar
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 ...
kim120's user avatar
  • 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 ...
Aishgadol's user avatar
  • 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 ...
Tyler's user avatar
  • 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 ...
al5719's user avatar
  • 3

1
2 3 4 5
17