The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems

If Ir IS a property on graphs (or digraphs), the corresponding maximum subgraph problem is Given a graph G find a maximum (induced) subgraph of G satisfying property ~r The author has previously shown this problem to be NP-hard for a large class of properties (the class of properties that are hereditary on induced subgraphs) The effect of adding a connectwtty requirement to ~r is now considered It is shown that for the same class of properties the connected maximum subgraph problem is also NP-hard, moreover, for a certain important subclass of properties, even approximating the node-deletion version of it in any "reasonable" way is NP-hard A related set of problems is shown to testify to A~ # NP LI co-NP, In the case that NP # co-NP.