Academic
Publications
Parameterized Complexity of Finding Regular Induced Subgraphs

Parameterized Complexity of Finding Regular Induced Subgraphs,Hannes Moser,Dimitrios M. Thilikos

Parameterized Complexity of Finding Regular Induced Subgraphs   (Citations: 9)
BibTex | RIS | RefWorks Download
The r-Regular Induced Subgraph problem asks, given a graph G and a non- negative integer k, whether G contains an r-regular induced subgraph of size at least k, that is, an induced subgraph in which every vertex has degree exactly r. In this paper we examine its parameterization k-Size r-Regular Induced Sub- graph with k as parameter and prove that it is W(1)-hard. We also examine the pa- rameterized complexity of the dual parameterized problem, namely, the k-Almost r-Regular Graph problem, which asks for a given graph G and a non-negative integer k whether G can be made r-regular by deleting at most k vertices. For this problem, we prove the existence of a problem kernel of size O(kr(r + k)2).
Conference: Algorithms and Complexity in Durham - ACID , pp. 107-118, 2006
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: