No.018 Parameterized Complexity and the Understanding, Design and Analysis of Heuristics

David Bryant (University of Otago)

Title: Combinatorial optimization using diversities

Abstract: A diversity is a generalisation of metric spaces to beyond pairwise comparisons. Formally, it is a pair (X,δ) where X is a set and δ is defined on finite subsets of X satisfying the two axioms:

• δ(A) = 0 ⇒ |A| ? 1;
• δ(A ∪ C) ? δ(A ∪ B) + δ(B ∪ C) whenever B≠?.

Note that δ restricted to pairs gives a metric. Examples of diversities include the diameter, the length of the minimum tour, and the length of an optimal Steiner tree. Diversities were introduced in a recent paper of Bryant and Tupper, and generate a rich theory which we are only just beginning to explore. We survey some of the main results and then speculate wildly on their use in applied combinatorial optimization and data analysis. In particular we discuss their role in hypergraph algorithms and show how L1 embedding strategies for graphs and metrics generalize to analogous results for hypergraphs and diversities (at least that is the plan).

___________________________________________________________________

Benjamin Burton (The University of Queensland)

Title: Exploring parameterised complexity in computational topology

Abstract: Topological decision problems in three dimensions are notoriously difficult: the mere existence of an algorithm is often a major result, and many important algorithms have yet to be studied from a complexity viewpoint.? Even “simple” problems, such as unknot recognition (testing whether a loop of string is knotted), or 3-sphere recognition (testing whether a triangulated 3-manifold is topologically trivial), have best-known algorithms that are worst-case exponential time.? In practice, however, some of these algorithms run surprisingly well in experimental settings, and we discuss some reasons why parameterised complexity now looks to be the “right” tool to explain this behaviour.? We also present some initial forays into the parameterised complexity of topological problems, including both fixed-parameter-tractability and W[P]-hardness results.

___________________________________________________________________

Yota Otachi (Japan Advanced Institute of Science And Technology)

Title: Graph Isomorphism Problem Parameterized by Width Parameters

Abstract: We study the parameterized complexity of the graph isomorphism problem when parameterized by width parameters related to strong tree decompositions. We first present fpt algorithms for some width parameters, and then provide a unified explanation for various isomorphism results concerned with parameters related to tree decompositions. As a first step towards intractability results for parameterized graph isomorphism we develop an fpt Turing-reduction from strong tree width to the a priori unrelated parameter maximum degree. This is joint work with Pascal Schweitzer.

___________________________________________________________________

Takeaki Uno (National Institute of Informatics)

Title: FPT for Scalable Mining Algorithms

