Input: a set of n-1 distances a_1, a_2,...,a_{n-1} with n>a_i>0
Question: does there exist a permutation \pi_1,...,\pi_n of the intergers [1,n] such that |\pi_{i+1}-\pi_{i}|=a_i, i=1,...,n-1?
For example, given the distances a_1=2, a_2=3, a_4=2, there is a permutation \pi_1=3, \pi_2=1, \pi_3=4, \pi_4=2 of the
set {1,2,3,4} with |\pi_2-pi_1\|=a_1, |\pi_3-\pi_2|=a_2 and |\pi_4-\pi_3|=a_3.
The problem is NP-hard.
References: Permutation Reconstruction from Differences
Input: A graph G=(V, E) and an integer k>0.
Question: Does there exist a set $S\subseteq V$ such that
(1) |V|<=k; and
(2) for every X\subseteq S, |N[X]\cap S|>=|N[X]\setminus S|?
This problem is \sum_2^P-hard
References: Complexity of Secure Setes
Input: A triangle-free planar graph G=(V, E) with maximum degree 4.
Question: Is there a partition (V_1, V_2) of V such that both G[V_1] and G[V_2] are of graphs with maximum degree 1?
The problem is NP-hard.
J. Gimbel and C. Hartman. Subcolorings and the subchromatic number of a graph, Discrete Math. 272 (2003), 139–154.