Abstract
For a fixed pattern graph H, let H-CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. We continue a line of research that was started in 1987 by Brouwer & Veldman, and we determine the computational complexity of H-CONTRACTIBILITY for certain classes of pattern graphs. In particular, we pin-point the complexity for all graphs H with five vertices.
Interestingly, in all cases that are known to be polynomially solvable, the pattern graph H has a dominating vertex, whereas in all cases that are known to be NP-complete, the pattern graph H does not have a dominating vertex.
| Original language | English |
|---|---|
| Title of host publication | Graph-Theoretic Concepts in Computer Science |
| Subtitle of host publication | 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers |
| Editors | H.L. Bodlaender |
| Publisher | Springer |
| Pages | 322-333 |
| ISBN (Electronic) | 978-3-540-39890-5 |
| ISBN (Print) | 978-3-540-20452-7 |
| DOIs | |
| Publication status | Published - 2003 |
| Event | 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2003 - Elspeet, Netherlands Duration: 19 Jun 2003 → 21 Jun 2003 Conference number: 29 |
Publication series
| Name | Lecture notes in computer science |
|---|---|
| Volume | 2880 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Workshop
| Workshop | 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2003 |
|---|---|
| Abbreviated title | WG |
| Country/Territory | Netherlands |
| City | Elspeet |
| Period | 19/06/03 → 21/06/03 |
Keywords
- METIS-213362