Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
7 votes
1 answer
1k views

NP-Complete Hard-on-Average Problems

This question considers a special class of problems in (NP,P-samplable). The question is: Do there exists a problem $(L,\mu) \in \mbox{(NP,P-samplable)}$ such that: $L$ is $\rm{NP}$-complete, and $L$...
user avatar
  • 16.4k
9 votes
1 answer
372 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 ...
user avatar
7 votes
3 answers
506 views

Graph classes in which CLIQUE is known to be NP-hard?

Given a graph $G$ and a positive integer $k$, the CLIQUE problem asks if $G$ contains a clique (complete subgraph) on at least $k$ vertices. This problem is long known to be NP-complete --- in fact, ...
user avatar
  • 1,384
2 votes
0 answers
203 views

Is there a list of NPC or harder problems for specific real world problem domains? [closed]

The domains of interest to me are: 1. Robotics 2. Search 3. NLP 4. Image feature extraction 5. Network optimization 6. Network security
user avatar
  • 203
8 votes
0 answers
1k views

Is Exact Cover by Equally-Sized Sets reducible to Multi-Dimensional Matching in a certain nice way?

This question is motivated by my other question “Gap hardness of Multi-Dimensional Cover,” which is in turn motivated by the question “Set Cover for Permutation Matrices” by Brayden Ware. Informal ...
user avatar
  • 16.3k
28 votes
2 answers
2k views

A category of NP-complete problems?

Does it make sense to consider a category of all NP-complete problems, with morphisms as poly-time reductions between different instances? Has anyone ever published a paper about this, and if so, ...
user avatar
12 votes
3 answers
906 views

Edge-partitioning cubic graphs into claws and paths

Again an edge-partitioning problem whose complexity I'm curious about, motivated by a previous question of mine. Input: a cubic graph $G=(V,E)$ Question: is there a partition of $E$ into $E_1, E_2, \...
user avatar
5 votes
2 answers
1k views

Is the following problem NP-Hard?

I'm not expert on complexity theory and combinatorial optimization. I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete. ...
user avatar
10 votes
2 answers
558 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 integer $k$...
user avatar
21 votes
4 answers
2k views

DNA-algorithms and NP-completeness

What is the relationship between DNA-algorithms and the complexity classes defined using Turing machines? What do the complexity measures like time and space correspond to in DNA-algorithms? Can they ...
user avatar
15 votes
3 answers
2k views

Complexity of edge coloring in planar graphs

3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". What is the complexity of 3-edge coloring of cubic ...
user avatar
1 vote
1 answer
265 views

Another edge partitioning problem on cubic graphs

This question was motivated by a closely related problem An edge partitioning problem on cubic graphs Input: at most cubic graph ( maximum node degree is 3) $G=(V,E)$, a natural number $k$ Question:...
user avatar
25 votes
3 answers
2k views

Hardness of approximation - additive error

There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for ...
user avatar
  • 3,920
0 votes
1 answer
498 views

Formalized configuration of Subset sum problem Worst-case ? [closed]

Is there a formal proof of the worst-case configuration of the subset sum problem? In other words - is there a set proven to be the hardest to find a subset equals to 0 from? thanks
user avatar
  • 113
25 votes
1 answer
1k views

An edge partitioning problem on cubic graphs

Has the complexity of the following problem been studied? Input: a cubic (or $3$-regular) graph $G=(V,E)$, a natural upper bound $t$ Question: is there a partition of $E$ into $|E|/3$ parts of size $...
user avatar
12 votes
2 answers
1k views

Reducing P vs. NP to SAT

The following question uses ideas from cryptography applied to complexity theory. That said, it is a purely complexity-theoretic question, and no crypto knowledge whatsoever is required to answer it. ...
user avatar
  • 16.4k
7 votes
3 answers
875 views

Non-rooted MST of directed graph

I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the ...
user avatar
  • 285
13 votes
1 answer
525 views

Is "Is a permutation p an automorphism of a graph in my set?" NP-complete?

Suppose we have a set S of graphs (finite graphs, but an infinite number of them) and a group P of permutations that acts on S. Instance: A permutation p in P. Question: Does there exist a graph g in ...
user avatar
2 votes
1 answer
4k views

Difference between NP-Hard and NP-Complete [closed]

Can someone please summarize the exact difference between NP-Complete and NP-Hard problems in simple language? Wiki and my standard books aren't exactly helping.
user avatar
4 votes
1 answer
497 views

Better approximation for special case of 3-hitting set

I have a question based on 3-Hitting Set problem. In this problem, we are given a universal set U of size n and a set of subsets S such that $\forall $ s $\in$ S |s|<=3. FOr this problem, Integer ...
user avatar
  • 467
28 votes
3 answers
2k views

Is it NP-hard to play international draughts correctly?

Is the following problem NP-hard? Given a board configuration for $n\times n$ international draughts, find a single legal move. The corresponding problem for $n\times n$ American checkers (aka ...
user avatar
  • 22.8k
9 votes
1 answer
540 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 ...
user avatar
  • 467
12 votes
4 answers
2k views

Directed NP-hard problems on DAGs

Tree width measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This ...
user avatar
16 votes
1 answer
861 views

Completeness and Context-Sensitive Languages.

I'm interested in two questions regarding context-sensitive languages (CSL) and completeness: Is there a notion of completeness for CSL, and which languages are complete? Are there natural CSL that ...
user avatar
49 votes
4 answers
12k views

Is finding the minimum regular expression an NP-complete problem?

I am thinking of the following problem: I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses). ...
user avatar
20 votes
4 answers
1k views

