Parameterized orientable deletion

DOI10.1007/s00453-020-00679-6zbMath1441.68186arXiv1807.11518MaRDI QIDQ2182093

Yota Otachi, Michael Lampis, Florian Sikora, Tesshu Hanaka, Ioannis Katsikarelis

Publication date: 21 May 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.11518

zbMATH Keywords

treewidth; orientation; parameterization; SETH

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

05C20: Directed graphs (digraphs), tournaments

68Q27: Parameterized complexity, tractability and kernelization