Editorial

4 pages, 170 KiB

Open AccessEditorial

Special Issue “New Frontiers in Parameterized Complexity and Algorithms”: Foreward by the Guest Editors

by Neeldhara Misra, Frances Rosamond and Meirav Zehavi

Algorithms 2020, 13(9), 236; https://0-doi-org.brum.beds.ac.uk/10.3390/a13090236 - 18 Sep 2020

Viewed by 2326

This Special Issue contains eleven articles—surveys and research papers—that represent fresh and ambitious new directions in the area of Parameterized Complexity. They provide ground-breaking research at the frontiers of knowledge, and they contribute to bridging the gap between theory and practice. The scope [...] Read more.

This Special Issue contains eleven articles—surveys and research papers—that represent fresh and ambitious new directions in the area of Parameterized Complexity. They provide ground-breaking research at the frontiers of knowledge, and they contribute to bridging the gap between theory and practice. The scope and impact of the field continues to increase. Promising avenues and new research challenges are highlighted in this Special Issue. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

Research

Jump to: Editorial

60 pages, 754 KiB

Open AccessArticle

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

by Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee and Pasin Manurangsi

Algorithms 2020, 13(6), 146; https://0-doi-org.brum.beds.ac.uk/10.3390/a13060146 - 19 Jun 2020

Cited by 46 | Viewed by 4904

Abstract

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques [...] Read more.

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

27 pages, 488 KiB

Open AccessArticle

Parameterized Optimization in Uncertain Graphs—A Survey and Some Results

by N. S. Narayanaswamy and R. Vijayaragunathan

Algorithms 2020, 13(1), 3; https://0-doi-org.brum.beds.ac.uk/10.3390/a13010003 - 19 Dec 2019

Cited by 2 | Viewed by 3525

Abstract

We present a detailed survey of results and two new results on graphical models of uncertainty and associated optimization problems. We focus on two well-studied models, namely, the Random Failure (RF) model and the Linear Reliability Ordering (LRO) model. We present an FPT [...] Read more.

We present a detailed survey of results and two new results on graphical models of uncertainty and associated optimization problems. We focus on two well-studied models, namely, the Random Failure (RF) model and the Linear Reliability Ordering (LRO) model. We present an FPT algorithm parameterized by the product of treewidth and max-degree for maximizing expected coverage in an uncertain graph under the RF model. We then consider the problem of finding the maximal core in a graph, which is known to be polynomial time solvable. We show that the Probabilistic-Core problem is polynomial time solvable in uncertain graphs under the LRO model. On the other hand, under the RF model, we show that the Probabilistic-Core problem is W[1]-hard for the parameter d, where d is the minimum degree of the core. We then design an FPT algorithm for the parameter treewidth. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

► Show Figures

Figure 1

33 pages, 618 KiB

Open AccessArticle

Parameterized Algorithms in Bioinformatics: An Overview

by Laurent Bulteau and Mathias Weller

Algorithms 2019, 12(12), 256; https://0-doi-org.brum.beds.ac.uk/10.3390/a12120256 - 01 Dec 2019

Cited by 16 | Viewed by 5287

Abstract

Bioinformatics regularly poses new challenges to algorithm engineers and theoretical computer scientists. This work surveys recent developments of parameterized algorithms and complexity for important NP-hard problems in bioinformatics. We cover sequence assembly and analysis, genome comparison and completion, and haplotyping and phylogenetics. Aside [...] Read more.

Bioinformatics regularly poses new challenges to algorithm engineers and theoretical computer scientists. This work surveys recent developments of parameterized algorithms and complexity for important NP-hard problems in bioinformatics. We cover sequence assembly and analysis, genome comparison and completion, and haplotyping and phylogenetics. Aside from reporting the state of the art, we give challenges and open problems for each topic. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

► Show Figures

Figure 1

18 pages, 529 KiB

Open AccessArticle

FPT Algorithms for Diverse Collections of Hitting Sets

by Julien Baste, Lars Jaffke, Tomáš Masařík, Geevarghese Philip and Günter Rote

Algorithms 2019, 12(12), 254; https://0-doi-org.brum.beds.ac.uk/10.3390/a12120254 - 27 Nov 2019

Cited by 17 | Viewed by 4323

Abstract

In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This [...] Read more.

