Questions tagged [np]
In computational complexity, NP is the complexity class consisting of problems whose yes instances can be verified in polynomial time. NP stands for 'nondeterministic polynomial time '.
40
questions with no upvoted or accepted answers
10
votes
0
answers
303
views
Testing contrasts in statistics: Is this provably a hard problem, or not?
Scheffé's method for identifying statistically significant contrasts is widely known. A contrast among the means $\mu_i$, $i=1,\ldots,r$ of $r$ populations is a linear combination $\sum_{i=1}^r c_i \...
- 11.9k
6
votes
0
answers
462
views
Any approximation algorithms for self-avoiding walks?
I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
- 565
5
votes
0
answers
138
views
Are there sampNP-intermediate problems?
This questions is approximately cross-posted from theoretical computer science stackexchange
Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \...
- 1,368
4
votes
0
answers
175
views
Is the Weber problem a NP-hard problem?
The Weber problem is a special case of a facilities location problem : In a basic formulation, the facility location problem consists of a set of potential facility sites L where a facility can be ...
- 141
3
votes
0
answers
239
views
Is there a version of 3-SAT that is NP-complete but grows like $2^n$ instead of $2^{n \choose 3}$?
If I have $n$ variables and I want to write down all 3-SAT problems, the number of problems is $2^{8{n \choose 3}}$, since each clause has 3 variables and each variable can be negated or not.
But ...
- 31
3
votes
0
answers
54
views
Karp hardness of two cycles which lengths differ by one
Our problem is as follows:
NEARLY-EQUAL-CYCLE-PAIR
Input: An undirected graph $G(V,E)$
Output: YES if there exists $2$ (simple) cycles in $G$ which lengths differ by $1$, otherwise NO
Is it $NP$-...
- 121
3
votes
0
answers
148
views
$\mathrm{NP}$-complete problems in graph theory: undirected vs. directed
Is it true that it is much easier to establish $\mathrm{NP}$-complete on undirected graphs than digraphs (directed graph)?
Academic articles proving $\mathrm{NP}$-completeness of problems on ...
user128192
3
votes
0
answers
260
views
Partitioning a cubic graph into two induced cycles of equal order
I am aware that deciding the existence of a partition of the vertices of a connected graph $G(V, E)$ into two induced cycles is $NP$-complete(Theorem 2). Induced cycle is a cycle without any chord (...
- 2,951
3
votes
0
answers
242
views
Intermediate $\mathsf{NP}$-complete problems?
Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition problem is strongly NP-...
- 2,951
3
votes
0
answers
3k
views
0,1 solution to system of linear integer equations
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
- 149
2
votes
0
answers
55
views
Proof for the NP-hardness of the Max-3-DCC Problem
The Max-3-DCC is the variant of vertex cycle cover problem where each of the vertex disjoint oriented cycles consists of at least 3 arcs and every vertex belongs to exactly one of those cycles; ...
- 12.7k
2
votes
0
answers
86
views
NP - hardness of school scheduling problem with a restriction
I do have a real-life scheduling problem for a special education school.
Basically, i have a binary variable containing teachers, subject, time slot and rooms as indices.
The goal is to assign each ...
- 21
2
votes
0
answers
150
views
How hard is recognizing a permutation that is a square for the shift product?
This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...
- 2,951
2
votes
0
answers
313
views
Complexity of a variant of the Mandelbrot set decision problem?
This is a modified version of a question posted on StackExchange TCS.
Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number. Let us define
$M=${$(c,k,r)...
- 2,951
1
vote
0
answers
47
views
Hardness of an optimization problem when some variables are fixed
Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed.
With the two (related) examples, it is clear that ...
- 11
1
vote
0
answers
27
views
Path cover with sets of nodes
I am considering the following variant of the path-cover problem. I have an acyclic directed graph G=(V,E). Moreover, the set V is partitioned into $V=V_1 \cup ... \cup V_k$ (these sets are pairwise ...
1
vote
0
answers
71
views
cut a path from DAG that has minimal conductance
Given a directed acyclic graph $G=(V,E)$, a source node $s$ and a sink node $t$, we want to find a path $P$ from $s$ to $t$ such that if we separate all the nodes in $V$ to two parts $P$ (all the ...
- 143
1
vote
0
answers
55
views
What is an approximation algorithm in the context of NP completeness in general
In theorem 4 of Approximability of Minimum-weight Cycle Covers Bodo Manthey proves that:
Then no approximation algorithm
for $\operatorname{Min-L-DCC}$ achieves an approximation ratio of $o(n)$, ...
- 12.7k
1
vote
0
answers
66
views
Subgraph isomorphism problem with linear map
I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem:
Problem 1: Given two graphs $G=(V, E)$ ...
- 101
1
vote
0
answers
45
views
Computational complexity of rate $\frac{1}{2}$ codes
We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)...
- 71
1
vote
0
answers
101
views
Promise version of minimum distance
It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard.
This immediately also says that given a code $C$, calculating minimum hamming ...
- 71
1
vote
0
answers
43
views
Determining the minimum weight maximal oriented subgraph of a complete directed graph
Let $G(V,A,W):\ |V| = n,\ A=V\times V\setminus \lbrace (v,\ v)\rbrace,\ W\in\mathbb{R}_+^{n\times n},\ W^T\ne W $ be a complete directed graph with asymmetric weights.
Questions:
What is the ...
- 12.7k
1
vote
0
answers
122
views
Is bounded graph isomorphism $NP$ complete?
Fix a matrix $M\in(\mathbb Z\backslash\{0\})^{n\times n}$ where $\|M\|_\infty\leq 2^{poly(n)}$.
Is the bounded graph isomorphism problem
Given symmetric $A,B\in\{0,1\}^{n\times n}$ and $U,V>0$ ...
- 13.7k
1
vote
0
answers
65
views
Shortest Lattice Vector with restricted $x$
Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$.
My questions ...
- 1,096
1
vote
0
answers
195
views
Is it known whether $\mathrm{NP \subseteq P/poly}$?
It is not immediately clear to me whether this statement is true or false. Can finite restrictions of NP problems be computed in polynomial time?
- 11
1
vote
0
answers
76
views
Bipartite clustering is NP-hard?
Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, ...
- 221
1
vote
0
answers
49
views
Cost associated set problem NP-hard
I have the following problem. I wonder whether or not it appears in the literature. Is it NP-hard?
Given a set $S = \{1,2,\ldots,m\}$, and $A_1,\ldots, A_n$ are subsets of $S$. Each set $A_i$ has ...
- 221
1
vote
0
answers
27
views
The complexity of Max-K interval selection
I came up with the following problem, but do not know how to analyze it.
Let $S$ be an ordered set of integers with size $n$ (i.e., $S=\{1,2,...,n\}$). An interval $INV(a,b)$ covers the elements in $...
- 11
1
vote
0
answers
145
views
Are set covering problems with nonlinear cost functions NP-Hard?
Are set covering problems (set cover problem wikipedia) with a nonlinear cost function also NP-hard? Is there a general result about this?
To be more specific the cost function I am interested in ...
1
vote
0
answers
142
views
Non-trivial lower bound on the number of "Graph Diagonals"
The definition of Graph Diagonals, that are the subject of this question, is based on the notions of crossing edges and on connected graphs:
Two edges $AC$ and $BD$ of a complete, symmetric and ...
- 12.7k
1
vote
0
answers
352
views
Is this minimization problem NP-Complete ?
We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.
...
- 209
1
vote
0
answers
259
views
Self-improvement property of optimazation problems?
Maximum CLIQUE problem is very hard to approximate. It has a self-improvement property defined using graph product which is utilized to prove hardness of approximation results. One such example is ...
- 2,951
0
votes
0
answers
29
views
Prove the NP-hardness of the following problem: Whether there exists a partition for a set of data points
Can anybody help me prove the NP-hardness of the following question:
Given $x_0, x_1, ..., x_m \in \mathbb{R}^n$, determine whether there exists a partition $S\cup [m]\backslash S$, such that $x_0 \in ...
0
votes
0
answers
13
views
Complexity of finding single source paths with capacity constraints and length constraints
Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...
- 21
0
votes
0
answers
28
views
The hardness of active learning with fixed budget
I have been looking for theoretical papers studying this question of the fundamental hardness of PAC active learning algorithms. I found a few papers studying the problem from a fixed perspective (...
- 29
0
votes
2
answers
192
views
Compute the average path weights of paths with the same path length in a directed acyclic graph (DAG)
Given a weighted directed acyclic graph (DAG) $G=(V,E)$ with each edge $e\in E$ has a non-negative weight $w(e)$. For a path $p=(e_1,e_2,\dotsc,e_n)$ in $G$, define the path weight as : $w(p)=\sum_{i=...
- 143
0
votes
0
answers
21
views
Complexity of reporting solutions to a decision problems
Suppose we have an oracle that tells us whether an instance of the Hamilton cycle problem contains a Hamilton cycle or not.
Question:
what is the complexity of e.g. finding the edges constituting to a ...
- 12.7k
0
votes
0
answers
65
views
Validity of an argument for an implication of NP-Completeness
Fedor Petrov has posed a notorious problem regarding the existence of a matching in this question: Resolution of multiple edges
As I see it the setting is a constrained bipartite matching and thus, ...
- 12.7k
0
votes
0
answers
121
views
What does it mean to find an efficient algorithm for NP complete problems
Suppose I have a problem $P$, an instance $I$ and an algorithm $A$ that efficently solves $P$ for $I$.
Let $P'$ be $P$ with additional constraints that are violated if $A$ is applied to $I$ and ...
- 12.7k
0
votes
0
answers
103
views
Surd Partition Problem
Could the following "Surd Partition" problem be NP complete? Note that if the square roots are omitted in the following then the problem is well known to have a polynomial solution.
Surd Partition
...
