12
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Feb 28, 2014 at 1:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – Andras Farago
    Commented Feb 28, 2014 at 15:47

3 Answers 3

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Similarly, vertex cover / dominating set of size at most $k$ work similarly. $\endgroup$
    – R B
    Commented Feb 28, 2014 at 16:49
  • $\begingroup$ 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. $\endgroup$
    – Vinicius dos Santos
    Commented Feb 28, 2014 at 17:40
  • $\begingroup$ 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$. $\endgroup$
    – Andras Farago
    Commented Feb 28, 2014 at 20:21
  • 4
    $\begingroup$ 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$". $\endgroup$
    – Vinicius dos Santos
    Commented Mar 1, 2014 at 0:57
  • 1
    $\begingroup$ 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). $\endgroup$
    – Andras Farago
    Commented Mar 3, 2014 at 19:28
1
$\begingroup$

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.

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andras Farago
    Commented Mar 2, 2014 at 4:17
1
$\begingroup$

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).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andras Farago
    Commented Mar 2, 2014 at 3:48
  • $\begingroup$ 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. $\endgroup$
    – Super8
    Commented Mar 2, 2014 at 11:28
  • $\begingroup$ 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. $\endgroup$
    – Andras Farago
    Commented Mar 3, 2014 at 18:59

Your Answer

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

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