Positive topological ordering, take 3

Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix? This question is motivated by this problem: Positive topological ordering ...
user avatar
  • 13.5k
6 votes
0 answers
213 views

Further question on hardness of node partitioning under shortest path constraint

This question first appeared at Hardness of node partitioning under shortest path constraint and I restate it here Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \...
user avatar
  • 283
26 votes
2 answers
3k views

Hamiltonicity of k-regular graphs

It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, ...
user avatar
28 votes
5 answers
3k views

Verifying unique solutions of SAT

Consider the following problem: given a CNF formula and an assignment that satisfies this formula, is there another satisfying assignment for this formula ? What is the complexity of this problem ? (...
user avatar
  • 381
3 votes
2 answers
387 views

Complexity of the Hamiltonian Subcycle problem

The problem is as follows: Given a graph $G$, find a (vertex) disjoint set of cycles $C$ on $G$ such that every vertex is visited by a cycle exactly once. My question is then: what is the ...
user avatar
15 votes
2 answers
1k views

NP-hard problems on expander graphs?

In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT? , Nati Linial posed the following open problem: Which $NP$-hard computational problem on graph remain hard when ...
user avatar
4 votes
1 answer
622 views

Hardness of node partitioning under shortest path constraint

Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \in R$ (negative weight is possible). A label $l(i)$ is associated with each node $i \in V$. How to assign $k$ (or less)...
user avatar
  • 283
10 votes
1 answer
431 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 ...
user avatar
5 votes
1 answer
368 views

Complexity of finding vectors with optimal projection?

Input: a set $T$ of vectors $v_i=(x_i,y_i,z_i)$. Where $x_i,y_i,z_i$ are integers. Output: a subset of vectors $v_1,v_2,...,v_n$ with vector addition $m=\sum v_i$ such that the projection of $m$ on ...
user avatar
5 votes
2 answers
365 views

Use of Lagrangian dual information to prove optimalitiy of a solution : Any example?

Can anyone please tell me what is Lagrangian Dual Information and how can it be used to prove the optimality of a solution? I'm talking about the solution to NP-Complete problems. Is it something that ...
user avatar
1 vote
1 answer
1k views

Removing all but a few cycles in a graph

Let problem $S$ be defined as Given undirected graph $G$ and a set of cycles $C_1,C_2, \ldots, C_n$ in G, find minimum number of vertices that need to be deleted to remove all cycles in the ...
user avatar
  • 467
51 votes
20 answers
8k views

NP-hard problems on trees

Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
user avatar
11 votes
2 answers
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 ...
user avatar
10 votes
1 answer
438 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$-...
user avatar
3 votes
2 answers
4k views

Using decision version of TSP to solve optimization version

Given an oracle for solving the decision version of TSP, how would I use this to solve the optimization version of TSP. This is not a homework assignment, but of general interest. I have been trying ...
user avatar
  • 171
14 votes
1 answer
913 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
user avatar
  • 2,756
7 votes
4 answers
889 views

A relaxed Steiner Tree Problem

Given a weighted graph $G(V,E,w)$ where $w$ is the weight function on edges and a subset of vertices $S\subseteq Q$ called terminals, a Steiner Tree is a connected subgraph which connects all vertices ...
user avatar
  • 73
5 votes
1 answer
437 views

Comparing $\mathbf{NP}$ and $\mathbf{E}$

We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$. The complexity zoo states that $\mathbf{E}$ does not equal $\mathbf{NP}$, and cites the following ...
user avatar
  • 16.4k
7 votes
1 answer
4k views

Simple reduction to unbounded knapsack?

Does anyone know (or can anyone think of) a simple reduction from (for example) PARTITION, 0-1-KNAPSACK, BIN-PACKING or SUBSET-SUM (or even 3SAT) to the UBK problem (integral knapsack with unlimited ...
user avatar
0 votes
2 answers
923 views

Where is the error in the following P != NP pseudo-proof ?

Here is a necessarily wrong proof of $P \neq NP$ as it relativizes, but I can't find the error : Le $U$ be a universal Turing machine, whose inputs are restricted to Turing machines accepting ...
user avatar
11 votes
1 answer
443 views

Computation of max H-free sets

In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question,...
user avatar
  • 1,952
8 votes
4 answers
2k views

Complexity of marriage matching problem?

Suppose you have $n$ males and $n$ females. Each person has $m$ attributes. Each person indicates a set of attributes that a possible candidate should have. A matching is a set of pairs. Each pair ...
user avatar
6 votes
3 answers
835 views

In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.

Given strongly connected tournament T.find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament. I have doubt whether the problem mentioned can be solved in polynomial ...
user avatar
  • 467
20 votes
3 answers
746 views

Is it hard to find optimal addition chains?

An addition chain is a sequence of positive integers $(x_1, x_2, \dots, x_n)$ where $x_1 = 1$ and each index $i\ge 2$, we have $x_i = x_j + x_k$ for some indices $1\le j,k < i$. The length of the ...
user avatar
  • 22.8k
13 votes
2 answers
378 views

H-free partition

This is a question inspired by the H-free cut problem. Given a graph, a partition of its vertex set $V$ into $r$ parts $V_1, V_2, \ldots, V_r$ is $H$-free if $G[V_i]$ does not induce a copy of $H$ for ...
user avatar
  • 599