Questions tagged [np-hardness]

Questions related to NP-hardness and NP-completeness.

Filter by
Sorted by
Tagged with
1
vote
0answers
12 views

What is the complexity of this weighted b-edge matching problem?

I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem: Input: An undirected multigraph $G = (V, E)$ without loops, an edge partition $(E_1,...
0
votes
2answers
103 views

Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials? [closed]

Arora and Barak define NP-completeness as the following: "We say that a language $A \subseteq \{0, 1\}^∗$ is polynomial-time Karp reducible to a language $B \subseteq \{0, 1\}^∗$ denoted by $A \leq_p ...
2
votes
0answers
87 views

Complexity of a scheduling problem with a fixed left bound of jobs

Consider the following scheduling problem. We have a finite set of jobs $\mathcal{J}= \{j_1, j_2, ..., j_n\}$ to do. Every job $j_i$ has its own value $c_i$ (the amount of money we are paid for ...
7
votes
5answers
337 views

NP-complete decision problems on deterministic automata

Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
7
votes
1answer
258 views

Complexity of constructing minimum depth decision trees

I am interested in the computational complexity of Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
-3
votes
1answer
91 views

is this selection problem np-hard? [closed]

Give $n$ clusters $C=\{C_i\}_{i=1}^n$ where each cluster consists of a set of similar points, i.e., $C_i=\{c_j\}_{j=1}^{|C_i|}$. The similarty between two points $c_i$ and $c_j$ is denoted as $w(c_i,...
3
votes
1answer
325 views

Best parameterized algorithm for maximum clique

I have seen the basic algorithm for the maximum clique problem parameterized by the maximum degree at an algorithms course. However, I struggle to find anything better. Searching for things like "...
0
votes
1answer
90 views

Is the counting version of 1-in-3 Sat #P-complete?

In the paper "Hard Tiling Problems with Simple Tiles", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat. Cubic Planar Positive 1-in-...
0
votes
0answers
83 views

NP-Hard Knapsack Instances

Consider the classic Knapsack optimization problem (KP): Given $p_1, \dots, p_n, w_1, \dots, w_n, B\in\mathbb N$, compute a solution $I\subseteq \{1,\dots,n\}$, such that $\sum_{i\in I} w_i \leq B$ ...
6
votes
1answer
86 views

Determining if a word of specific length exists that is not accepted by a NFA

It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard? Given an NFA and a ...
0
votes
0answers
56 views

Complexity of multi-objective optimization problems

How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)? It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
1
vote
1answer
80 views

The decision procedure of theory of closed real field is in NP-hard?

The decision procedure of theory of closed real field refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers
4
votes
1answer
120 views

Hardness of finding if a vertex lies on a simple directed path between two vertices

Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$? I found a couple of hardness ...
9
votes
2answers
113 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'...
6
votes
2answers
144 views

$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$

Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$ be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup ...
12
votes
0answers
132 views

NP-Hardness of 4-cycle packing problem in complete bipartite digraph?

A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a ...
10
votes
1answer
700 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 ...
2
votes
0answers
75 views

How hard is it to approximate distance of linear code

I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance. I of course found that ...
2
votes
1answer
140 views

What Is the Complexity of This Two-to-One Matching Problem?

Given a graph $G=(V,E)$ and a function $c:V\mapsto\{1,2\}$. The function $c(\cdot)$ divides the vertices into two disjoint sets $V_1$ and $V_2$, where for all $v_1\in V_1$, we have $c(v_1)=1$ and for ...
-4
votes
1answer
106 views

Example of decidable NP-hard problem that is not NP-complete [closed]

I am looking for an example of a decision problem which fulfills the following conditions: 1. It is decidable 2. It is NP-hard 3. It is not NP-complete All my search attempts yielded examples that ...
7
votes
1answer
215 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 ...
1
vote
1answer
225 views

What languages can be reduced to a NP-complete problem in polynomial time

NP-complete: Language is NP-complete, when it is in NP and every problem in NP is reducible to it in polynomial time. But what languages are reducible to a NP-complete problem (for example SAT) in ...
7
votes
0answers
132 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 ...
2
votes
1answer
92 views

Diameter vs. Tractability

I would like to find examples of (unweighted) optimization problems $\Pi$ that satisfy 1) or 2): 1) $\Pi$ is NP-hard but polytime solvable in the class of graphs with diameter $\le k$, for all $k\ge ...
2
votes
0answers
53 views

Complexity of Block Design?

