16

One example: choosing the property "G contains a node that has an edge to all nodes in G" makes P1 trivial in $O(n + m)$ (pick node with largest degree), but makes P2 the problem of finding the minimum size dominating set, which is NP-hard.


10

This is an interesting (and surprising) example for a P $\to$ NP-hard $\to$ P $\to$ NP-hard $\to \cdots$ phase transition: Deciding if a complete graph on $n$ vertices, in which each vertex has a strict ranking of all other vertices, admits a popular matching is in P for odd $n$ and NP-hard for even $n$. (The parameter is the vertex number $n$.) The ...


8

As Mikhail noted, the problem was called Perfect Matching Cut in literatures. It was proved to be NP-complete in the following paper (see Theorem 1 on page 5), with a reduction from monotone 1-in-3-SAT: Pinar Heggernes, Jan Arne Telle. Partitioning Graphs Into Generalized Dominating Sets.


7

Here are a few examples: (Most Common) Cutting Stock Problem - determine patterns for which to cut boards in order to meet demand. (Kinda same problem) - Knapsack with general integer variables - used for column generation in the cutting stock problem Problems with modular constraints: $x \equiv 3 \pmod 5$ can be written as $x + 5y = 3$, $y \in \mathbb{Z}$....


7

A decision variant, without the minimality condition, asking whether there is a set $B$ of size $n$ is called the set basis problem [SP7] in Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. The NP-completeness of it was proved by Stockmeyer.


6

Suppose that the dimension $d$ of the Euclidean space is fixed, and that the input consists of $n$ convex polytopes in $\mathbb{R}^d$ that altogether have $p$ facets. Let $h_1,\ldots,h_p$ denote the supporting hyperplanes for the $p$ facets of the input polytopes. The arrangement of $h_1,\ldots,h_p$ is the decomposition of $\mathbb{R}^d$ into connected open ...


5

The largest number is the soft number I claim that for any instance of your problem, if the instance is solvable (it is possible to partition the numbers using one soft number) then it is possible to solve the instance using the largest number as the sole soft number. This is easy to prove: any solution can be modified into a solution with the largest ...


5

