Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
879 questions
1 vote
0 answers
28 views
Hardness of approximation for max-LINSAT mentioned in DQI paper
I went through Def 2.1 of this paper, where the approximation version of max-LINSAT is defined as follows. Let $\mathbb{F}_p$ be a finite field. Input: For each $i=1,\cdots,m$, let $F_i\subset \...
- 209
2 votes
1 answer
96 views
Proving NPhardness of linkedin queens
Consider the linkedin queens problem - our queens move like a rook + king on a nxn chessboard with coloured regions. The goal of the game is to place exactly queen in every row, column and coloured ...
- 21
1 vote
0 answers
71 views
NP-hardness proof densest 3-way partitioned weighted subgraph
I am investigating the complexity of the following problem: Let $G=(V,E,w)$ be a finite, simple, directed graph with a non-negative weight function $w:E\to\mathbb{R}_{\ge 0}$. A solution consists of ...
- 11
1 vote
1 answer
77 views
Simple Unbounded Multi-Knapsack with Distinct Items Constraint - strongly or weakly NP-c?
Is the following Knapsack problem strongly or weakly NP-hard? We have unbounded knapsacks, meaning we can use each item unlimited number of times. Given: $I = \{ w_1, ... w_n \}$ - a set of the ...
0 votes
0 answers
77 views
Hardness of approximation for complexity class $\mathsf{MA}$
Under the derandomization assumption $\mathsf{MA=NP}$, one can obtain the hardness of approximation result for the class $\mathsf{MA}$. (Note: By invoking the PCP theorem.) Has there been another way/...
- 209
2 votes
1 answer
111 views
NP-Completeness of the Rectangle Packing Puzzles
I'm reading the proof of the (strongly) NP-completeness of the Rectangle Packing Puzzles by Erik D. Demaine, Martin L. Demaine (source: https://erikdemaine.org/papers/Jigsaw_GC/paper.pdf). ...
0 votes
0 answers
76 views
Graham's Greedy Algorithm is optimal for (2m) machines
I am reading up on Graham's algorithm and want to prove it's $4/3 - 1/(3m)$ optimality. To do that, we need to prove that if $j$ is the last job assigned to the most heavily loaded machine in the ...
- 71
2 votes
1 answer
168 views
FPT solution for Digraph Pair Cut
Consider following problem: Given a direct graph $G$, some vertex $s\in V (G)$, a family of pairs of vertices $F$, and an integer $k$; the goal is to find a set $X$ of at most $k$ edges of $G$, such ...
14 votes
2 answers
815 views
Is this graph problem NP-hard?
Given a bipartite graph G with bipartition $G = A \cup B$, and weights $w(v)$ for nodes of G such that $w(v)>0$ for $v \in A$ and $w(v)<0$ for $v \in B$. Let $V(G) = \{ v_1,v_2,..,v_n \}$. Call ...
- 155
1 vote
1 answer
80 views
What is the point of proof of correctness of NP-completeness?
In most the problems I am tasked to prove that a problem A is NP-complete. I show that B is in NP, then I reduce NP-hard problem A to B. Then I am required to prove that a yes instance in B is a yes ...
- 31
2 votes
0 answers
49 views
Special case of rank minimization
The problem takes as input an $m \times 2n$ matrix $A$ over $\mathbb{F}_2$. Optimization version: find a subset of exactly $n$ columns so that the corresponding submatrix (taking only selected columns)...
1 vote
1 answer
132 views
Is it NP-hard to decide whether a graph is balanced bipartite?
The problem is the following. On input, an undirected graph $G = (V, E)$. Question: can $V$ be partitioned into two (disjoint) subsets $V = V_1 \cup V_2$, with $-1 \leq |V_1| - |V_2| \leq 1$ so that ...
1 vote
1 answer
139 views
Algorithm for The Ticket to Ride Problem
The Problem Given a connected graph $G=(V,E)$, edge weights $w:E\rightarrow\mathbb{N}$, and a set of vertex pairs $T=\{\{t_{1a},t_{1b}\},\{t_{2a},t_{2b}\},...,\{t_{ka},t_{kb}\}\}|t_{ij}\in V$, find a ...
- 123
1 vote
1 answer
316 views
How do you show Dominating Set is NP Complete
A dominating set of an undirected graph $G = (V,E)$ is a subset of vertices $C\subseteq V$ such that every vertex $v\in V$ either belongs to $C$ or has a neighbor in $C$. The corresponding decision ...
2 votes
1 answer
200 views
NP-Hardness: Finding the Best Subtree for Hierarchical Matching in Elasticsearch
Given a graph G = (V, E) (a forest) stored in Elasticsearch and a set of requests R, where each request r in R can potentially match between 0 and V vertices in G, the task is to identify the "...
- 21