2026-07-22T04:16:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2326 2024-03-06T10:33:18Z ddc:004 open_access

A Fine-grained Analysis of a Simple Independent Set Algorithm Kneis, Joachim Langer, Alexander Rossmanith, Peter Exact Algorithms Independent Set Computer-aided Proof We present a simple exact algorithm for the \is\ problem with a runtime bounded by $O(\rt^n \poly(n))$. This bound is obtained by, firstly, applying a new branching rule and, secondly, by a distinct, computer-aided case analysis. The new branching rule uses the concept of satellites and has previously only been used in an algorithm for sparse graphs. The computer-aided case analysis allows us to capture the behavior of our algorithm in more detail than in a traditional analysis. The main purpose of this paper is to demonstrate how a very simple algorithm can outperform more complicated ones if the right analysis of its running time is performed. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joachim Kneis and Alexander Langer and Peter Rossmanith 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2326 urn:nbn:de:0030-drops-23269 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2326 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode