Exploring the gap between treedepth and vertex cover through vertex integrity

Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)

Abstract

For problems intractable on graphs of bounded treewidth, two graph parameters treedepth and vertex cover number have been used to obtain fine-grained algorithmic and complexity results. Although the studies in this direction are successful, we still need a systematic way for further investigations because the graphs of bounded vertex cover number form a rather small subclass of graphs of bounded treedepth. To fill this gap, we use another graph parameter, vertex integrity, which is placed between the two parameters mentioned above. For several graph problems, we generalize fixed-parameter tractability results parameterized by vertex cover number to the ones parameterized by vertex integrity. We also show some finer complexity contrasts by showing hardness with respect to vertex integrity or treedepth.

Original languageEnglish
Pages (from-to)60-76
Number of pages17
JournalTheoretical Computer Science
Volume918
DOIs
Publication statusPublished - May 29 2022
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Exploring the gap between treedepth and vertex cover through vertex integrity'. Together they form a unique fingerprint.

Cite this