# Tag Info

9

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

The state-of-the-art for PCPs that yield a reduction to $(\frac{7}{8}+\varepsilon)$ 3-SAT (even for sub-constant $\varepsilon$) are those of Dana Moshkovitz and Ran Raz, which have length $n^{1 + o(1)}$. I do not know, however, if anyone tried to compute the exact dependence of the length on $\varepsilon$, or the computation complexity of the reduction. ...

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

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^{... 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/\...

4

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 ...

4

Ken Supowit proved that the following problem is NP-hard: Given a set $P$ of $n$ points in the Euclidean plane and an integer $k$, partition $P$ into $k$ clusters so that the largest cluster diameter is minimized. Kenneth J Supowit: "Topics in Computational Geometry" Ph.D. thesis, Dept. of Computer Science, University of Illinois at Urbana-Champaign (...

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

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

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 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-... 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 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 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 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 The algorithm previously proposed in the post (before the current edit), does not work. Here are the problem and algorithm proposed in that version of the post: input: graph$G=(V,E)$and the minimum size$k$of any dominating set in$G$output: a set of$k$nodes that dominates a dominating set of size$k$algorithm$(G,k)$: At the start, all ... 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 ... 1 It's hard for$k\ge 2$by a reduction from Partition. Let's first look at$k = 3$. Suppose that the input to Partition is the numbers$x_1, \ldots, x_n$, and their sum is$S$. For each$i$create a vector$v_i$whose first coordinate is$x_i$, second coordinate is$-x_i$, and the third coordinate is$0$. Add another vector$v_{n+1}$with first coordinate$0$,... 1 The best-known algorithm for vertex cover in (general) graphs runs in time$O(1.2114^n)$by Bourgeois, Escoffier, Paschos and van Rooij. You may read their paper and see whether their algorithm can be improved for cubic graphs. Bourgeois, N., Escoffier, B., Paschos, V. T., & van Rooij, J. M. (2012). Fast algorithms for max independent set. Algorithmica, ... 1 I followed the link in the question, and the reduction there actually produces graphs whose edges have a natural coloring such that each$K_n$present in the graph is a "rainbow$K_n\$" (has exactly one edge of each color). In other words, we can easily adjust the reduction in that paper so that it reduces to your problem instead of reducing to the partition ...

1

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

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