Questions tagged [np-hard]
decision problems that are at least as hard as NP-complete problems
880 questions
2
votes
1
answer
80
views
Is Exact Matching with more than two colours in RP or NP-hard?
I'm interested in the following problem: given a (multi-)graph with each edge coloured by one of 3 colours, find a perfect matching with exactly k_i edges of colour i in {1,2,3}. I'm also interested ...
- 849
1
vote
0
answers
33
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
99
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
82
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
112
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
78
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
818
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
145
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
324
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 ...