In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in

k + r

for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of ‘base’ solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

► Show Figures

Figure 1

14 pages, 278 KiB

Open AccessArticle

Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey

by Robert Ganian and Sebastian Ordyniak

Algorithms 2019, 12(12), 248; https://0-doi-org.brum.beds.ac.uk/10.3390/a12120248 - 22 Nov 2019

Cited by 6 | Viewed by 4441

Abstract

Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint [...] Read more.

Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a detailed complexity landscape for the problem centered around the structure of graphical representations of instances. The aim of this survey is to summarize these recent developments, put them into context and a unified format, and make them more approachable for experts from many diverse backgrounds. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

► Show Figures

Figure 1

14 pages, 328 KiB

Open AccessArticle

The Inapproximability of k-DominatingSet for Parameterized AC 0 Circuits †

by Wenxing Lai

Algorithms 2019, 12(11), 230; https://0-doi-org.brum.beds.ac.uk/10.3390/a12110230 - 04 Nov 2019

Cited by 1 | Viewed by 3396

Abstract

Chen and Flum showed that any FPT-approximation of the k-Clique problem is not in para-

{AC}^{0}

and the k-DominatingSet (k-DomSet) problem could not be computed by para-

{AC}^{0}

circuits. It is natural to [...] Read more.

Chen and Flum showed that any FPT-approximation of the k-Clique problem is not in para-

{AC}^{0}

and the k-DominatingSet (k-DomSet) problem could not be computed by para-

{AC}^{0}

circuits. It is natural to ask whether the

f (k)

-approximation of the k-DomSet problem is in para-

{AC}^{0}

for some computable function f. Very recently it was proved that assuming

W [1] \neq FPT

, the k-DomSet problem cannot be

f (k)

-approximated by FPT algorithms for any computable function f by S., Laekhanukit and Manurangsi and Lin, seperately. We observe that the constructions used in Lin’s work can be carried out using constant-depth circuits, and thus we prove that para-

{AC}^{0}

circuits could not approximate this problem with ratio

f (k)

for any computable function f. Moreover, under the hypothesis that the 3-CNF-SAT problem cannot be computed by constant-depth circuits of size

2^{ε n}

for some

ε > 0

, we show that constant-depth circuits of size

n^{o (k)}

cannot distinguish graphs whose dominating numbers are either ≤k or >

{(\frac{log n}{3 log log n})}^{1 / k}

. However, we find that the hypothesis may be hard to settle by showing that it implies

NP ⊈ {NC}^{1}

. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

20 pages, 516 KiB

Open AccessArticle

A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth

by Borislav Slavchev, Evelina Masliankova and Steven Kelk

Algorithms 2019, 12(10), 200; https://0-doi-org.brum.beds.ac.uk/10.3390/a12100200 - 20 Sep 2019

Viewed by 4889

Abstract

We present an algorithm selection framework based on machine learning for the exact computation of treewidth, an intensively studied graph parameter that is NP-hard to compute. Specifically, we analyse the comparative performance of three state-of-the-art exact treewidth algorithms on a wide array [...] Read more.

We present an algorithm selection framework based on machine learning for the exact computation of treewidth, an intensively studied graph parameter that is NP-hard to compute. Specifically, we analyse the comparative performance of three state-of-the-art exact treewidth algorithms on a wide array of graphs and use this information to predict which of the algorithms, on a graph by graph basis, will compute the treewidth the quickest. Experimental results show that the proposed meta-algorithm outperforms existing methods on benchmark instances on all three performance metrics we use: in a nutshell, it computes treewidth faster than any single algorithm in isolation. We analyse our results to derive insights about graph feature importance and the strengths and weaknesses of the algorithms we used. Our results are further evidence of the advantages to be gained by strategically blending machine learning and combinatorial optimisation approaches within a hybrid algorithmic framework. The machine learning model we use is intentionally simple to emphasise that speedup can already be obtained without having to engage in the full complexities of machine learning engineering. We reflect on how future work could extend this simple but effective, proof-of-concept by deploying more sophisticated machine learning models. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

► Show Figures

Figure 1

16 pages, 380 KiB

Open AccessArticle

Parameterised Enumeration for Modification Problems

by Nadia Creignou, Raïda Ktari, Arne Meier, Julian-Steffen Müller, Frédéric Olive and Heribert Vollmer

