Deciding whether a grid is a topological subgraph of a planar graph is NP-complete

Link:
Autor/in:
Verlag/Körperschaft:
Hamburg University of Technology
Erscheinungsjahr:
2020
Medientyp:
Text
Schlagworte:
  • Grids
  • NP-complete
  • Planar graph
  • Subdivision
  • Subgraph homeomorphism
  • Topological subgraph
Beschreibung:
  • PROBLEM is to decide, for two given graphs G and H, whether H is a topological subgraph of G. It is known that the TSC PROBLEM is NP-complete when H is part of the input, that it can be solved in polynomial time when H is fixed, and that it is fixed-parameter tractable by the order of H. Motivated by the great significance of grids in graph theory and algorithms due to the Grid-Minor Theorem by Robertson and Seymour, we investigate the computational complexity of the GRID TSC PROBLEM in planar graphs. More precisely, we study the following decision problem: given a positive integer k and a planar graph G, is the k×k grid a topological subgraph of G? We prove that this problem is NP-complete, even when restricted to planar graphs of maximum degree six, via a novel reduction from the PLANAR MONOTONE 3-SAT PROBLEM.
Beziehungen:
DOI 10.1016/j.disc.2020.111952
Quellsystem:
TUHH Open Research

Interne Metadaten
Quelldatensatz
oai:tore.tuhh.de:11420/6174