<p>I think the $k$-clique cover problem, which asks whether there exists a partition of the vertices in $k$ sets such that each set induces a clique, has the desired properties.</p>

<p>Clearly, taking induced subgraphs can't make the minimum size of such partition increase. On the other hand, when you take the disjoint union of two graphs, you have to take the union of the partition into cliques of each one.</p>

CC BY-SA 3.0
2014-02-28T16:49:37.363Z
Similarly, vertex cover / dominating set of size at most $k$ work similarly.
R B
CC BY-SA 3.0
2014-02-28T17:40:22.593Z
But both problems you mentioned are polynomial for fixed $k$, right? I think if you force $k$ to be part of the input, then it stops being a well defined property in the sense the question asked.
Vinicius dos Santos
CC BY-SA 3.0
2014-02-28T20:21:34.417Z
The $k$-clique cover property, as stated in the answer, is not $hereditary$. A graph may have a $k$-partition into cliques, but a subgraph of it may not inherit this property. This remains true both for constant and variable $k$.
Andras Farago
CC BY-SA 3.0
2014-02-28T23:13:35.190Z
Could you show me an example? I can't see where the problem is.
Vinicius dos Santos
CC BY-SA 3.0
2014-03-01T00:12:13.967Z
Here is a very simple example: a triangle can be partitioned into 3 cliques (each is a single vertex). If, however, we remove a vertex, the remaining graph cannot partitioned anymore into 3 cliques, as it only has 2 vertices. So, the property is not hereditary.
Andras Farago
CC BY-SA 3.0
2014-03-01T00:57:54.463Z
This can be easily solved allowing empty partitions (if the original problem doesn't allow it, just consider this modified version).  Instead of "clique cover of size $k$" consider "of size at most $k$".
Vinicius dos Santos
CC BY-SA 3.0
2014-03-03T19:28:04.173Z
Yes, I think, with this modification it is now a correct answer! If we fix $k=3$, then the property is equivalent to "is the complement of G 3-colorable?" (meaning that the complement is colorable by at most 3 colors). This is hereditary, and is indeed NP-complete, by the known NP-completeness of graph 3-colorability. The property is also non-additive, because if $G_1$ and $G_2$ both individually have their complements 3-colorable, still the complement of their disjoint union may not remain 3-colorable (it may require as many as 6 colors).
Andras Farago
CC BY-SA 3.0
2014-02-28T01:23:09.590Z
2014-02-28T01:23:09.590Z
Vinicius dos Santos
<p>Consider this problem </p>

<blockquote>
  <p>Given a graph $G$ deciding whether its vertex set can be partitioned
  into two disjoint sets such that the induced graphs created by the
  sewts exhibits property $P$ and $Q$, is <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r46" rel="nofollow">NP- complete</a>.</p>
</blockquote>

<p>It remains NP complete even if the properties are hereditary.</p>

<p>Now clearly a solution of the above problem for a graph also provides solution for the induced subgraphs. But upon taking union of graphs of same family as G might not be solved using that solution.</p>

<p>For example partitioning general graphs in disjoint unit interval graphs is NP complete but upon taking union of all possible edges (making the graph complete) solves the problem trivially.</p>

CC BY-SA 3.0
2014-03-02T04:17:53.900Z
Please note that the question looks for a property that is not additive. In your example nothing seems to guarantee that there must exist two graphs which both have the property, but their _disjoint_ union does not.
Andras Farago
CC BY-SA 3.0
2014-03-01T13:04:03.190Z
2014-03-01T13:04:03.190Z
Dibyayan
<p>Define the cycle cover number of a graph $G = (V,E)$ as the minimum number of cycles $C_1,\ldots,C_m$ such that (i) each $C_i$ is a cycle graph over a subset of $V$, (ii) each edge of $E$ is present in some $C_i$. I conjecture the following:</p>

<p>(1) for $k \geq 3$, it is NP-complete to decide if $G$ has cycle cover number at most $k$,</p>

<p>(2) for $k = 2$, the problem is polynomial -- this should follow from "Gauss Codes, Planar Hamiltonian Graphs, and Stack-Sortable Permutations" by Rosenstiehl and Tarjan.</p>

<p>If (1) is true then it should answer your question, as it gives a property that is hereditary, but clearly not additive.</p>

<p>(NOTE ADDED: conjecture (2) is different from the "double cycle cover conjecture" by Szekeres and Seymour, despite the homonymity).</p>

CC BY-SA 3.0
2014-03-02T03:48:18.640Z
This property is not hereditary. The removal of a vertex may increase the needed number of cycles to cover all edges, because the removed vertex may eliminate a cycle that was used to cover many edges. The simplest example is when the whole graph is just a cycle. The removal of a vertex makes any cycle cover impossible, since no cycles are left.
Andras Farago
CC BY-SA 3.0
2014-03-02T11:28:20.767Z
Note that my definition doesn't require that each cycle is a subgraph of $G$, i.e. it may contain extra edges not in $G$. With this definition the property is hereditary: when removing a vertex $v$, you just have to "bypass" $v$ in every cycle containing it to obtain a cycle cover of the resulting graph.
Super8
CC BY-SA 3.0
2014-03-03T18:59:50.350Z
Thank you, it looks interesting. If conjecture (1) is proved for a fixed $k$, then it may indeed yield an NP-complete graph property that is hereditary, but not additive. One has to make sure, however, that the cycles that are used to cover the two graphs in the disjoint union cannot be combined into fewer cycles via adding edges between the two graphs, since adding edges is allowed by your definition.
Andras Farago
CC BY-SA 3.0
2014-03-01T18:35:37.800Z
2014-03-02T12:50:20.283Z
2014-03-02T12:50:20.283Z
Super8
<p>A graph property is called <strong>hereditary</strong> if it closed with respect to deleting vertices (i.e., all induced subgraphs inherit the property). A graph property is called <strong>additive</strong> if it is closed with respect to taking disjoint unions. </p>

<p>It is not hard to find properties that are hereditary, but not additive. Two simple examples: </p>

<p>$\;\;\;$ (1) The graph is complete. </p>

<p>$\;\;\;$ (2) The graph does not contain two vertex-disjoint cycles. </p>

<p>In these cases it is obvious that the property is inherited by induced subgraphs, but taking two <em>disjoint</em> graphs that have the property, their union may not preserve it.</p>

<p>Both of the above examples are polytime decidable properties (although for (2) it is somewhat less trivial). If we want harder properties, they could still be created by following  the pattern of  (2), but replacing the cycles with more complicated graph types. Then, however, we can easily run into the situation where the problem does not even remain in $NP$, under standard complexity assumptions, such as $NP\neq coNP$. It appears less trivial to find an example which stays within $NP$, but it is still hard. </p>

<blockquote>
  <p><strong>Question:</strong> Do you know a (preferably natural)  $NP$-complete graph property that is hereditary, but not additive?</p>
</blockquote>

CC BY-SA 3.0
2014-02-28T01:52:55.973Z
You've asked a number of questions now about "natural" properties. It might be helpful to understand what the motivation for some of these questions is.
Suresh Venkat
CC BY-SA 3.0
2014-02-28T15:47:39.797Z
@Suresh I would like to better understand what makes a problem natural, as opposed to contrived, artificial. I think, the concept of naturalness is an important bridge between theory and reality, and it is worth exploring. What I find intriguing is that even though we do not have any formal definition of which problems are  "natural," people usually have clear consensus about whether a specific problem is natural or not. Perhaps I will post a separate question about this issue, to find out more about how others view it.
Andras Farago
<cc.complexity-theory><graph-theory><graph-algorithms><np>
NP-complete graph property that is hereditary, but not additive?
Andras Farago
# NP-complete graph property that is hereditary, but not additive?

(Asked by: username_0 on 2014-02-27)

A graph property is called **hereditary** if it closed with respect to deleting vertices (i.e., all induced subgraphs inherit the property). A graph property is called **additive** if it is closed with respect to taking disjoint unions.

It is not hard to find properties that are hereditary, but not additive. Two simple examples:

$\;\;\;$ (1) The graph is complete.

$\;\;\;$ (2) The graph does not contain two vertex-disjoint cycles.

In these cases it is obvious that the property is inherited by induced subgraphs, but taking two *disjoint* graphs that have the property, their union may not preserve it.

Both of the above examples are polytime decidable properties (although for (2) it is somewhat less trivial). If we want harder properties, they could still be created by following the pattern of (2), but replacing the cycles with more complicated graph types. Then, however, we can easily run into the situation where the problem does not even remain in $NP$, under standard complexity assumptions, such as $NP\neq coNP$. It appears less trivial to find an example which stays within $NP$, but it is still hard.

> **Question:** Do you know a (preferably natural) $NP$-complete graph property that is hereditary, but not additive?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, np

> **Comments:**
> **username_1**: You've asked a number of questions now about "natural" properties. It might be helpful to understand what the motivation for some of these questions is.  
> **username_0**: @Suresh I would like to better understand what makes a problem natural, as opposed to contrived, artificial. I think, the concept of naturalness is an important bridge between theory and reality, and it is worth exploring. What I find intriguing is that even though we do not have any formal definition of which problems are  "natural," people usually have clear consensus about whether a specific problem is natural or not. Perhaps I will post a separate question about this issue, to find out more about how others view it.  

---

## 3 answers

### Answer by username_2 on 2014-02-28. Score: 9

I think the $k$-clique cover problem, which asks whether there exists a partition of the vertices in $k$ sets such that each set induces a clique, has the desired properties.

Clearly, taking induced subgraphs can't make the minimum size of such partition increase. On the other hand, when you take the disjoint union of two graphs, you have to take the union of the partition into cliques of each one.

> **Comments:**
> **username_3**: Similarly, vertex cover / dominating set of size at most $k$ work similarly.  
> **username_2**: But both problems you mentioned are polynomial for fixed $k$, right? I think if you force $k$ to be part of the input, then it stops being a well defined property in the sense the question asked.  
> **username_0**: The $k$-clique cover property, as stated in the answer, is not $hereditary$. A graph may have a $k$-partition into cliques, but a subgraph of it may not inherit this property. This remains true both for constant and variable $k$.  
> **username_2**: Could you show me an example? I can't see where the problem is.  
> **username_0**: Here is a very simple example: a triangle can be partitioned into 3 cliques (each is a single vertex). If, however, we remove a vertex, the remaining graph cannot partitioned anymore into 3 cliques, as it only has 2 vertices. So, the property is not hereditary.  
> **username_2**: This can be easily solved allowing empty partitions (if the original problem doesn't allow it, just consider this modified version).  Instead of "clique cover of size $k$" consider "of size at most $k$".  
> **username_0**: Yes, I think, with this modification it is now a correct answer! If we fix $k=3$, then the property is equivalent to "is the complement of G 3-colorable?" (meaning that the complement is colorable by at most 3 colors). This is hereditary, and is indeed NP-complete, by the known NP-completeness of graph 3-colorability. The property is also non-additive, because if $G_1$ and $G_2$ both individually have their complements 3-colorable, still the complement of their disjoint union may not remain 3-colorable (it may require as many as 6 colors).  

---

### Answer by username_4 on 2014-03-01. Score: 1

Consider this problem

> Given a graph $G$ deciding whether its vertex set can be partitioned
> into two disjoint sets such that the induced graphs created by the
> sewts exhibits property $P$ and $Q$, is [NP- complete](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r46).

It remains NP complete even if the properties are hereditary.

Now clearly a solution of the above problem for a graph also provides solution for the induced subgraphs. But upon taking union of graphs of same family as G might not be solved using that solution.

For example partitioning general graphs in disjoint unit interval graphs is NP complete but upon taking union of all possible edges (making the graph complete) solves the problem trivially.

> **Comments:**
> **username_0**: Please note that the question looks for a property that is not additive. In your example nothing seems to guarantee that there must exist two graphs which both have the property, but their _disjoint_ union does not.  

---

### Answer by username_5 on 2014-03-01. Score: 1

Define the cycle cover number of a graph $G = (V,E)$ as the minimum number of cycles $C\_1,\ldots,C\_m$ such that (i) each $C\_i$ is a cycle graph over a subset of $V$, (ii) each edge of $E$ is present in some $C\_i$. I conjecture the following:

(1) for $k \geq 3$, it is NP-complete to decide if $G$ has cycle cover number at most $k$,

(2) for $k = 2$, the problem is polynomial -- this should follow from "Gauss Codes, Planar Hamiltonian Graphs, and Stack-Sortable Permutations" by Rosenstiehl and Tarjan.

If (1) is true then it should answer your question, as it gives a property that is hereditary, but clearly not additive.

(NOTE ADDED: conjecture (2) is different from the "double cycle cover conjecture" by Szekeres and Seymour, despite the homonymity).

> **Comments:**
> **username_0**: This property is not hereditary. The removal of a vertex may increase the needed number of cycles to cover all edges, because the removed vertex may eliminate a cycle that was used to cover many edges. The simplest example is when the whole graph is just a cycle. The removal of a vertex makes any cycle cover impossible, since no cycles are left.  
> **username_5**: Note that my definition doesn't require that each cycle is a subgraph of $G$, i.e. it may contain extra edges not in $G$. With this definition the property is hereditary: when removing a vertex $v$, you just have to "bypass" $v$ in every cycle containing it to obtain a cycle cover of the resulting graph.  
> **username_0**: Thank you, it looks interesting. If conjecture (1) is proved for a fixed $k$, then it may indeed yield an NP-complete graph property that is hereditary, but not additive. One has to make sure, however, that the cycles that are used to cover the two graphs in the disjoint union cannot be combined into fewer cycles via adding edges between the two graphs, since adding edges is allowed by your definition.  

---

