Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
11
votes
1answer
246 views

maximize MST(G[S]) over all induced subgraphs G[S] in a metric graph

Has this problem been studied before? Given a metric undirected graph G (edge lengths satisfy triangle inequality), find a set S of vertices such that MST(G[S]) is maximized, where MST(G[S]) is the ...
11
votes
0answers
316 views

Is unary $\Pi_2$-SUBSETSUM coNP-complete?

Consider the following problem: for given integers $a_1, \ldots, a_{2n}$ and $A$ that are given in unary representation define is it true that for every $S \subseteq \{1, ..., 2n \}$ such that $|...
11
votes
0answers
328 views

a geometric variant of k-medians. NP-hard or in P?

The following problem is a special case of k-medians. Is it NP-hard? Is it in P? Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$. Output: a set ...
10
votes
2answers
1k views

Is Almost-2-SAT NP-hard?

Is a CNF SAT problem NP hard when the total number (but not the width) of the 3-or-more-term clauses is bounded above by a constant? What about specifically when there's only one such clause?
10
votes
2answers
473 views

Hardness of a subcase of Set Cover

How hard is the Set Cover problem if the number of elements is bounded by some function (e.g, $\log n$) where $n$ is the size of the problem instance. Formally, Let $\mathcal{U}=\{e_1, \cdots, e_m\}$...
10
votes
1answer
727 views

Relationship between two graph optimization problems

Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph: P1. Find a largest induced subgraph of the ...
10
votes
1answer
303 views

Hamilton Decomposition Decision Problem

Let $G=(V,E)$ be an undirected graph. A decomposition of $V$ into disjoint subsets $V_i$ is called a Hamilton decomposition of $G$ if the subgraph induced by each set $V_i$ is either a Hamilton graph ...
10
votes
1answer
700 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=...
10
votes
2answers
600 views

Exact exponential-time algorithms for 0-1 programming

Are there known algorithms for the following problem that beat the naive algorithm? Input: A system $Ax \le b$ of $m$ linear inequalities. Output: A feasible solution $x^*\in \{0,1 \}^n$ if one ...
10
votes
3answers
424 views

Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton

Problem statement : Let $M$ be a (potentially nondeterministic) pushdown automaton and let $\cal A$ be its input alphabet. Is there a word $w \in \cal A^*$ s. t. $|w| \leq k$ that is accepted by $M$ ?...
10
votes
2answers
1k views

NP-complete variants of undecidable problems?

