Complexity of finding maximum regular induced subgraphs with prescribed degree We study the problem of finding a maximum vertexsubset S of a given graph G such that the subgraph GS induced by S is rregular for a prescribed degree ru003e0. We also consider a variant of the problem which requires GS to be rregular and connected. Both problems are known to be NPhard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NPhard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having treelike structures, as follows. We give lineartime algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs.

Subgraph isomorphism on graph classes that exclude a substructure We study Subgraph Isomorphism on graph classes defined by a fixed forbidden graph. Although there are several ways for forbidding a graph, we observe that it is reasonable to focus on the minor relation since other wellknown relations lead to either trivial or equivalent problems. When the forbidden minor is connected, we present a near dichotomy of the complexity of Subgraph Isomorphism with respect to the forbidden minor, where the only unsettled case is the path of five vertices. We then also consider the general case of possibly disconnected forbidden minors. We show in particular that: the problem is fixedparameter tractable parameterized by the size of the forbidden minor H when H is a linear forest such that at most one component has four vertices and all other components have three or less vertices; and it is NPcomplete if H contains four or more components with at least five vertices each. As a byproduct, we show that Subgraph Isomorphism is fixedparameter tractable parameterized by vertex integrity. Using similar techniques, we also observe that Subgraph Isomorphism is fixedparameter tractable parameterized by neighborhood diversity.