What is known about the complexity of creating Block Designs (https://en.wikipedia.org/wiki/Block_design)? I've found one paper that creates approximately solutions using Metaheuristics that claims ...
2
votes
0answers
91 views

How hard is it to determine ex(n,G)?

Define the extremal Turán function $ex(n,G)$ of a graph $G$ as the most edges a graph on $n$ vertices can have without having a subgraph that is isomorphic to $G$. This function is known ...
0
votes
1answer
172 views

Find the shortest s-t trail(edge disjoint path) in a graph with negative weight edges

A walk in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. A trail is a walk in which all edges are distinct. Note that a trial may visit a vertex multiple times ...
0
votes
0answers
102 views

Network Reliability Problem

Network reliability, in which we are given an undirected graph $G$ with a failure probability $p_e$ for each edge and we are asked to calculate the probability that the network becomes disconnected ...
11
votes
0answers
307 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 $|...
0
votes
0answers
64 views

Generalization of k-Coloring: maximizing the number of vertices with no neighbours of same color

One can consider the following generalization of the $k$-Coloring problem: Let be given a graph $G$ and an two integers $k$ and $p$. A vertex $v$ of $G$ is properly colored if $v$ has no neighbour ...
2
votes
0answers
55 views

Is minimal cover under symmetric 3-deduction NP-complete?

Forgive me if this problem is known by another name, I do not know any references for it. Symmetric deduction. An equation $e \in E$ is a subset of variables $V$ such that knowing $|e| - 1$ of the ...
3
votes
1answer
88 views

Complexity of existence of simple polygonalization with prescribed area?

This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
13
votes
0answers
217 views

Which monotone DNFs are evasive?

A Boolean function $\phi$ on variables $X$ is evasive if every decision tree for $\phi$ has height $|X|$. In other words, for any strategy that picks variables of $X$ and asks for their value, an ...
8
votes
1answer
204 views

A partition problem with order constraints

In the OrderedPartition problem, the input is two sequences of $n$ positive integers, $(a_i)_{i\in [n]}$ and $(b_i)_{i\in [n]}$. The output is a partition of the ...
-3
votes
1answer
175 views

Can we map this problem to subset-sum?

Let there be $n$ set of ordered pairs $s_1=\{(c_1,f_1),(c_1,f_2) ...(c_1,f_m)\}$, $s_2=\{(c_2,f_1),(c_2,f_2) ...(c_2,f_m)\}$, $s_3=\{(c_3,f_1),(c_3,f_2) ...(c_3,f_m)\}$, .... $s_n=\{(c_n,f_1)(c_n,f_2) ...
5
votes
1answer
141 views

Complexity of Finding Largest Set of Intersecting Convex Polytopes

I have a set of $n$ convex polytopes, and I wish to find the largest subset of those polytopes that shares at least one point in common. I think that this problem should be NP-hard, but I am ...
8
votes
1answer
343 views

Planar Exact Cover by even-size sets

Major edit on June 6, 2019: Replaced the target problem with a simpler (but equivalent) one. Is the following problem NP-complete? Planar Exact Cover by even-size sets Input: A set $U$, a ...
5
votes
0answers
71 views

Complexity of a specific class of definite integrals

INTRODUCTION: From the answer to this question I learned that deciding whether a definite integral is $0$ or not can be NP-complete, as the following integral representation of the Number Partition ...
1
vote
0answers
32 views

Scheduling with Separation Constraint

There are $N$ types of jobs. For each $i$, we have to schedule $T/D_i$ jobs of type $i$ in $T$ timeslots. We know that $\sum_{i=1}^N 1/(D_i+1) = 1$. For each type $i$, the distance between two ...
10
votes
1answer
305 views

How hard is deciding the existence of Red-Blue perfect matching?

Two-colorable perfect matching problem is to decide whether a graph has coloring with two colors such that each node has exactly one neighbor the same color as itself. The problem was proven to be NP-...
1
vote
0answers
81 views

Minimum cut with nonlinear objective function

Let $G$ be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut $C\subseteq E(G)$, such that $|C|$ is minimum. Let us generalize it the following way: let $f$ be a ...
7
votes
0answers
141 views

NP-hardness proof of selecting the ''fittest'' topological sequence of a DAG

Given a directed acyclic graph (DAG) with $n$ vertexes $V=\{v_1, v_2,...,v_n\}$ and a given permutation of those $n$ vertexes $P=[p_1, p_2,..., p_n]$ that $\forall i, p_i\in V$. Note that $P$ could ...
15
votes
1answer
629 views

Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ . Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph ...
2
votes
0answers
82 views

Finding 3SUM witness when promised a solution

Suppose we have a 3SUM instance given with the promise that there exists at least one solution. Is the trivial $O(n^2)$ (modulo logarithmic improvements) solution still the best algorithm or is there ...
3
votes
0answers
167 views

Take a NEXP-complete problem and then have the input in unary. Why is this not NP-complete?

It is known that if any unary language is NP-complete, then P=NP. Suppose we take a NEXP-complete language with input $x$ in binary and witness $y\in\{0,1\}^{2^{poly(|x|)}}$ such that the verifying ...
8
votes
0answers
238 views

Subset sum problem with at most one solution for any target

This question was originally asked on CS.se. A little bit of initial discussion can be found in the comments there. We first consider the search version of the subset sum problem: Given a set $S$ of ...
1
vote
1answer
106 views

3 dimensional matching shortest solution NP-hard?

We have array of arbitrary number of elements - 3d vectors with positive integers components - for example ...
3
votes
0answers
70 views

Rearranging angles of a convex polyline to make it closed

Let {$\alpha_1, \alpha_2, ... ,\alpha_n$} be a string of n positive reals summing up to 2$\pi$. We inductively construct the following 2D polyline, denoting with $R[\alpha]$ the clockwise rotation by ...
5
votes
0answers
104 views

Is monotone 1-in-3 MAXSAT known to be APX hard?

Monotone 1-in-3 SAT is the problem where each clause of the SAT problem contains exactly 3 positive variables. The goal is to find an assignment such that exactly one variable is true in each clause ...
6
votes
1answer
195 views

Minimal generator for a set of sets

Is this a known problem? Given a set of sets $S$ find a set of sets $B$ s.t. each set in $S$ can be obtained through unions of some sets in $B$. The set $S$ is already a solution but the objective is ...

1
2 3 4 5
12