Algorithms 2019, 12(9), 189; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090189 - 09 Sep 2019

Cited by 9 | Viewed by 2951

Abstract

Recently, Creignou et al. (Theory Comput. Syst. 2017), introduced the class DelayFPT into parameterised complexity theory in order to capture the notion of efficiently solvable parameterised enumeration problems. In this paper, we propose a framework for parameterised ordered enumeration and will show how [...] Read more.

Recently, Creignou et al. (Theory Comput. Syst. 2017), introduced the class DelayFPT into parameterised complexity theory in order to capture the notion of efficiently solvable parameterised enumeration problems. In this paper, we propose a framework for parameterised ordered enumeration and will show how to obtain enumeration algorithms running with an FPT delay in the context of general modification problems. We study these problems considering two different orders of solutions, namely, lexicographic order and order by size. Furthermore, we present two generic algorithmic strategies. The first one is based on the well-known principle of self-reducibility and is used in the context of lexicographic order. The second one shows that the existence of a neighbourhood structure among the solutions implies the existence of an algorithm running with FPT delay which outputs all solutions ordered non-decreasingly by their size. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

► Show Figures

Figure 1

28 pages, 412 KiB

Open AccessFeature PaperArticle

A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

by Ronald de Haan and Stefan Szeider

Algorithms 2019, 12(9), 188; https://0-doi-org.brum.beds.ac.uk/10.3390/a12090188 - 09 Sep 2019

Cited by 4 | Viewed by 3393

Abstract

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These problems are parameterized versions of problems whose complexity lies at the second level of the Polynomial Hierarchy or [...] Read more.

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These problems are parameterized versions of problems whose complexity lies at the second level of the Polynomial Hierarchy or higher. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

► Show Figures

Figure 1

17 pages, 960 KiB

Open AccessArticle

Practical Access to Dynamic Programming on Tree Decompositions

by Max Bannach and Sebastian Berndt

Algorithms 2019, 12(8), 172; https://0-doi-org.brum.beds.ac.uk/10.3390/a12080172 - 16 Aug 2019

Cited by 10 | Viewed by 4055

Abstract

Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few decades, but the practicability of these methods for real-world problems is still not well understood. We investigate the practicability of one of the fundamental approaches of this [...] Read more.

Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few decades, but the practicability of these methods for real-world problems is still not well understood. We investigate the practicability of one of the fundamental approaches of this field: dynamic programming on tree decompositions. Indisputably, this is a key technique in parameterized algorithms and modern algorithm design. Despite the enormous impact of this approach in theory, it still has very little influence on practical implementations. The reasons for this phenomenon are manifold. One of them is the simple fact that such an implementation requires a long chain of non-trivial tasks (as computing the decomposition, preparing it, …). We provide an easy way to implement such dynamic programs that only requires the definition of the update rules. With this interface, dynamic programs for various problems, such as 3-coloring, can be implemented easily in about 100 lines of structured Java code. The theoretical foundation of the success of dynamic programming on tree decompositions is well understood due to Courcelle’s celebrated theorem, which states that every MSO-definable problem can be efficiently solved if a tree decomposition of small width is given. We seek to provide practical access to this theorem as well, by presenting a lightweight model checker for a small fragment of

{MSO}_{1}

(that is, we do not consider “edge-set-based” problems). This fragment is powerful enough to describe many natural problems, and our model checker turns out to be very competitive against similar state-of-the-art tools. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

► Show Figures

Figure 1

12 pages, 784 KiB

Open AccessArticle

Randomized Parameterized Algorithms for the Kidney Exchange Problem

by Mugang Lin, Jianxin Wang, Qilong Feng and Bin Fu

Algorithms 2019, 12(2), 50; https://0-doi-org.brum.beds.ac.uk/10.3390/a12020050 - 25 Feb 2019

Cited by 5 | Viewed by 4142

Abstract

In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the [...] Read more.

In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant L (typically

2 \leq L \leq 5

), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases

L = 3

and

L \geq 3

, and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively. Full article

(This article belongs to the Special Issue New Frontiers in Parameterized Complexity and Algorithms)

Journal Menu

Journal Browser

New Frontiers in Parameterized Complexity and Algorithms

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Published Papers (12 papers)

Editorial

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI