A note on the complexity of finding regular subgraphs
type: Item
instance of: scholarly article
title: A note on the complexity of finding regular subgraphs
zbMATH Open document ID: 0567.05029
DOI: 10.1016/0012-365X(84)90113-4
author: Ján Plesník
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: This is an interesting investigation on the algorithmic difficulty of detecting regular subgraphs in a given graph. The author proves a general theorem which states that, for a given graph G and an integer \(r\geq 3\), the problem of deciding the existence of an r-regular subgraph of G is NP-complete. NP-completeness is proved by polynomial reduction of the known NP-complete problem ''exact cover by 3-sets'' to the new problem. Stronger results are then presented; these show that the r-regular subgraph problem remains NP-complete even when G is a bipartite or planar graph with given characteristics.
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3904617
zbMATH Keywords: detecting regular subgraphs in a given graph
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
cites work: Q4187840
cites work: Q5422499
cites work: Three‐regular subgraphs of four‐regular graphs
cites work: Q4198056
cites work: Parallel concepts in graph theory
cites work: Q4142699
cites work: On a problem of K. Zarankiewicz
cites work: Q3929767
cites work: On the berge—sauer conjecture
cites work: Q4750685
Recommended article: Q4865472
Recommended article: The complexity of regular subgraph recognition
Recommended article: Parameterized complexity of finding regular induced subgraphs
Recommended article: On the complexity of some subgraph problems
Recommended article: Note on regular subgraphs
Recommended article: Q3688439
Recommended article: Finding regular subgraphs in both arbitrary and planar graphs
Recommended article: Addendum to: The complexity of regular subgraph recognition
Recommended article: Complexity of finding maximum regular induced subgraphs with prescribed degree
Recommended article: Complexity of Finding Maximum Regular Induced Subgraphs with Prescribed Degree
description: scientific article; zbMATH DE number 3904617