Abstract: Data mining algorithms often enumerates patterns/structures included in the given data, for exhaust search of candidates. They usually deal with data that are noisy but have some property (sparse, locally dense, having hubs, etc.) The time complexity of the algorithm are usually exponential in the input size, but practically they are efficient.? One of the reason is that, the number of solutions is not exponential, relatively small, and the algorithms are output sensitive (#solutions (resp., #edges) is a kind of “fixed parameter”).? We would like to introduce fixed parameters to data mining/enumeration algorithms so that we can solve difficult problems, and can understand the mechanism of the practical efficiency.

___________________________________________________________________

Dimitrios M. Thilikos (CNRS-LIRMM & University of Athens)

Title: From parameterized complexity to heuristics

Abstract: In this talk we describe some of the the existing links netween parameterized complexity and heuristics. More particular we present how the notion of kernelization can serve as a formal mathematical framework for studying preprocessing and we explain why the multivariate computational complexity viewpoint is necessary for this approach. We also give several research directions for the study of various heuristic approaches using tools and techniqeus from parameterized algorithm design.

___________________________________________________________________

Sebastian Boecker (University of Jena, Germany)

Title: The Matrix Representation with Flipping problem and the FlipCut heuristic

Abstract: In computational phylogenetics, supertree methods assemble phylogenetic trees with non-identical but overlapping taxon sets, into a larger supertree: These supertrees contains all taxa of all input trees and describes the evolutionary relationship of these taxa. This problem can be formalized in different ways, to cope with contradictory information in the input. I will concentrate on the Matrix Representation with Flipping (MRF) framework: The input trees are encoded in a 0/1/?-matrix, and we search for a minimum set of 0/1-flips such that the resulting matrix admits a directed perfect phylogeny. This is an NP-hard problem, but if all input trees share the same set of taxa, the problem is fixed-parameter tractable. Otherwise, the problem is W[2]-hard and cannot be approximated within a constant factor. I will present a data reduction as well as an ILP formulation for the problem which, unfortunately, both do not work well in practice. Finally, I will present a novel heuristic for the problem, named FlipCut supertrees. Evaluations of the heuristic are very promising.

___________________________________________________________________

Gregory Gutin (Royal Holloway, University of London)

Title: Domination Analysis of Heuristics

Abstract: Many heuristics do not provide approximation guarantee in the worst case and so we cannot compare worst case performance of heuristics for the same problem using approximation. Domination analysis is an alternative way of comparing heuristics based on the concept of domination number proposed in 1996 by Glover and Punnen. (Interestingly, some results in the area were obtained already in the 1970s.) Consider the Asymmetric Travelling Salesman problem (defined on weighted complete directed graph). The domination number of an ATSP heuristic H donated dom(H,n) is the maximum integer d such that for every instance of ATSP on n vertices H finds a solution not worse than d solutions. For example, for every n> 1 there are instances on n vertices for which the nearest neighbour heuristic (NN) will find the unique worst possible solution. Thus, the domination number of NN is 1. There are ATSP heuristics with domination number at least (n-2)! and even higher. We’ll concentrate mainly on TSP heuristics, but heuristics for other problems will also be mentioned.

___________________________________________________________________

Gregory Gutin (Royal Holloway University of London)

Title: Exponential Neighborhoods

Abstract: Exponential neighbourhoods contain exponential number of solutions. However, there are some such neighbourhoods for which the best solution can be found in polynomial time. We’ll consider such neighbourhoods for TSP and other problems. We should be able to get something much bigger if we replace ‘polynomial time’ with ‘FPT time’, but for which problems we can do it and what is the parameter?

___________________________________________________________________

Hadas Shachnai (Technion, Israel)

Title: Tractable Parameterizations for the Minimum Linear Arrangement Problem

Abstract: The Minimum Linear Arrangement (MLA) problem asks to embed a given graph on the integer line so that the sum of the edge lengths of the embedded graph is? minimized. Most layout problems are either intractable, or not known to be tractable,? parameterized by the treewidth of the input graphs. We investigate MLA with respect to three parameters that provide more structure than treewidth.? In particular, we give a factor 1+ε-approximation algorithm for MLA parameterized by (ε, k), where k is? the vertex cover number of the input graph. By a similar approach, we describe two FPT algorithms that exactly solve MLA parameterized by,? respectively, the max-leaf and clique-cover numbers of the input graph. Joint work with Michael Fellows, Danny Hermelin and Frances Rosamond

___________________________________________________________________

Rod Downey (Victoria University of Wellington)

Title: What have I been doing recently in parameterized complexity

Abstract: I will mention some of the work in this area I have been looking at. This includes the new book with Mike, plus lots of new projects with Judith Egan, Mike, Fran and Peter Shaw. These concern permissive search, incremental computation, hueristics, and parameterizing by the number of numbers. I will give a brief overview of these.

___________________________________________________________________

Fedor V. Fomin (Univ. of Bergen)

Title: Parameterized k-opt

Abstract: We discuss results on the parameterized complexity about searching in the k-exchange neighborhoods for the following optimization problems
– Problems on planar graphs
– Feedback Arc Set in Tournaments (FAST)
– Chordal completion (fill-in)

___________________________________________________________________

Falk Hüfner (Technische Universität Berlin)

Title: Implementing and testing fixed-parameter algorithms

Abstrat:? The talk is about various aspects of implementing and testing fixed-parameter algorithms, such as ensuring correctness, debugging, speedups, and performance evaluation and visualization.

___________________________________________________________________

Siamak Tazari (Google)

Title: Deconstructing Algorithms: From Theory to Engineering

Abstract: We present the generic idea of deconstructing a sophisticated theoretical algorithm, and engineering its parts to obtain a useful, practical “heuristic” via a case study on Steiner tree in planar graphs. Afterwards, we will briefly talk about the disconnect between theoretical computer science and the state of the industry today and propose possible directions on bringing them closer together.

___________________________________________________________________

Faisal Abu Khzam (Lebanese American University)

Title: Practical Aspects of Fixed-Parameter Algorithms: An Implementations’ Viewpoint

Abstract: The talk will cover some implementation techniques and a discussion of design alternatives, including a comparison between best-worst-case algorithms and algorithms based on simple heuristic priorities. Some parallel implementation strategies will be discussed as well.

___________________________________________________________________

Manuel Sorge (Technische Universität Berlin)
Title: Some Algorithmic Challenges in Arc Routing

Arc Routing problems occur naturally in many logistic tasks like delivering mail, garbage disposal, street sweeping and snow plowing. Such a task is formulated, for example, in the Chinese Postman problem where, given an edge-weighted graph, one searches for a minimum-weight tour that visits all edges in the graph. In this simple form, Chinese Postman is solvable in polynomial time, but many variants that arise in applications yield NP-hard problems. Yet, despite the practical relevance, the literature on parameterized complexity of Arc Routing problems is rather sparse. We give a brief survey of the known (parameterized) complexity results and identify some interesting open questions. In particular, we briefly report on our theoretical and empirical studies related to the Rural Postman problem. This is joint work with René van Bevern, Rolf Niedermeier, and Mathias Weller.

___________________________________________________________________

Patricia Evans (University of New Brunswick)

Title: Inferring Haplotypes from Genotypes on a Pedigree

Abstract: In genetics, it is considerably easier to determine genotype information (what values an individual has at each of a number of marker sites) than it is to determine haplotype information (how those values are split between the chromosomes). Since haplotype information can be very useful in pedigree analysis, we would like to be able to infer haplotypes from genotypes for a set of individuals with known family relationships in a pedigree. This work examines how haplotypes including recombination can be inferred as an application of Edge Bipartitization. This is joint work with Peter Doan.

___________________________________________________________________

?Peter Rossmanith (RWTH Aachen University)

Title: Implementing Courcelle’s Theorem

Abstract: I will make a demonstration of our MSO solver and explain how it works.
The solver is based on game trees.

___________________________________________________________________

Peter Shaw (Charles Darwin University)

Title: Solving Hard Problems Incrementaly

Abstract😕 By utilizing an incremental (or solution repair) formulation, some hard problems, when formulated with appropriate parameters, become FPT. This talk describes how algorithmic solutions of such problems can be applied as effective FPT subroutines to improve many local search problems. To illustrate this we consider the Dominating Set problem. We show that the incremental Dominating set problem is FPT. A number of formulations of this problem were considered, but most of these resulted in hard problems. We show a FPT algorithm for one particular formulation and further prove that this problem has no polynomial kernel.?This is a joint work with? Rod Downey, Judith Egan, Michael Fellows, and Frances Rosamond.

___________________________________________________________________

Kazuo Iwama (School of Informatics, Kyoto University)

Title: Parameterized Testability

Abstract: In graph property testing, given a graph represented by an oracle, we want to test whether the graph satisfies some predetermined property P or ε-far from satisfying the property. Roughly speaking, a graph is called ε-far from a property if we need to modify an ε-fraction of the graph to make it satisfy the property. A most important focus in this topic has been on general characterizations for (constant-time) testable properties, which have obtained much progress in the last decade: For the dense graph model, Alon et al. finally obtained a purely combinatorial necessary and sufficient condition for P to be testable that is closely related to the Szemerédi Regularity Lemma. For the bounded-degree graph model, due to Benjamini et al., any property is testable if it is minor- closed.

In this talk, we are still interested in a general framework of testable properties, but our approach is a bit different from the qualitative one as above. Rather, we are interested in “parameterized properties” that are quite common in NP optimization problems. A bit curiously, this direction has not been so popular in the context of property testing. The obvious reason is that the problem becomes less interesting in both the dense graph model and the bounded degree model. For instance, consider the problem k-Vertex Cover for a constant k. In the dense graph model, we want to decide whether a graph has a vertex cover of size at most k or we need to remove at least εn^2 edges to have the property. It turns out that this property is easily testable just by accepting only graphs with at most ε \times n^2 edges.

To avoid this triviality, we consider the general graph model with an augmentation of random edge sampling capability. It is shown that a variety of such problems, including k-Vertex Cover, k-Feedback Vertex Set, k-Multicut, k-Path Free and k-Dominating Set, are constant-time testable if k is constant. It should be noted that the first four problems are fixed parameter tractable (FPT) and it turns out that algorithmic techniques for their FPT algorithms (bounded-branching tree search, color coding, etc.) are also useful for our testers. k- Dominating Set is W[2]-hard, but we can still test the property in constant time since the definition of ε-farness makes the problem trivial for non- sparse graphs that are the source of hardness for the original optimization problem. We also consider k-Odd Cycle Transversal, which is another well-known FPT problem, but we only give a sublinear-time tester when k is a constant. This is a joint work with Yuichi Yoshida.

___________________________________________________________________

Yoshio Okamoto (JAIST)

Title: Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data

Abstract: We study a character-based phylogeny reconstruction problem when an incomplete set of data is given. More specifically, we consider the situation under the directed perfect phylogeny assumption with binary characters in which for some species the states of some characters are missing. Our main object is to give an efficient algorithm to enumerate (or list) all perfect phylogenies that can be obtained when the missing entries are completed. While a simple branch-and-bound algorithm (B&B) shows a theoretically good performance, we propose another approach based on a zero-suppressed binary decision diagram (ZDD). Experimental results on randomly generated data exhibit that the ZDD approach outperforms B&B. We also prove that counting the number of phylogenetic trees consistent with a given data is #P-complete, thus providing an evidence that an efficient random sampling seems hard. Joint work with Masashi Kiyomi and Toshiki Saitoh.

___________________________________________________________________

Christophe Paul (CNRS-LIRMM)

Title: Linear kernel via conflict packing – application to FAST and dense RTI problems.

Abstract: We introduce a new technique to design kernelization algorithms for parameterized problems, namely Conflict Packing. We illustrate this technique on two well-studied problems: FAST and RTI. For the former, one is given a tournament T = (V,A) and seeks a set of at most k arcs whose reversal in T leads to an acyclic tournament. While a linear vertex-kernel is already known for this problem, it requires a constant-factor approximation algorithm as a subroutine. Using the Conflict Packing, we show how to avoid this subroutine to find a so-called safe partition.? In the RTI problem, one is given a set of vertices V and a dense collection R of rooted binary trees over three vertices of V and seeks a rooted tree over V containing all but at most k triplets from R. Using again the Conflict Packing, we prove that the dense RTI problem admits a linear vertex-kernel. This result improves the on the quadratic known kernel.? joint work with A. Perez and S. Thomassé

___________________________________________________________________

Daniel Lokshtanov (Univ. Bergen)

Title: LP-Based Parameterized Algorithms for Separation Problems

Abstract: We show that the most basic branching algorithm for Vertex Cover turbo-boosted by a classical linear-programming based reduction rule runs in time 4^[k-OPT(LP)]poly(n), where OPT(LP) is the value of the optimum solution to the LP relaxation of the problem. It turns out that this algorithm can be used to solve Odd Cycle Transversal and Almost 2-Sat, as well as a number of other problems, in time 4^k poly(n). We then give an improved algorithm for Vertex Cover with running time 2.32^[k-OPT(LP)]poly(n), this improves considerably over the currently fastest parameterized algorithms for Odd Cycle Transversal and Almost 2-SAT.