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

CC BY-SA 4.0
2019-11-18T14:26:10.820Z
Nice example! I wonder if there is an example the other way around: P1 is NP-hard, while P2 is solvable in polynomial time.
Andras Farago
CC BY-SA 4.0
2019-11-19T00:14:30.193Z
@MarioCarneiro oops, I misread the answer. misleading comment deleted.
Gregory J. Puleo
CC BY-SA 4.0
2019-11-18T10:51:42.983Z
2019-11-18T10:51:42.983Z
Antti Röyskö
<p>Let <span class="math-container">$Q$</span> be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph: </p>

<p><strong>P1.</strong> Find a largest induced subgraph of the input graph with property <span class="math-container">$Q$</span>, or detect if no such subgraph exists. (Largest = maximum number of vertices.)</p>

<p><strong>P2.</strong> Partition the vertices of the input graph, such that the number of partition classes is minimum, and each class induces a subgraph with property <span class="math-container">$Q$</span>, or detect if no such partition exists.</p>

<p>Several choices of <span class="math-container">$Q$</span> lead to classical problems, for example:</p>

<ul>
<li><p><span class="math-container">$Q(G)$</span>="<span class="math-container">$G$</span> is an independent set." Then <strong>P1</strong> is the max independent set problem, <strong>P2</strong> is minimum coloring. Both are NP-hard.</p></li>
<li><p><span class="math-container">$Q(G)$</span>="<span class="math-container">$G$</span> is a clique." Then <strong>P1</strong> is the max clique problem, <strong>P2</strong> is minimum clique cover. Both are NP-hard.</p></li>
<li><p><span class="math-container">$Q(G)$</span>="<span class="math-container">$G$</span> is Hamiltonian." Then <strong>P1</strong> looks for a largest circle, <strong>P2</strong> looks for a minimum partition into Hamiltonian subgraphs. Both are NP-hard.</p></li>
<li><p><span class="math-container">$Q(G)$</span>="<span class="math-container">$G$</span> is connected." Then <strong>P1</strong> looks for the largest connected component, while <strong>P2</strong> looks for the number of connected components. Both are solvable in polynomial time.</p></li>
<li><p><span class="math-container">$Q(G)$</span>="<span class="math-container">$G$</span> has a perfect matching." Then <strong>P1</strong> 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 <strong>P2</strong> 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.</p></li>
</ul>

<p><strong>Question:</strong> is there any (preferably natural) choice for the property <span class="math-container">$Q$</span>, which makes <strong>one</strong> of the problems <strong>P1,P2</strong> NP-hard, while the other is solvable in polynomial time? </p>

CC BY-SA 4.0
2019-11-18T21:27:32.133Z
There is linear/integer programming duality going on in this question, but I don't know the details off the top of my head.
Alexander Woo
<graph-algorithms><np-hardness><np-complete>
Relationship between two graph optimization problems
Andras Farago
# Relationship between two graph optimization problems

(Asked by: username_0 on 2019-11-18)

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?

**Tags:** graph-algorithms, np-hardness, np-complete

> **Comments:**
> **username_1**: There is linear/integer programming duality going on in this question, but I don't know the details off the top of my head.  

---

## 1 answers

### Answer by username_2 on 2019-11-18. Score: 17 | Accepted answer

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.

> **Comments:**
> **username_0**: Nice example! I wonder if there is an example the other way around: P1 is NP-hard, while P2 is solvable in polynomial time.  
> **username_3**: @MarioCarneiro oops, I misread the answer. misleading comment deleted.  

---

