On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

DOI10.1145/3470869zbMath1495.68178arXiv2006.10364OpenAlexW3196689725MaRDI QIDQ5066147

Pallavi Jain, Spoorthy Gunda, Prafullkumar Tale, Saket Saurabh, Daniel Lokshtanov

Publication date: 29 March 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

inapproximabilitygraph contractionlossy kernelsFPT-approximation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Graph operations (line graphs, products, etc.) (05C76) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

On the parameterized complexity of maximum degree contraction problem ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms

This page was built for publication: On the Parameterized Approximability of Contraction to Classes of Chordal Graphs