Examples of bounded $NP$-complete variants of undecidable sets: Bounded Halting problem={ $(M, x, 1^t)$| NTM machine $M$ halts and accepts $x$ within $t$ steps} Bounded Tiling={ $(T, 1^t)$| there is ...
10
votes
1answer
1k 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?
10
votes
2answers
530 views

Complexity of hidden polygon puzzle on square grids?

Hiroimono is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle. The problem is: Input: Given a set of points on on a $n$x$n$ square grid and ...
10
votes
1answer
5k views

Monotone bijections between lists of intervals

I have the following problem: Input: two sets of intervals $S$ and $T$ (all endpoints are integers). Query: is there a monotone bijection $f:S \to T$? The bijection is monotone w.r.t. the set ...
10
votes
1answer
426 views

What are the complexities of the following SAT subsets ?

Assume $P \neq NP$ Let use the following notation ${}^ia$ for tetration (ie. ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$). |x| is the size of the instance x. Let L be ...
10
votes
1answer
436 views

Hardness of constrained star system problem?

A star system is a family $F$ of n subsets of n-elements set $S$. A star system is graphical if there is some graph $G(V,E)$ such that $F$ is the family of vertex neighborhoods in $G$. It is $NP$-...
10
votes
2answers
244 views

Common insights into hypothetical complexity of graph problems

I came across two examples of hypothetical hardness of some graph problems. Hypothetical hardness means that refuting some conjecture would imply the NP-completeness of the respective graph problem. ...
10
votes
1answer
323 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 ...
10
votes
2answers
1k views

A variant of Critical SAT in DP

A language $L$ is in the class $DP$ iff there are two languages $L1 \in NP$ and $L2 \in coNP$ such that $L = L1 \cap L2$ A canonical $DP$-complete problem is SAT-UNSAT : given two 3-CNF expressions, $...
10
votes
0answers
127 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 ...
10
votes
2answers
713 views

Set optimization problem - is it np-complete?

Set $S=\{e_1,\cdots,e_n\}$ is given. For each element $e_i$, we have weight $w_i>0$ and cost $c_i>0$. The goal is findIng the subset $M$ of size $k$ that maximize the following objective ...
9
votes
3answers
897 views

Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?

There are some NP-Complete problems ($ \mathsf{SAT} $, $ \mathsf{SUBSETSUM} $, etc.) known to be in $ \mathsf{DSPACE(n)} $. What about the sub-linear spaces? Is there any known NP-Complete (or NP-...
9
votes
1answer
1k views

Does every Turing-recognizable undecidable language have a NP-complete subset?

Does every Turing-recognizable undecidable language have a NP-complete subset? The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an ...
9
votes
2answers
3k views

What are good approximation algorithms for the subset sum problem so far?

By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.
9
votes
2answers
126 views

Complexity of finding an edge set yielding specified vertex degrees

I'm trying to figure out if the following two problems are known in general to be in P or NP-complete: Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'\...
9
votes
1answer
690 views

Fitting minimum number of rectangles of width/height 1 into a 2D grid

Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied and you need to put the minimum number of non-overlapping rectangles of any size w x h where ...
9
votes
1answer
369 views

Is the backup problem NP-complete?

Is the following decision problem NP-complete: Let $G$ be an undirected graph and $b \le c$ two integers. Is it possible to select for every vertex of $G$ exactly $b$ different neighbors ...
9
votes
1answer
790 views

Proof that sparsest cut is NP-hard

Everywhere that I read about the sparsest cut problem, it only says that the problem is known to be NP-hard. Where can I find a proof of this? Which known NP-hard problem reduces to the sparsest cut ...
9
votes
2answers
394 views

Exact exponential-time algorithms for 0-1 programs with nonnegative data

Are there known algorithms for the following problem that beat the naive algorithm? Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers. Output: an optimal ...
9
votes
3answers
728 views

Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems?

Suppose P != NP. We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there ...
9
votes
2answers
356 views

NP-hardness of a planar SAT variant

Background: An instance of 3-SAT is called monotone if each clause consists only of positive literals or only of negative literals. Given an instance $\phi$ of 3-SAT, we consider the bipartite graph $...
9
votes
1answer
188 views

Best known asymptotic PCP sizes / 3-SAT

What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs? Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am ...
9
votes
1answer
762 views

NP-Hardness of a special case of orthogonal packing problem

Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used ...
9
votes
1answer
262 views

Complexity of digraph homomorphism to an oriented cycle

Given a fixed directed graph (digraph) $D$, the $D$-COLORING decision problem asks whether an input digraph $G$ has a homomorphism to $D$. (A homomorphism of $G$ to $D$ is a mapping $f$ of $V(G)$ to $...
9
votes
1answer
239 views

Consequences of a distillation algorithm for PSPACE

The following notion of a distillation algorithm comes from "On Problems Without Polynomial Kernels". Let a language $L$ be given. A distillation algorithm for $L$ takes a given list of input ...
9
votes
1answer
225 views

What is known about the hardness of the chromatic index for restricted graph classes?

There is a nice paper from 1991 that contains three diagrams about different graphclass-families showing what is known about the hardness of determining the chromatic index for them. Are there any ...
9
votes
1answer
732 views

Does 1-in-3 SAT remain NP-hard even if every variable occurs both positively and negatively?

The standard problem 1-in-3 SAT (or XSAT or X3SAT) is: Instance: a CNF formula with every clause containing exactly 3 literals Question: is there a satisfying assignment setting precisely 1 literal ...
9
votes
1answer
1k views

Complexity of finding the maximal number of pair-wise disjoint sets

Assume that I have $P$ sets with elements taken from $r$ possible ones. Each set is of size $n$ ($n<r$), where the sets can overlap. I want to determine whether the following two problems are NP-...
9
votes
1answer
185 views

Edge-partitioning into rainbow triangles

I'm wondering if the following problem is NP-hard. Input: $G = (V,E)$ a simple graph, and a coloring $f : E \to \{1,2,3\}$ of the edges ($f$ does not verify any specific property). Question:...
9
votes
1answer
231 views

Recent progress on the next-to-shortest-path problem for directed graphs?

In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem: Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be vertices in ...
9
votes
0answers
146 views

Optimal bee swarm plots: NP-hard?

Bee swarm plots are a way of visualizing one-dimensional data sets, similar to box plots. The idea is that if there's not too many points (e.g. <300) we can just plot them along the $x$-axis with ...
9
votes
0answers
156 views

Complexity of fractional SAT

Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...
9
votes
0answers
417 views

What are the best known reductions from SAT to CNF-SAT?

Problems Let SAT denote the following problem: Given a boolean formula, does there exist a satisfying assignment? Let CNF-SAT denote the following problem: Given a ...
9
votes
0answers
344 views

Triangle arrangement problem

Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (...
9
votes
0answers
252 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 $\...
9
votes
1answer
529 views

Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments

Given a tournament $T$ where $S_1$ and $S_2$ be two acyclic sub-tournament of $T$. Is the following problem NP-Complete: Finding a maximum acyclic sub-tournament $S$, which is subset of $S_1 \cup ...
8
votes
3answers
3k views

Is Deolalikar's 2010 proof that $P \ne NP$ correct?

There was recently a claimed proof that $P \ne NP$. Not long after its publication there were raised some issues with this proof. So ... is the proof correct or not ? (Please only answer this if you ...
8
votes
3answers
2k views

P vs NP: Instructive example of when Brute Force search can be avoided

To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...
8
votes
1answer
29k views

Is integer factorization an NP-complete problem? [duplicate]

Possible Duplicate: What are the consequences of factoring being NP-complete? What notable reference works have covered this?
8
votes
5answers
2k 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 2 3
4
5
13