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 input graph with property $Q$, or detect if no such subgraph exists. (Largest = maximum number of vertices.)
P2. Partition the vertices of the input graph, such that the number of partition classes is minimum, and each class induces a subgraph with property $Q$, or detect if no such partition exists.
Several choices of $Q$ lead to classical problems, for example:
$Q(G)$="$G$ is an independent set." Then P1 is the max independent set problem, P2 is minimum coloring. Both are NP-hard.
$Q(G)$="$G$ is a clique." Then P1 is the max clique problem, P2 is minimum clique cover. Both are NP-hard.
$Q(G)$="$G$ is Hamiltonian." Then P1 looks for a largest circle, P2 looks for a minimum partition into Hamiltonian subgraphs. Both are NP-hard.
$Q(G)$="$G$ is connected." Then P1 looks for the largest connected component, while P2 looks for the number of connected components. Both are solvable in polynomial time.
$Q(G)$="$G$ has a perfect matching." Then P1 looks for a maximum matching, if the input graph has at least one edge, otherwise there is no subgraph with the property. The solution for P2 is the trivial partition with one class if the input graph has a perfect matching, or otherwise there is no feasible partition. Both cases are solvable in polynomial time.
Question: is there any (preferably natural) choice for the property $Q$, which makes one of the problems P1,P2 NP-hard, while the other is solvable in polynomial time?
