Amiri, Saeed Akhoondian (2021). A note on the fine-grained complexity of MIS on regular graphs. Inf. Process. Lett., 170. AMSTERDAM: ELSEVIER. ISSN 1872-6119

Full text not available from this repository.

Abstract

We show that there is no subexponential time algorithm for computing the exact solution of the maximum independent set problem in d-regular graphs, unless ETH fails. We expand our method to show that it helps to provide lowerbounds for other covering problems such as vertex cover and clique. We utilize the construction to show the NP-hardness of MIS on 5-regular planar graphs, closing the exact complexity status of the problem on regular planar graphs. (C) 2021 Elsevier B.V. All rights reserved.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Amiri, Saeed AkhoondianUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-567159
DOI: 10.1016/j.ipl.2021.106123
Journal or Publication Title: Inf. Process. Lett.
Volume: 170
Date: 2021
Publisher: ELSEVIER
Place of Publication: AMSTERDAM
ISSN: 1872-6119
Language: English
Faculty: Unspecified
Divisions: Unspecified
Subjects: no entry
Uncontrolled Keywords:
KeywordsLanguage
MAXIMUM INDEPENDENT SET; P-T-FREE; TIME ALGORITHMMultiple languages
Computer Science, Information SystemsMultiple languages
URI: http://kups.ub.uni-koeln.de/id/eprint/56715

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item