New Frontiers in Parameterized Complexity and Algorithms

2024

The research on parameterized complexity (PC), described in these peer-reviewed chapters by esteemed researchers, provides ties to practice as well as new theoretical developments, many in the direction of AI. Applications in bioinformatics and social choice are described, as well as faster, less costly approximation methods and new techniques using machine learning to find treewidth and other metrics. Many practical problems can be solved by harnessing the power of both PC and SAT solvers or integer linear programming modeled by parameterized graph problems. The extremely rapid development and deployment of PC continues to bring fresh understanding and solutions to fundamental open questions.

eBook

English

MDPI - Multidisciplinary Digital Publishing Institute, 2024.

kidney exchange problem, randomized algorithm, parameterized algorithm, random partitioning, multilinear monomial detection, fixed-parameter tractability, treewidth, model checking, parameterized complexity, polynomial hierarchy, fpt-reductions, parameterised complexity, enumeration, bounded search tree, parameterised enumeration, ordering, tree decomposition, algorithm selection, machine learning, combinatorial optimisation, parameterized AC0, dominating set, inapproximability, integer linear programming, treedepth, solution diversity, hitting sets, vertex cover, feedback vertex set, Hamming distance, genome assembly, sequence analysis, comparative genomics, haplotyping, phylogenetics, agreement forests, probabilistic graphs, uncertain graphs, influence maximization, cascade failure, linear reliable ordering, expected coverage, probabilistic core., approximation algorithms, hardness of approximation, FPT, kernelization, lower bounds, fine-grained, Heuristics, turbo-charged, ETH/SETH, Computing and Information Technology, Computer science