10
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ There is linear/integer programming duality going on in this question, but I don't know the details off the top of my head. $\endgroup$
    – Alexander Woo
    Nov 18, 2019 at 21:27

1 Answer 1

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Nice example! I wonder if there is an example the other way around: P1 is NP-hard, while P2 is solvable in polynomial time. $\endgroup$
    – Andras Farago
    Nov 18, 2019 at 14:26
  • $\begingroup$ @MarioCarneiro oops, I misread the answer. misleading comment deleted. $\endgroup$
    – Gregory J. Puleo
    Nov 19, 2019 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.