Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

6
votes
1answer
364 views

NP-hardness of minimum distance over a code

There happens to be this NP-complete question, Minimum-Distance-Over-$\mathbb{F}_{2^m}$ Given $w \in \mathbb{Z}^+$ and a $r \times n$ matrix $H$ over $\mathbb{F}_{2^m}$, is there a $x \in \mathbb{F}...
-4
votes
1answer
358 views

Proving NP-hardness of scheduling problem (total weighted completion time)

Consider the problem $P \mid \mid \sum w_j C_j$. I want to prove that this problem is (strongly) NP-hard by reducing from $3$-Partition, but I am not really sure how to do this. Just to be precise, ...
11
votes
2answers
1k views

To which complexity class does this language belong?

I was thinking about which class this language belongs: $L =\{ \langle G,k \rangle \mid G $ is a graph, $k$ is a natural number and $k$ is the chromatic number of $G\}$ I thought of $L$ as (1) " ...
0
votes
0answers
381 views

Hardness of Minimizing Submodular Functions with Cardinality Constraints

I am new to submodular functions and I am reading the introductions to submodular functions and applications ( https://www.ima.umn.edu/optimization/seminar/queyranne.pdf ). In this introduction, it ...
2
votes
2answers
785 views

$k$-clique in $k$-partite graph

Is the decision whether a $k$-clique exists in a $k$-partite graph NP-hard? I have found only a very limited number of references on this problem, and they seem to be concerned with heuristics to ...
4
votes
1answer
167 views

Generalized geography on solid grid graphs

A post here For which families of graphs is Generalized Geography in $P$? mentioned that generalized geography on solid grid graphs is open. Is the question still open? A quick search on Google shows ...
0
votes
1answer
264 views

NP-complete problems with optimal approximation in poly-time

I'm looking for examples of hard optimization problems, for which we have an optimal approximation (not that this is not the same as $PTAS$, as we require a completely tight approximation, and not $1+\...
3
votes
1answer
726 views

The complexity of a multi-objective shortest path problem

I have the following shortest path problem. Consider a directed graph with $n$ levels. Each level has $m$ nodes. Each node at level $i$ is connected to all nodes at level $i+1$. Let us also make a ...
0
votes
0answers
70 views

Finding exact value with a quotients of products of random values

Sorry for the haphazard title: really not sure what this should be called Suppose we have a set of $z$ random values $S = r_1, \dots, r_z$ drawn from $\mathbb{Z}_N$ (where $N$ is some large prime). ...
5
votes
3answers
1k views

Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?

Good Evening! I am aware that the minimum (cardinality) vertex cover problem on cubic graphs ($3$-regular) graphs is $NP$-hard. Say positive integer $k>2$ is fixed. Has there been any ...
2
votes
3answers
177 views

How hard is it to find a “well-distributed” subset of models of a propositional formula?

We consider the propositional language $\mathcal{L}_{\mathit{PS}}$ defined over a finite alphabet $\mathit{PS}$ and the usual logical connectives. An interpretation is an assignment $\mathit{PS} \...
13
votes
1answer
468 views

“Snake” reconfiguration problem

While writing a small post on the complexity of the videogames Nibbler and Snake; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such ...
8
votes
1answer
418 views

Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio ...
9
votes
1answer
255 views

Maximum weight “fair” matching

I'm interested in a variant of the maximum weight matching in a graph, which I call "Maximum Fair Matching". Assume that the graph is full (i.e. $E=V\times V$), has even number of vertices, and that ...
2
votes
2answers
242 views

Balls & Bins: A punishment and reward game

Consider a game where one has a set of bins $(b_1, b_2, ...)$, and each bin has an associated initial count of balls $(c_1, c_2, ...)$. The rules of the game are as follows: (1) Once a bin has a ...
2
votes
0answers
117 views

Calculating the ground state of an Ising model with $\sigma_i = (0,1)$ spin state assignments (do Barahona & Istrail's NP-hardness results hold?)

In a typical Ising model, one has possible spin assignments of $\sigma_i = \pm 1$. However, one can also imagine a $q = 2$ Potts model generalization with spin assignments $\sigma_i = (0,1)$. Is ...
9
votes
0answers
114 views

Reconstructing labeled poset from linear extensions

Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
9
votes
0answers
225 views

Advances towards proving the Held-Karp conjecture for TSP

I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture. The Held-Karp relaxation is conjectured to have an integrality gap of $\...
2
votes
0answers
200 views

Which complexity information of Ising model is more important?

In 1982, Barahona proved that finding the ground state of an Ising model is NP-hard. Later, in 2000, Istrail proved that it is NP-complete. When I look up the citations of these two papers using ...
1
vote
0answers
45 views

Bounding the cost of an approximation algorithm when subtraction involve [closed]

Given an algorithm with approximation ratio $\alpha$, and another algorithm with approximation ratio $\beta=n^\epsilon$, and a solution to a problem with cost $c$. What is the standard way to bound $\...
4
votes
2answers
212 views

Variation on partial Set Cover with penalties

I'm looking at the following problem, which I'm hoping is perhaps a known variant of the Set Cover problem: Input: We're given a universe $U$ and two disjoint subsets $A$ and $B$ such that $A \cup B=...
0
votes
0answers
108 views

Minimum Weight Ordering of nodes on a directed graph

I'm bumping my head against the wall trying to prove this problem is NP-complete (it might not be) Let $G = (V,E)$ be a directed graph with weights $w:E \to \mathbb{R_{\geq 0}}$ on the edges. The ...
4
votes
1answer
183 views

Inapproximability of $(\alpha, \beta)$ bi-criteria approximation

An $(\alpha, \beta)$ bi-criteria approximation algorithm for $k$-center is defined as an algorithm that returns a solution whose value is $\beta \cdot OPT$ ($OPT$ being the optimal solution for the $k$...
10
votes
1answer
606 views

Probability of generating a desired permutation by random swaps

I'm interested in the following problem. We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$. Then, starting with the list $L=...
6
votes
0answers
246 views

NP-hardness of tasks graph assignment to two heterogenous servers

I have a problem with determinig if the following assignment problem is NP-hard. Any comments and suggestions would be appreciated. Problem definition Given is a directed acyclic graph $G=(V,E)$ ...
1
vote
1answer
198 views

Node-weighted steiner problem with few terminals

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight subset ...
8
votes
1answer
585 views

Definition of Planar 3-SAT

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?
0
votes
1answer
350 views

Hardness of an extended maximum set packing problem

(Edited) The maximum set packing problem when the sets are all of equal size, say $k$, is known to be NP-hard for $k \ge 3$. The requirement in this problem is that the sets in the solution will be ...
2
votes
1answer
314 views

Complexity class of a subset problem similar to subset sum

What could be the complexity class of the following problem: Given a positive integer $K$, a positive integer $d$ (say $2$) and a set $S$ of all non-negative integers less than $K$ find a $S' \...
12
votes
2answers
1k views

Hamiltonian cycle on graphs without small cycles

While answering this question on cstheory, I (informally) proved on the fly the following theorem: Theorem: For any fixed $l \geq 3$ the Hamiltonian cycle probem remains NP-complete even if ...
12
votes
1answer
248 views

Hard extendability problems

In extendability problem, we are given part of the solution and we want to decide whether we can extend it to a complete solution. Some extendability problems are efficiently solvable while other ...
5
votes
0answers
508 views

NP-completeness of the Dominating set problem for planar graphs of maximum degree 3?

I am trying to learn about some techniques that are used for proving the NP-completeness of domination related problems. One of the problems that is known to be NP-complete is the domination number of ...
3
votes
1answer
1k views

Hardness of 3-dimensional matching variant

I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose ...
3
votes
1answer
226 views

NP-hardness of a bilinear program?

Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$ and $d_{ij}=d_{ji}$. I have the following bilinear program: max $\sum_{i=1}^n (x_i-a_i)y_i$ ...
2
votes
0answers
156 views

Graph partition with objective over intra-partition weights

I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
1
vote
0answers
57 views

Help in NP-Hardness proof of a certain type of Class Cover problem

Class Cover Problem is nothing but finding an optimal cover of certain class (Point Set) with a particular shape only i.e. finding minimum number of a certain shaped polygon (for example, rectangle) ...
2
votes
1answer
194 views

Set cover with budget on sets

I am wondering if this is a studied variant of the Set Cover problem. We are given a universe $X$, a collection of sets $S = \{S_1, ..., S_m\}$ and integers $c_i$. We want to cover all elements in $...
8
votes
1answer
336 views

NP-hardness proof: looking for some good restricted np-hard problems

To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can ...
2
votes
2answers
321 views

For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?

The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows: Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Does there exist $k$-...
6
votes
5answers
1k views

Multidimensional knapsack STRONGLY NP-complete

Who can point me to a reference where it is actually shown that multidimensional knapsack is strongly NP-complete? I have found loads of papers where they claim it is, without citation; I have found ...
1
vote
0answers
70 views

Different hardness proofs w.r.t different classes

Consider a language $L$ which is hard for some class $C$ (e.g. PSPACE-hard). Trivially, $L$ is also $D$-hard for every class $D\subseteq C$ under the same type of reduction (e.g. NP-hard). Is there a ...
8
votes
1answer
581 views

Max-weight connected subgraph problem in planar graphs

The maximum-weight connected subgraph problem is as follows: Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$. Output: a maximum-weight subset $S$ of ...
-1
votes
1answer
126 views

NP Hardness of Metric Steiner Tree

It is known that the metric steiner tree problem is NP hard (Garry and Johnson [1977]). I wanted to know if there is a simpler way of proving the same. Specifically, I am trying to find a polynomial ...
7
votes
0answers
163 views

What relations are there between a problem hardness and the hardness of verifying a witness?

I had some hard times trying to formulate the question, so I'll start with some examples: Suppose you are given a Dominating Set instance, $<G,k>$. Now suppose I give you a set of vertices $D$ ...
4
votes
0answers
217 views

How does part 5 of the paper “computational complexity of Minesweeper” work?

Marzio De Biasi mentioned this paper in this answer, and that paper's claim in part 5 would appear to resolve my question. However, there seems to be a significant gap in the proof. Even though one ...
7
votes
1answer
632 views

Is it NP-hard to _play_ minesweeper perfectly?

This paper shows that it is NP-hard "to determine if there is some pattern of mines in the blank squares that give rise to the numbers seen." If there is a way to "lead a perfect player into" such ...
4
votes
0answers
402 views

another solution problem (ASP) of integer multicommodity flow: is it NP-complete?

I know that integer multicommodity flow is NP-complete. It was proven in "On the complexity of time table and multi-commodity flow problems" (http://dl.acm.org/citation.cfm?id=1382492) that any SAT ...
2
votes
1answer
138 views

Complexity of Haemers' minimum rank

In 1978 Willem H. Haemmers published "An upper bound on the Shannon capacity of a graph". Tims has a survey of more recent results his thesis. What is the computational complexity of computing ...
22
votes
10answers
2k views

Problems that are easy on unweighted graphs, but hard for weighted graphs

Many algorithmic graph problems can be solved in polynomial time both on unweighted and weighted graphs. Some examples are shortest path, min spanning tree, longest path (in directed acyclic graphs), ...
21
votes
2answers
914 views

$NP$-completeness of recognizing the difference of two permutations

Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two ...