In my opinion, this is an utter triviality, so unimportant that no one would remark on it. Furthermore, the chance that $t$ numbers chosen at random would have gcd > 1 is vanishingly small once $t$ is large. (There is an explicit formula, which says that t integers chosen at random from the interval [1..n] will have gcd 1 with probability tending to $1/\...


5

This problem is NP-complete. I will prove NP-hardness below Source Problem Colored Token Swapping on Cliques: In the colored token swapping problem, we are given a graph with a colored token placed on each vertex. We are given the color of each token. Also, each vertex has a target color which is also given. A swap is an operation in which the tokens on ...


5

Intuitively, the intermediate cases should be neither in P, nor NP-hard. Perhaps it depends exactly on what we mean by "intermediate case". Here is one interpretation for which we can prove something. Note: The Exponential-Time Hypothesis, or ETH, is that it is not the case that, for every constant $\epsilon>0$, SAT has an algorithm running in time $2^{...


4

For part (1), if you allow additional restrictions on your graph class, then independent set, Hamiltonian circuit, dominating set, etc., are NP-hard on arbitrary planar graphs but FPT on planar graphs of bounded diameter (because in planar graphs a bound on diameter implies a bound on treewidth). You can turn this into an artificial problem that is NP-hard ...


4

Edit 2: Embarrassingly, there is a two line proof of the $NP$-hardness, if one starts with the right polytope. First, recall the circulation polytope of a graph on the bottom of page 4 of Generating all vertices of a polyhedron is hard. It's vertices are in bijective correspondence with the directed simple cycles. Therefore, they are hard to sample or ...


4

As proved in this paper: http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf If P != NP can be shown to be independent of Peano Arithmetic, then NP has extremely-close-to-polynomial deterministic time upper bounds. In particular, in such a case, there is a DTIME(n^1og*(n)) algorithm that computes SAT correctly on ...


3

This answer does not solve the question. It only settles the following auxiliary problem formulated by @JohnDvorak in the comments (partitioning a set in 1:2 ratio): Auxiliary problem: Instance: Positive rationals $a_1,\ldots,a_m$ with $\sum_{i=1}^m a_i = 3A$. Question: Does there exist an index set $I\subseteq\{1,\ldots,n\}$ with $\sum_{i\in I}a_i=A$?...


3

Edit: The result is incorrect, see the discussion at the end. Inspired by Mikhail Rudoy's answer, we can generalize to partitioning into $k$ parts with equal sum. The problem is polynomial time solvable for each constant $k$. The input is $a_1,\ldots,a_n$ such that $a_n$ is the largest number. Mikhail's observations are, wlog, the soft number is $a_n$ $...


3

The Rainbow Dominating Set (RDS) remains NP-hard on paths. Given a vertex-colored graph, a RDS is a DS where each color of the graph appears at least once. Tropical dominating sets in vertex-coloured graphs, JDA'18


3

The problem seems to be NP-complete. My reduction is from Planar 1-in-3-SAT, just like in their paper. For each variable, take $2k$ vertices. Each of these is covered by two 4-sets and each 4-set covers two consecutive vertices. Thus, we need to take every second of the 4-sets for each variable, this corresponds to TRUE/FALSE. The other two vertices of the 4-...


3

Your problem is NP-complete, even in two dimensions. There is a straightforward reduction from MINIMUM MAXIMAL MATCHING in bipartite graphs: MINIMUM MAXIMAL MATCHING in bipartite graphs INSTANCE: a bipartite graph $G=(V_1\cup V_2,E)$ with $E\subseteq V_1\times V_2$; an integer $k$ QUESTION: Does $G$ possess a maximal matching $E'$ of cardinality at ...


3

Under Karp reductions, the answer is exactly $\mathbf{NP}$: it is not hard to see that if a language is Karp-reducible to any $\mathbf{NP}$-language, then it is in $\mathbf{NP}$ too. On the other hand, all of $\mathbf{NP}$ reduces to $\mathbf{NP}$-complete languages by definition. Under Turing reductions, the answer is the class $\mathbf{P}^\mathbf{NP}$: ...


3

The longest path problem can be reduced to this problem. Let $G = (V,E)$ be an instance of longest $s,t$-path problem. For each vertex $v \in V$ create two vertices, $v_{in}$ and $v_{out}$, and a directed edge with weight $-1$ from $v_{in}$ to $v_{out}$. For each edge $(u, v) \in E$, create an edge from $u_{out}$ to $v_{in}$ with weight $0$. Now each trial ...


3

You can trivially consider NEXP-complete problems and they satisfy all 3 conditions that you're looking for. And by the Time Hierarchy Theorem, NP is strictly in NEXP.


2

EDIT: changed a few things to make this work with the new constraint, also rewrote the whole proof to add details and clarity. The following is a reduction of minimum vertex cover to your problem. Take the graph $(V, E)$ we want to solve minimum vertex cover on. Set $|V_{1}| = |V|^{2} + |V| + |E|$, $|V_{2}| = |E| + |V|$. To every node $x \in V$ there ...


2

Below I show that reordering is not possible in any sense, so a new hardness proof from scratch is needed. It's not even possible to reorder just one side if you don't eliminate redundant cluases. This is because any pair of adjacent (cyclically) variables can be in a clause and that gives you very little freedom, you can only reorder them by a cyclical ...


2

The answer to your question is already contained in Fekete's paper. In Section 3, Fekete shows that the following problem GRID-EMPTY is NP-complete: Problem: GRID-EMPTY Instance: a set $S$ of $n$ grid points in the plane Question: Is there a simple polygon on this vertex set $S$ that does not contain any other grid points on its boundary or in its ...


2

Our FOCS'17 paper on the Short Presburger Arithmetic is an example of a "natural" problem which is NP-c, and uses a constant number $C$ of integers in the input, say $C< 220$. It is different from Manders-Adleman in that the constraints are all inequalities. See Gil Kalai's blog post for some background.


2

In a comment, OP expressed interest in a reduction which generated instances with 3 distinct variables per clause. Here's a simple approach: The reduction is from 1-in-3 SAT with 3 distinct variables per clause: First of all, include all the clauses in the input formula as clauses in the output formula. Second, introduce three new variables $F_1$, $F_2$, ...


2

This question is far from research level. Comparison sorts cannot have better than $O(n\log n)$ worst-case complexity. The proof is easily found in any algorithms textbook. Non-comparison sorts potentially could be faster, but they have a limited domain, e.g. integer arrays.


2

Dominating Set and Independent Dominating Set are NP-hard on paths if there is also in the input a "conflict graph", where an edge in this graph is a pair of vertices which cannot be both in the solution. Cornet, Alexis; Laforest, Christian, Domination problems with no conflicts, Discrete Appl. Math. 244, 78-88 (2018). ZBL1387.05181.


2

A caterpillar is equivalent to a list of integers $n_1,n_2,...,n_m$ (given in unary), in which integer $n_i$ represents a central node $i$ and its $n_i$ neighbours. So your question could be rephrased: "Are there hard problems in which the input is a list of (unary) integers?" Clearly this is cheating, but a list of integers can encode everything (e.g. a ...


1

(1) Note that any instance $G=(V,E)$ of the (NP-complete) Hamiltonian cycle problem can be represented by a bit string $b_1b_2\cdots b_k$: Just write down the $n\times n$ adjacency matrix of $G$ row by row, and merge the rows into one long bit string of length $k=n^2$. (2) Note that you may encode an arbitrary bit string $b_1b_2\cdots b_k$ into a ...


Only top voted, non community-wiki answers of a minimum length are eligible