CINXE.COM
Parameterized and Counting Algorithms and Complexity - Max Planck Institute for Informatics
<!DOCTYPE html> <html lang="en-US"> <head> <meta charset="utf-8"> <!-- This website is powered by TYPO3 - inspiring people to share! TYPO3 is a free open source Content Management Framework initially created by Kasper Skaarhoj and licensed under GNU/GPL. TYPO3 is copyright 1998-2024 of Kasper Skaarhoj. Extensions are copyright of their respective owners. Information and contribution at https://typo3.org/ --> <base href="https://www.mpi-inf.mpg.de/"> <link rel="icon" href="/typo3conf/ext/mpi_inf_site_package/Resources/Public/favicon.ico" type="image/vnd.microsoft.icon"> <title>Parameterized and Counting Algorithms and Complexity - Max Planck Institute for Informatics</title> <meta http-equiv="x-ua-compatible" content="IE=edge" /> <meta name="generator" content="TYPO3 CMS" /> <meta name="viewport" content="width=device-width, initial-scale=1, minimum-scale=1" /> <meta name="robots" content="index,follow" /> <meta name="twitter:card" content="summary" /> <meta name="apple-mobile-web-app-capable" content="no" /> <link rel="stylesheet" href="/typo3temp/assets/css/477c5e4dcc714b3ff0da8403884a460e.css?1697447411" media="all"> <link rel="stylesheet" href="/typo3conf/ext/mpi_inf_site_package/Resources/Public/Css/swiper-bundle-8.4.6.min.css?1725541122" media="screen"> <link rel="stylesheet" href="/typo3conf/ext/mpi_inf_site_package/Resources/Public/Css/style.css?1725541122" media="all"> <script src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/JavaScript/Build/head.js?1725541122"></script> <style>.page-141 .news__categories { display: none !important; }</style> <link rel="canonical" href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/research/parameterized-algorithms-and-complexity"/> </head> <body id="p4201" class="page page-4201 page-lvl--4 lang--0 be-layout--sidebar layout--default dep--d1"><a name="top"></a> <div class="skip-link"> Skip to <a href="#main">main content</a> or <a href="#nav">main navigation</a> </div> <style> .department-lnk--d1 .department-lnk__icon { background: #a50d0f; } .department-lnk--d1.active, .department-lnk--d1:active, .department-lnk--d1:hover { background: #a50d0f; } .department-lnk--d1.active .department-lnk__id, .department-lnk--d1:active .department-lnk__id, .department-lnk--d1:hover .department-lnk__id { color: #a50d0f; } </style> <style> .department-lnk--d2 .department-lnk__icon { background: #db6413; } .department-lnk--d2.active, .department-lnk--d2:active, .department-lnk--d2:hover { background: #db6413; } .department-lnk--d2.active .department-lnk__id, .department-lnk--d2:active .department-lnk__id, .department-lnk--d2:hover .department-lnk__id { color: #db6413; } </style> <style> .department-lnk--d3 .department-lnk__icon { background: #758e25; } .department-lnk--d3.active, .department-lnk--d3:active, .department-lnk--d3:hover { background: #758e25; } .department-lnk--d3.active .department-lnk__id, .department-lnk--d3:active .department-lnk__id, .department-lnk--d3:hover .department-lnk__id { color: #758e25; } </style> <style> .department-lnk--d4 .department-lnk__icon { background: #0d82a1; } .department-lnk--d4.active, .department-lnk--d4:active, .department-lnk--d4:hover { background: #0d82a1; } .department-lnk--d4.active .department-lnk__id, .department-lnk--d4:active .department-lnk__id, .department-lnk--d4:hover .department-lnk__id { color: #0d82a1; } </style> <style> .department-lnk--d5 .department-lnk__icon { background: #87136e; } .department-lnk--d5.active, .department-lnk--d5:active, .department-lnk--d5:hover { background: #87136e; } .department-lnk--d5.active .department-lnk__id, .department-lnk--d5:active .department-lnk__id, .department-lnk--d5:hover .department-lnk__id { color: #87136e; } </style> <style> .department-lnk--d6 .department-lnk__icon { background: #03325d; } .department-lnk--d6.active, .department-lnk--d6:active, .department-lnk--d6:hover { background: #03325d; } .department-lnk--d6.active .department-lnk__id, .department-lnk--d6:active .department-lnk__id, .department-lnk--d6:hover .department-lnk__id { color: #03325d; } </style> <style> .department-lnk--rg1 .department-lnk__icon { background: #f0b006; } .department-lnk--rg1.active, .department-lnk--rg1:active, .department-lnk--rg1:hover { background: #f0b006; } .department-lnk--rg1.active .department-lnk__id, .department-lnk--rg1:active .department-lnk__id, .department-lnk--rg1:hover .department-lnk__id { color: #f0b006; } </style> <style> .department-lnk--rg2 .department-lnk__icon { background: #d7390b; } .department-lnk--rg2.active, .department-lnk--rg2:active, .department-lnk--rg2:hover { background: #d7390b; } .department-lnk--rg2.active .department-lnk__id, .department-lnk--rg2:active .department-lnk__id, .department-lnk--rg2:hover .department-lnk__id { color: #d7390b; } </style> <style> .department-lnk--rg3 .department-lnk__icon { background: #5aa1a8; } .department-lnk--rg3.active, .department-lnk--rg3:active, .department-lnk--rg3:hover { background: #5aa1a8; } .department-lnk--rg3.active .department-lnk__id, .department-lnk--rg3:active .department-lnk__id, .department-lnk--rg3:hover .department-lnk__id { color: #5aa1a8; } </style> <nav class="site__department-nav department-dd js-site-department-nav " title=""> <a class="department-dd__toggle js-site-department-dd-toggle" role="button" title="" href="javascript:"> <i class="mpg-icon mpg-icon-down2"></i> </a> <ul class="department-dd__menu"> <li> <a class="department-lnk department-lnk--home js-department-dd-lnk" href="/home"> <span class="department-lnk__ct"> <span class="department-lnk__icon"> <i class="mpg-icon mpg-icon-home"></i> </span> <span class="department-lnk__lbl"> Institute </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d1 active " href="/departments/algorithms-complexity" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D1 </span> </span> <span class="department-lnk__lbl"> Algorithms and Complexity </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d2 " href="/departments/computer-vision-and-machine-learning" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D2 </span> </span> <span class="department-lnk__lbl"> Computer Vision and Machine Learning </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d3 " href="/departments/inet" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D3 </span> </span> <span class="department-lnk__lbl"> Internet Architecture </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d4 " href="/departments/computer-graphics" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D4 </span> </span> <span class="department-lnk__lbl"> Computer Graphics </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d5 " href="/departments/databases-and-information-systems" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D5 </span> </span> <span class="department-lnk__lbl"> Databases and Information Systems </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d6 " href="/departments/visual-computing-and-artificial-intelligence" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D6 </span> </span> <span class="department-lnk__lbl"> Visual Computing and Artificial Intelligence </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--rg1 " href="/departments/automation-of-logic" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> RG1 </span> </span> <span class="department-lnk__lbl"> Automation of Logic </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--rg2 " href="/departments/network-and-cloud-systems" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> RG2 </span> </span> <span class="department-lnk__lbl"> Network and Cloud Systems </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--rg3 " href="/departments/mlp" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> RG3 </span> </span> <span class="department-lnk__lbl"> Multimodal Language Processing </span> </span> </a> </li> </ul> <div class="department-dd__close-ct"> <a class="department-dd__close js-site-department-nav-close-lnk" role="button" title="" href="javascript:"> <svg width="12px" height="12px" viewBox="0 0 12 12" stroke="white" stroke-width="1"> <line x1="1" y1="1" x2="11" y2="11"></line> <line x1="1" y1="11" x2="11" y2="1"></line> </svg> </a> </div> </nav> <header class="site-header"> <div class="site-header__ct"> <div class="site-header__mob-ct"> <div class="site-header__logo-lnk-ct"> <a class="site-header__logo-lnk" href="/home"> <img class="site-header__logo" alt="Logo Max Planck Institute for Informatics" src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/Images/Core/mpi-logo-en.svg" width="1527" height="300" /> </a> <a class="site-header__department-lnk" href="/departments/algorithms-complexity"> <span class="site-header__department-lbl"> Algorithms and Complexity </span> </a> </div> <button class="site-header__nav-toggle js-toggle-mobile-nav" type="button" aria-label="Toggle navigation" > <svg width="40" height="40" viewBox="-25 -25 50 50"> <circle cx="0" cy="0" r="25" fill="none"></circle> <rect class="burgerline-1" x="-15" y="-12" width="30" height="4" fill="black"></rect> <rect class="burgerline-2" x="-15" y="-2" width="30" height="4" fill="black"></rect> <rect class="burgerline-3" x="-15" y="8" width="30" height="4" fill="black"></rect> </svg> </button> </div> <div class="site-header__mob-nav-ct js-mob-nav-ct"> <div class="site-header__mob-nav-ct-helper js-mob-nav-helper"> <div class="site-header__search"> <div class="tx-solr"> <div class="tx-solr-search-form"> <form method="get" id="tx-solr-search-form-pi-results" action="/search" data-suggest="/search?type=7384" data-suggest-header="Top Results" accept-charset="utf-8"> <input class="tx-solr-search-form__input js-solr-q" name="tx_solr[q]" placeholder="Search" value="" type="search" aria-label="Search" /> <button class="tx-solr-search-form__submit" aria-label="Search" type="submit"> <i class="mpg-icon mpg-icon-search" role="img" aria-hidden="true"></i> </button> </form> </div> </div> </div> <div class="site-header__main-nav"> <nav class="main-nav" id="nav"> <div class="main-nav__ct"> <ul class="main-nav__items"> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/people/current-members" target="" > People </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/people/current-members" target="" > Current Members </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/people/former-members" target="" > Former Members </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item has-children"> <a class="active has-children" href="/departments/algorithms-complexity/research" target="" > Research </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/algorithmic-game-theory" target="" > Algorithmic Game Theory </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/approximation-algorithms" target="" > Approximation Algorithms </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/fine-grained-complexity" target="" > Fine-Grained Complexity and Algorithm Design </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/graph-algorithms" target="" > Graph Algorithms </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/optimization" target="" > Optimization </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk active" href="/departments/algorithms-complexity/research/parameterized-algorithms-and-complexity" target="" > Parameterized and Counting Algorithms and Complexity </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/robust-learning" target="" > Robust Learning </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/offers" target="" > Offers </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/offers/postdoc" target="" > Postdoc Application </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/teaching" target="" > Teaching </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter-2024/25" target="" > Winter 2024/25 </a> <ul class="sub-menu sub-menu--lvl-2"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.sic.saarland/gralgodat24/" target="" > Introduction to Algorithms and Data Structures </a> </li> </ul> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer24" target="" > Summer 2024 </a> <ul class="sub-menu sub-menu--lvl-2"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.sic.saarland/finegrained24/" target="" > Fine-Grained Complexity Theory </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer24/fair-div-game-theory" target="" > Topics in Computational Social Choice Theory </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer24/discrete-optimization" target="" > Discrete Optimization </a> </li> </ul> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter23" target="" > Winter 2023/24 </a> <ul class="sub-menu sub-menu--lvl-2"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.sic.saarland/algodat23/" target="" > Algorithms and Data Structures </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.sic.saarland/sublinear23/" target="" > Sublinear Algorithms </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.sic.saarland/ideen2324/" target="" > Ideen und Konzepte der Informatik </a> </li> </ul> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer23" target="" > Summer 2023 </a> <ul class="sub-menu sub-menu--lvl-2"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer23/counting" target="" > Techniques for Counting Problems </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.cispa.saarland/paramalg_23/" target="" > Parametrized Algorithms (external) </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer23/ml-foundations" target="" > Seminar: Foundations of Machine Learning </a> </li> </ul> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter22" target="" > Winter 2022/23 </a> <ul class="sub-menu sub-menu--lvl-2"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter22/random" target="" > Randomized Algorithms and Probabilistic Analysis of Algorithms </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter22/approx" target="" > Approximation Algorithms </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter22/ideen" target="" > Ideen und Konzepte der Informatik </a> </li> </ul> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer22" target="" > Summer 2022 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter21" target="" > Winter 2021/22 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer21" target="" > Summer 2021 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter20" target="" > Winter 2020/21 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer20" target="" > Summer 2020 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter19" target="" > Winter 2019/20 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer19" target="" > Summer 2019 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter18" target="" > Winter 2018/19 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer18" target="" > Summer 2018 </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/seminars" target="" > Seminars </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/seminars/algorithms-with-predictions" target="" > Algorithms with Predictions </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/quantum-lecture-series" target="" > Quantum Lecture Series </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/virtual-theory-seminar" target="" > Virtual Theory Seminar </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/publications" target="" > Publications </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/publications/current-year" target="" > Current Year </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/publications/last-year" target="" > Last Year </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/publications/the-year-before-last" target="" > The Year Before Last </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/publications/reports" target="" > Reports </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item "> <a class=" " href="/departments/algorithms-complexity/adfocs" target="" > ADFOCS </a> </li> <li class="main-nav__item js-main-nav-item "> <a class=" " href="/departments/algorithms-complexity/news" target="" > News </a> </li> </ul> </div> </nav> </div> <div class="site-header__lang-switch"> <a title="Seite auf Deutsch anzeigen" href="/de/departments/algorithms-complexity/research/parameterized-algorithms-and-complexity">Deutsch</a> </div> </div> </div> </div> </header> <!--TYPO3SEARCH_begin--> <nav class="breadcrumb"> <div class="breadcrumb__ct"> <ol class="breadcrumb__items"> <li class="breadcrumb__item is-first " > <a class="breadcrumb__link" href="/departments" title="Departments"> <span class="breadcrumb__lbl">Departments</span> </a> </li> <li class="breadcrumb__item " > <a class="breadcrumb__link" href="/departments/algorithms-complexity" title="Algorithms and Complexity"> <span class="breadcrumb__lbl">Algorithms and Complexity</span> </a> </li> <li class="breadcrumb__item is-sec-to-last " > <a class="breadcrumb__link" href="/departments/algorithms-complexity/research" title="Research"> <span class="breadcrumb__lbl">Research</span> </a> </li> <li class="breadcrumb__item is-last is-active" > <span class="breadcrumb__lbl">Parameterized and Counting Algorithms and Complexity</span> </li> </ol> </div> </nav> <main id="main" class="site__body has-sidebar sidebar-left"> <div class="site__main"> <div id="c15705" class="content content--textpic content--layout-0 has-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><header class="content__hd"><h1 class="content__ttl "> Parameterized and Counting Algorithms and Complexity </h1></header><div class="content__bd"><div class="ce-textpic ce-right ce-intext"><div class="ce-bodytext"><p>Parameterized complexity analyzes how different parameters of the input influence the complexity of hard algorithmic problems. The general goal is to show with fixed-parameter tractability results that the combinatorial explosion can be confined to certain well-defined parameters, or to understand why such algorithms are not possible. An interesting class of hard problems that we consider are counting problems (where the goal is to count all solutions), as they may allow for interesting phenomena that are not observed in the corresponding decision problems.</p></div></div></div></div></div></div> <div id="c15703" class="content content--header content--layout-0 has-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><header class="content__hd"><h2 class="content__ttl "> People </h2></header><div class="content__bd"></div></div></div></div> <div id="c23499" class="content content--list content--layout-0 has-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><header class="content__hd"><h3 class="content__ttl "> Coordinator </h3></header><div class="content__bd"><div class="tx-ttaddress"><div class="tt_address_list dm-mpgCard"><article class="address-card" itemscope itemtype="https://schema.org/Person"><div class="address-card__img-ct "><img itemprop="image" class="address-card__img" src="/fileadmin/user_upload/KarolWegrzycki.jpg" width="1515" height="1935" alt="" /></div><div class="address-card__cnt-ct"><header class="address-card__hd"><h3 class="address-card__name" itemprop="name">Karol Wegrzycki</h3></header><div class="address-card__cnt"><div class="address-card__main-ct"><address class="address-card__address" itemprop="address" itemscope itemtype="http://schema.org/PostalAddress"> Max-Planck-Institut für Informatik <br><span itemprop="streetAddress"> Saarland Informatics Campus <br> Campus E1 4 – Room 306 </span><br><span itemprop="postalCode">66123</span> <span itemprop="addressLocality">Saarbrücken</span></address><meta itemprop="url" content="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/people/current-members/karol-wegrzycki"/><a class="link-more address-card__more-lnk" href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/people/current-members/karol-wegrzycki">more</a></div><div class="address-card__contact-ct"><h4 class="address-card__sec-ttl">Contact</h4><ul class="address-card__contact-list"><li><a class="link-mail" href="https://domino.mpi-inf.mpg.de/intranet/mpii/people.nsf/email!ReadForm&UID=23771&Name=Wegrzycki%2c%20Karol" >Get email via email</a></li><li><a href="tel:+4968193250" class="link-phone" itemprop="telephone">+49 681 9325 0</a></li><li><a href="fax:+4968193251099" class="link-fax" itemprop="faxNumber">+49 681 9325 1099</a></li></ul></div><div class="address-card__department-ct"><h4 class="address-card__sec-ttl">Departments</h4><div class="department">ALGO</div></div></div></div></article><article class="address-card" itemscope itemtype="https://schema.org/Person"><div class="address-card__img-ct is-placeholder"><img role="" class="address-card__img address-card__img--placeholder" alt="Platzhalterfoto" src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/Images/person-placeholder.png" width="180" height="200" /></div><div class="address-card__cnt-ct"><header class="address-card__hd"><h3 class="address-card__name" itemprop="name">Dr. Daniel Neuen</h3></header><div class="address-card__cnt"><div class="address-card__main-ct"><address class="address-card__address" itemprop="address" itemscope itemtype="http://schema.org/PostalAddress"> Max-Planck-Institut für Informatik <br><span itemprop="streetAddress"> Saarland Informatics Campus <br> Campus E1 4 – Room 305 </span><br><span itemprop="postalCode">66123</span> <span itemprop="addressLocality">Saarbrücken</span></address><meta itemprop="url" content="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/people/current-members/daniel-neuen"/><a class="link-more address-card__more-lnk" href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/people/current-members/daniel-neuen">more</a></div><div class="address-card__contact-ct"><h4 class="address-card__sec-ttl">Contact</h4><ul class="address-card__contact-list"><li><a class="link-mail" href="https://domino.mpi-inf.mpg.de/intranet/mpii/people.nsf/email!ReadForm&UID=23631&Name=Neuen%2c%20Daniel" >Get email via email</a></li><li><a href="tel:+4968193250" class="link-phone" itemprop="telephone">+49 681 9325 0</a></li><li><a href="fax:+4968193251099" class="link-fax" itemprop="faxNumber">+49 681 9325 1099</a></li></ul></div><div class="address-card__department-ct"><h4 class="address-card__sec-ttl">Departments</h4><div class="department">ALGO</div></div></div></div></article></div></div></div></div></div></div> <div id="c23501" class="content content--div content--layout-0 has-no-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><div class="content__bd"><hr class="ce-div" /></div></div></div></div> <div id="c23503" class="content content--list content--layout-0 has-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><header class="content__hd"><h3 class="content__ttl "> Researchers </h3></header><div class="content__bd"><div class="tx-ttaddress"><div class="tt_address_list dm-mpgCard"><article class="address-card" itemscope itemtype="https://schema.org/Person"><div class="address-card__img-ct "><img itemprop="image" class="address-card__img" src="/fileadmin/user_upload/jfocke.png" width="893" height="892" alt="" /></div><div class="address-card__cnt-ct"><header class="address-card__hd"><h3 class="address-card__name" itemprop="name">Jacob Focke</h3></header><div class="address-card__cnt"><div class="address-card__main-ct"><address class="address-card__address" itemprop="address" itemscope itemtype="http://schema.org/PostalAddress"> Max-Planck-Institut für Informatik <br><span itemprop="streetAddress"> Saarland Informatics Campus <br> Campus E1 4 – Room 322 </span><br><span itemprop="postalCode">66123</span> <span itemprop="addressLocality">Saarbrücken</span></address><meta itemprop="url" content="https://people.mpi-inf.mpg.de/~fjacob"/><a class="link-more address-card__more-lnk" href="https://people.mpi-inf.mpg.de/~fjacob">more</a></div><div class="address-card__contact-ct"><h4 class="address-card__sec-ttl">Contact</h4><ul class="address-card__contact-list"><li><a class="link-mail" href="https://domino.mpi-inf.mpg.de/intranet/mpii/people.nsf/email!ReadForm&UID=23773&Name=Focke%2c%20Jacob" >Get email via email</a></li><li><a href="tel:+4968193251133" class="link-phone" itemprop="telephone">+49 681 9325 1133</a></li><li><a href="fax:+4968193251099" class="link-fax" itemprop="faxNumber">+49 681 9325 1099</a></li></ul></div><div class="address-card__department-ct"><h4 class="address-card__sec-ttl">Departments</h4><div class="department">ALGO</div></div></div></div></article><article class="address-card" itemscope itemtype="https://schema.org/Person"><div class="address-card__img-ct is-placeholder"><img role="" class="address-card__img address-card__img--placeholder" alt="Platzhalterfoto" src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/Images/person-placeholder.png" width="180" height="200" /></div><div class="address-card__cnt-ct"><header class="address-card__hd"><h3 class="address-card__name" itemprop="name">Simon Döring</h3></header><div class="address-card__cnt"><div class="address-card__main-ct"><address class="address-card__address" itemprop="address" itemscope itemtype="http://schema.org/PostalAddress"> Max-Planck-Institut für Informatik <br><span itemprop="streetAddress"> Saarland Informatics Campus <br> Campus E1 4 – Room 324 </span><br><span itemprop="postalCode">66123</span> <span itemprop="addressLocality">Saarbrücken</span></address><meta itemprop="url" content="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/people/current-members/simon-doering"/><a class="link-more address-card__more-lnk" href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity/people/current-members/simon-doering">more</a></div><div class="address-card__contact-ct"><h4 class="address-card__sec-ttl">Contact</h4><ul class="address-card__contact-list"><li><a class="link-mail" href="https://domino.mpi-inf.mpg.de/intranet/mpii/people.nsf/email!ReadForm&UID=24333&Name=Döring%2c%20Simon" >Get email via email</a></li><li><a href="tel:+4968193251132" class="link-phone" itemprop="telephone">+49 681 9325 1132</a></li><li><a href="fax:+4968193251099" class="link-fax" itemprop="faxNumber">+49 681 9325 1099</a></li></ul></div><div class="address-card__department-ct"><h4 class="address-card__sec-ttl">Departments</h4><div class="department">ALGO, IMPRS</div></div></div></div></article></div></div></div></div></div></div> </div> <aside class="site__sidebar"> <div class="sidebar__content"> <div id="c23453" class="content content--shortcut content--layout-0 has-no-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><div class="content__bd"><div id="c23437" class="content content--menu_subpages content--layout-13 has-no-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><div class="content__bd"><ul class="pages-menu pages-menu--layout-sidebar"><li class="pages-menu__entry"><a href="/departments/algorithms-complexity/research/algorithmic-game-theory" target="" title="Algorithmic Game Theory" class="pages-menu__lnk "><span class="pages-menu__page-ttl"> Algorithmic Game Theory </span></a></li><li class="pages-menu__entry"><a href="/departments/algorithms-complexity/research/approximation-algorithms" target="" title="Approximation Algorithms" class="pages-menu__lnk "><span class="pages-menu__page-ttl"> Approximation Algorithms </span></a></li><li class="pages-menu__entry"><a href="/departments/algorithms-complexity/research/fine-grained-complexity" target="" title="Fine-Grained Complexity and Algorithm Design" class="pages-menu__lnk "><span class="pages-menu__page-ttl"> Fine-Grained Complexity and Algorithm Design </span></a></li><li class="pages-menu__entry"><a href="/departments/algorithms-complexity/research/graph-algorithms" target="" title="Graph Algorithms" class="pages-menu__lnk "><span class="pages-menu__page-ttl"> Graph Algorithms </span></a></li><li class="pages-menu__entry"><a href="/departments/algorithms-complexity/research/optimization" target="" title="Optimization" class="pages-menu__lnk "><span class="pages-menu__page-ttl"> Optimization </span></a></li><li class="pages-menu__entry"><a href="/departments/algorithms-complexity/research/parameterized-algorithms-and-complexity" target="" title="Parameterized and Counting Algorithms and Complexity" class="pages-menu__lnk is-active"><span class="pages-menu__page-ttl"> Parameterized and Counting Algorithms and Complexity </span></a></li><li class="pages-menu__entry"><a href="/departments/algorithms-complexity/research/robust-learning" target="" title="Robust Learning" class="pages-menu__lnk "><span class="pages-menu__page-ttl"> Robust Learning </span></a></li></ul></div></div></div></div></div></div></div></div> </div> </aside> </main> <!--TYPO3SEARCH_end--> <footer class="site__footer"> <div class="site-footer__to-top-lnk-ct js-to-top-btn-ct"> <a class="site-footer__to-top-lnk js-to-top-btn js-scroll-lnk" role="button" href="#top"><span class="site-footer__to-top-lnk-lbl">Top</span></a> </div> <div class="site-footer site-footer--contact"> <div class="site-footer__ct"> <div class="site-footer__row"> <section class="site-footer__sec site-footer__sec--quick-links js-collapse-ct"> <h2 class="site-footer__sec-ttl"> <a href="javascript:" role="button" class="site-footer__sec-ttl-lnk js-collapse-toggle is-collapsed"> Quick Links <i class="site-footer__sec-expand-icon mpg-icon mpg-icon-down2"></i> </a> </h2> <div class="site-footer__sec-bd site-footer-links js-collapse-target-ct is-collapsed"> <div class="js-collapse-target"> <div id="c22759" class="content content--menu_pages content--layout-10 has-no-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><div class="content__bd"><ul><li><a href="/institute/address" target="" title="Location" class=""><span>Location</span></a></li><li><a href="/news/latest" target="" title="Press" class=""><span>Press</span></a></li><li><a href="/covid-19" target="" title="COVID-19" class=""><span>COVID-19</span></a></li></ul></div></div></div></div> </div> </div> </section> <section class="site-footer__sec site-footer__sec--social-media js-collapse-ct"> </section> <div class="site-footer__sec site-footer__sec--quick-actions"> <div id="c22761" class="content content--text content--layout-0 has-no-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><div class="content__bd"><p><a href="mailto:kontakt@mpi-inf.mpg.de" class="button">Contact</a></p></div></div></div></div> </div> </div> </div> </div> <div class="site-footer site-footer--legal"> <div class="site-footer__ct"> <div class="site-footer__row"> <div class="site-footer__sec site-footer__org"> <img class="site-footer__org-img" alt="Bildmarke Max Planck Gesellschaft" src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/Images/Core/mpg-bildmarke_w.svg" width="160" height="160" /> <div class="site-footer__org-lbl"> Max-Planck-Gesellschaft </div> </div> <div class="site-footer__sec site-footer__legal-links"> <div id="c22763" class="content content--menu_pages content--layout-10 has-no-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><div class="content__bd"><ul><li><a href="/sitemap" target="" title="Sitemap" class=""><span>Sitemap</span></a></li><li><a href="https://imprint.mpi-klsb.mpg.de/inf/www.mpi-inf.mpg.de" target="" title="Imprint" class=""><span>Imprint</span></a></li><li><a href="https://data-protection.mpi-klsb.mpg.de/inf/www.mpi-inf.mpg.de" target="" title="Data Protection" class=""><span>Data Protection</span></a></li></ul></div></div></div></div> </div> <div class="site-footer__sec site-footer__copyright"> © 2024, Max-Planck-Gesellschaft </div> </div> </div> </div> </footer> <script src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/JavaScript/Libraries/jquery-1.12.4.min.js?1725541122"></script> <script src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/JavaScript/Libraries/jquery-ui-1.13.2.min.js?1725541122"></script> <script src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/JavaScript/Libraries/swiper-bundle-8.4.6.min.js?1725541122"></script> <script src="/typo3conf/ext/powermail/Resources/Public/JavaScript/Powermail/Form.min.js?1726560232" defer="defer"></script> <script src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/JavaScript/Build/main.js?1725541122"></script> </body> </html>