Parameterized and Exact Computation

Frontmatter

Balanced Hashing, Color Coding and Approximate Counting

Abstract

Color Coding is an algorithmic technique for deciding efficiently if a given input graph contains a path of a given length (or another small subgraph of constant tree-width). Applications of the method in computational biology motivate the study of similar algorithms for counting the number of copies of a given subgraph. While it is unlikely that exact counting of this type can be performed efficiently, as the problem is #W[1]-complete even for paths, approximate counting is possible, and leads to the investigation of an intriguing variant of families of perfect hash functions. A family of functions from [n] to [k] is an (ε,k)-balanced family of hash functions, if there exists a positive T so that for every K ⊂ [n] of size |K| = k, the number of functions in the family that are one-to-one on K is between (1 − ε)T and (1 + ε)T. The family is perfectly k-balanced if it is (0,k)-balanced.

We show that every such perfectly k-balanced family is of size at least \(c(k) n^{\lfloor k/2 \rfloor}\), and that for every \(\epsilon>\frac{1}{poly(k)}\) there are explicit constructions of (ε,k)-balanced families of hash functions from [n] to [k] of size e ^{(1 + o(1))k} logn. This is tight up to the o(1)-term in the exponent, and supplies deterministic polynomial time algorithms for approximately counting the number of paths or cycles of a specified length k (or copies of any graph H with k vertices and bounded tree-width) in a given input graph of size n, up to relative error ε, for all k ≤ O(logn).

Noga Alon, Shai Gutner

Kernelization: New Upper and Lower Bound Techniques

Abstract

In this survey, we look at kernelization: algorithms that transform in polynomial time an input to a problem to an equivalent input, whose size is bounded by a function of a parameter. Several results of recent research on kernelization are mentioned. This survey looks at some recent results where a general technique shows the existence of kernelization algorithms for large classes of problems, in particular for planar graphs and generalizations of planar graphs, and recent lower bound techniques that give evidence that certain types of kernelization algorithms do not exist.

Hans L. Bodlaender

A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams

Abstract

Given two binary phylogenetic trees covering the same n species, it is useful to compare them by drawing them with leaves arranged side-by-side. To facilitate comparison, we would like to arrange the trees to minimize the number of crossings k induced by connecting pairs of identical species. This is the NP-hard Tanglegram Layout problem. By providing a fast transformation to the Balanced Subgraph problem, we show that the problem admits an O(2 ^k n ⁴) algorithm, improving upon a previous fixed-parameter approach with running time O(c ^k n ^O(1)) where c ≈ 1000. We enhance a Balanced Subgraph implementation based on data reduction and iterative compression with improvements tailored towards these instances, and run experiments with real-world data to show the practical applicability of this approach. All practically relevant (k ≤ 1000) Tanglegram Layout instances can be solved exactly within seconds. Additionally, we provide a kernel-like bound by showing how to reduce the Balanced Subgraph instances for Tanglegram Layout on complete binary trees to a size of O(k logk).

Sebastian Böcker, Falk Hüffner, Anke Truss, Magnus Wahlström

Planar Capacitated Dominating Set Is W[1]-Hard

Abstract

Given a graph G together with a capacity function c : V(G) →ℕ, we call S ⊆ V(G) a capacitated dominating set if there exists a mapping f: (V(G) ∖ S) →S which maps every vertex in (V(G) ∖ S) to one of its neighbors such that the total number of vertices mapped by f to any vertex v ∈ S does not exceed c(v). In the Planar Capacitated Dominating Set problem we are given a planar graph G, a capacity function c and a positive integer k and asked whether G has a capacitated dominating set of size at most k. In this paper we show that Planar Capacitated Dominating Set is W[1]-hard, resolving an open problem of Dom et al. [IWPEC, 2008 ]. This is the first bidimensional problem to be shown W[1]-hard. Thus Planar Capacitated Dominating Set can become a useful starting point for reductions showing parameterized intractablility of planar graph problems.

Hans L. Bodlaender, Daniel Lokshtanov, Eelko Penninkx

Boolean-Width of Graphs

Abstract

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods across a cut of a graph. For many graph problems this number is the runtime bottleneck when using a divide-and-conquer approach. Boolean-width is similar to rank-width, which is related to the number of GF(2)-sums (1+1=0) of neighborhoods instead of the Boolean-sums (1+1=1) used for boolean-width. For an n-vertex graph G given with a decomposition tree of boolean-width k we show how to solve Minimum Dominating Set, Maximum Independent Set and Minimum or Maximum Independent Dominating Set in time O(n(n + 2^3k k )). We show for any graph that its boolean-width is never more than the square of its rank-width. We also exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Θ(n ²) vertices has boolean-width Θ(logn) and tree-width, branch-width, clique-width and rank-width Θ(n). Moreover, any optimal rank-decomposition of such a graph will have boolean-width Θ(n), i.e. exponential in the optimal boolean-width.

B. -M. Bui-Xuan, J. A. Telle, M. Vatshelle

The Complexity of Satisfiability of Small Depth Circuits

Abstract

Say that an algorithm solving a Boolean satisfiability problem x on n variables is improved if it takes time poly(|x|)2 ^cn for some constant c < 1, i.e., if it is exponentially better than a brute force search. We show an improved randomized algorithm for the satisfiability problem for circuits of constant depth d and a linear number of gates cn: for each d and c, the running time is 2^{(1 − δ)n} where the improvement \(\delta\geq 1/O(c^{2^{d-2}-1}\lg^{3\cdot 2^{d-2}-2}c)\), and the constant in the big-Oh depends only on d. The algorithm can be adjusted for use with Grover’s algorithm to achieve a run time of \(2^{\frac{1-\delta}{2}n}\) on a quantum computer.

Chris Calabro, Russell Impagliazzo, Ramamohan Paturi

On Finding Directed Trees with Many Leaves

Abstract

The ROOTED MAXIMUM LEAF OUTBRANCHING problem consists in finding a spanning directed tree rooted at some prescribed vertex of a digraph with the maximum number of leaves. Its parameterized version asks if there exists such a tree with at least k leaves. We use the notion of s − t numbering studied in [19,6,20] to exhibit combinatorial bounds on the existence of spanning directed trees with many leaves. These combinatorial bounds allow us to produce a constant factor approximation algorithm for finding directed trees with many leaves, whereas the best known approximation algorithm has a \(\sqrt{OPT}\)-factor [11]. We also show that ROOTED MAXIMUM LEAF OUTBRANCHING admits an edge-quadratic kernel, improving over the vertex-cubic kernel given by Fernau et al [13].

Jean Daligault, Stéphan Thomassé

Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms

Abstract

Many algorithms for FPT graph problems are search tree algorithms with sophisticated local branching rules. But it has also been noticed that using the global structure of input graphs complements the the search tree paradigm. Here we prove some new results based on the global structure of bounded-degree graphs after branching away the high-degree vertices. Some techniques and structural results are generic and should find more applications. First, we decompose a graph by “separating” branchings into cheaper or smaller components wich are then processed separately. Using this idea we accelerate the O ^*(1.3803 ^k ) time algorithm for counting the vertex covers of size k (Mölle, Richter, and Rossmanith, 2006) to O ^*(1.3740 ^k ). Next we characterize the graphs where no edge is in three conflict triples, i.e., triples of vertices with exactly two edges. This theorem may find interest in graph theory, and it yields an O ^*(1.47 ^k ) time algorithm for Cluster Deletion, improving upon the previous O ^*(1.53 ^k ) (Gramm, Guo, Hüffner, Niedermeier, 2004). Cluster Deletion is the problem of deleting k edges to destroy all conflict triples and get a disjoint union of cliques. For graphs where every edge is in O(1) conflict triples we show a nice dichotomy: The graph or its complement has degree O(1). This opens the possibility for future improvements via the above decomposition technique.

Peter Damaschke

Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover

Abstract

We propose a framework for the complexity of algorithms for FPT problems with two separate parameters k,m and with exponential time bounds O ^*(x ^k y ^m ) where x,y > 1 are constant bases. An optimal combination of bases x,y can be chosen depending on the ratio m/k. As a first illustration we apply the framework to the problem of finding, in a graph, a vertex cover of size k that leaves at most m edges uncovered. We report the best branching rules we could find so far, for all ranges of ratio m/k.

Peter Damaschke

What Makes Equitable Connected Partition Easy

Abstract

We study the Equitable Connected Partition problem: partitioning the vertices of a graph into a specified number of classes, such that each class of the partition induces a connected subgraph, so that the classes have cardinalities that differ by at most one. We examine the problem from the parameterized complexity perspective with respect to various (aggregate) parameterizations involving such secondary measurements as: (1) the number of partition classes, (2) the treewidth, (3) the pathwidth, (4) the minimum size of a feedback vertex set, (5) the minimum size of a vertex cover, (6) and the maximum number of leaves in a spanning tree of the graph. In particular, we show that the problem is W[1]-hard with respect to the first four combined, while it is fixed-parameter tractable with respect to each of the last two alone. The hardness result holds even for planar graphs. The problem is in XP when parameterized by treewidth, by standard dynamic programming techniques. Furthermore, we show that the closely related problem of Equitable Coloring (equitably partitioning the vertices into a specified number of independent sets) is FPT parameterized by the maximum number of leaves in a spanning tree of the graph.

Rosa Enciso, Michael R. Fellows, Jiong Guo, Iyad Kanj, Frances Rosamond, Ondřej Suchý

Improved Induced Matchings in Sparse Graphs

Abstract

An induced matching in graph G is a matching which is an induced subgraph of G. Clearly, among two vertices with the same neighborhood (called twins) at most one is matched in any induced matching, and if one of them is matched then there is another matching of the same size that matches the other vertex. Motivated by this, Kanj, Pelsmajer, Schaefer and Xia [10] studied induced matchings in twinless graphs. They showed that any twinless planar graph contains an induced matching of size at least \(\frac{n}{40}\) and that there are twinless planar graphs that do not contain an induced matching of size greater than \(\frac{n}{27}+O(1)\). We improve both these bounds to \(\frac{n}{28}+O(1)\), which is tight up to an additive constant. This implies that the problem of deciding an whether a planar graph has an induced matching of size k has a kernel of size at most 28k. We also show for the first time that this problem is FPT for graphs of bounded arboricity.

Kanj et al. presented also an algorithm which decides in \(O(2^{159\sqrt{k}}+n)\)-time whether an n-vertex planar graph contains an induced matching of size k. Our results improve the time complexity analysis of their algorithm. However, we show also a more efficient, \(O(2^{25.5\sqrt{k}}+n)\)-time algorithm. Its main ingredient is a new, O ^*(4 ^l )-time algorithm for finding a maximum induced matching in a graph of branch-width at most l.

Rok Erman, Łukasz Kowalik, Matjaž Krnc, Tomasz Waleń

Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs

Abstract

We show that three subclasses of bounded treewidth graphs are well-quasi-ordered by refinements of the minor order. Specifically, we prove that graphs with bounded feedback-vertex-set are well-quasi-ordered by the topological-minor order, graphs with bounded vertex-covers are well-quasi-ordered by the subgraph order, and graphs with bounded circumference are well-quasi-ordered by the induced-minor order. Our results give an algorithm for recognizing any graph family in these classes which is closed under the corresponding minor order refinement.

Michael R. Fellows, Danny Hermelin, Frances A. Rosamond

An Exact Algorithm for the Maximum Leaf Spanning Tree Problem

Abstract

Given an undirected graph G with n nodes, the Maximum Leaf Spanning Tree problem asks to find a spanning tree of G with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4 ^k poly(n)) using a simple branching algorithm introduced by a subset of the authors [13]. Daligault, Gutin, Kim, and Yeo [6] improved this branching algorithm and obtained a running time of O(3.72 ^k poly(n)). In this paper, we study the problem from an exact exponential time point of view, where it is equivalent to the Connected Dominating Set problem. For this problem Fomin, Grandoni, and Kratsch showed how to break the Ω(2 ⁿ ) barrier and proposed an O(1.9407 ⁿ ) time algorithm [10]. Based on some properties of [6] and [13], we establish a branching algorithm whose running time of O(1.8966 ⁿ ) has been analyzed using the Measure-and-Conquer technique. Finally we provide a lower bound of Ω(1.4422 ⁿ ) for the worst case running time of our algorithm.

Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith

An Exponential Time 2-Approximation Algorithm for Bandwidth

Abstract

The bandwidth of a graph G on n vertices is the minimum b such that the vertices of G can be labeled from 1 to n such that the labels of every pair of adjacent vertices differ by at most b.

In this paper, we present a 2-approximation algorithm for the Bandwidth problem that takes worst-case \(\mathcal{O}(1.9797^n)\) \(= \mathcal{O}(3^{0.6217 n})\) time and uses polynomial space. This improves both the previous best 2- and 3-approximation algorithms of Cygan et al. which have an \(\mathcal{O}^*(3^n)\) and \(\mathcal{O}^*(2^n)\) worst-case time bounds, respectively. Our algorithm is based on constructing bucket decompositions of the input graph. A bucket decomposition partitions the vertex set of a graph into ordered sets (called buckets) of (almost) equal sizes such that all edges are either incident on vertices in the same bucket or on vertices in two consecutive buckets. The idea is to find the smallest bucket size for which there exists a bucket decomposition. The algorithm uses a simple divide-and-conquer strategy along with dynamic programming to achieve this improved time bound.

Martin Fürer, Serge Gaspers, Shiva Prasad Kasiviswanathan

On Digraph Width Measures in Parameterized Algorithmics

Abstract

In contrast to undirected width measures (such as tree-width or clique-width), which have provided many important algorithmic applications, analogous measures for digraphs such as DAG-width or Kelly-width do not seem so successful. Several recent papers, e.g. those of Kreutzer–Ordyniak, Dankelmann–Gutin–Kim, or Lampis–Kaouri–Mitsou, have given some evidence for this. We support this direction by showing that many quite different problems remain hard even on graph classes that are restricted very beyond simply having small DAG-width. To this end, we introduce new measures K-width and DAG-depth. On the positive side, we also note that taking Kanté’s directed generalization of rank-width as a parameter makes many problems fixed parameter tractable.

Robert Ganian, Petr Hliněný, Joachim Kneis, Alexander Langer, Jan Obdržálek, Peter Rossmanith

The Parameterized Complexity of Some Geometric Problems in Unbounded Dimension

Abstract

We study the parameterized complexity of the following fundamental geometric problems with respect to the dimension d:

i) Given n points in ℝ ^d , compute their minimum enclosing cylinder.

ii) Given two n-point sets in ℝ ^d , decide whether they can be separated by two hyperplanes.

iii) Given a system of n linear inequalities with d variables, find a maximum size feasible subsystem.

We show that (the decision versions of) all these problems are W[1]-hard when parameterized by the dimension d. Our reductions also give a n ^Ω(d)-time lower bound (under the Exponential Time Hypothesis).

Panos Giannopoulos, Christian Knauer, Günter Rote

Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms

Abstract

We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem and the bounded length cut problem. From Menger’s theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length l of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both k and l and hardness results when the parameter is only one of k and l. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph.

Petr A. Golovach, Dimitrios M. Thilikos

Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs

Abstract

A parameterized problem Π can be considered as a set of pairs (I,k) where I is the main part and k (usually an integer) is the parameter. Π is called fixed-parameter tractable (FPT) if membership of (I,k) in Π can be decided in time O(f(k)|I| ^c ), where |I| denotes the size of I, f(k) is a computable function, and c is a constant independent of k and I. An algorithm of complexity O(f(k)|I| ^c ) is called a fixed-parameter algorithm.

It often happens that although a problem is FPT, the practitioners prefer to use imprecise heuristic methods to solve the problem in the real-world situation simply because of the fact that the heuristic methods are faster. In this paper we argue that in this situation a fixed-parameter algorithm for the given problem may be still of a considerable practical use. In particular, the fixed-parameter algorithm can be used to evaluate the approximation quality of heuristic approaches.

To demonstrate this way of application of fixed-parameter algorithms, we consider the problem of extracting a maximum-size reflected network in a linear program. We evaluate a state-of-the-art heuristic SGA and two variations of it with a new heuristic and with an exact algorithm. The new heuristic and algorithm use fixed-parameter tractable procedures. The new heuristic turned out to be of little practical interest, but the exact algorithm is of interest when the network size is close to that of the linear program especially if the exact algorithm is used in conjunction with SGA. Another conclusion which has a large practical interest is that some variant of SGA can be the best choice because in most cases it returns optimal solutions; previously it was disregarded because comparing to the other heuristics it improved the solution insignificantly at the cost of much larger running times.

Gregory Gutin, Daniel Karapetyan, Igor Razgon

A Probabilistic Approach to Problems Parameterized above or below Tight Bounds

Abstract

We introduce a new approach for establishing fixed-parameter tractability of problems parameterized above tight lower bounds or below tight upper bounds. To illustrate the approach we consider two problems of this type of unknown complexity that were introduced by Mahajan, Raman and Sikdar (J. Comput. Syst. Sci. 75, 2009). We show that a generalization of one of the problems and three nontrivial special cases of the other problem admit kernels of quadratic size.

Gregory Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo

Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor

Abstract

The domination number of a graph G = (V,E) is the minimum size of a dominating set U ⊆ V, which satisfies that every vertex in V ∖ U is adjacent to at least one vertex in U. The notion of a problem kernel refers to a polynomial time algorithm that achieves some provable reduction of the input size. Given a graph G whose domination number is k, the objective is to design a polynomial time algorithm that produces a graph G′ whose size depends only on k, and also has domination number equal to k. Note that the graph G′ is constructed without knowing the value of k. All the constructions in this paper are of monotone kernels, that is, the kernel G′ is a subgraph of the input graph G. Problem kernels can be used to obtain efficient approximation and exact algorithms for the domination number, and are also useful in practical settings.

In this paper, we present the first nontrivial result for the general case of graphs with an excluded minor, as follows. For every fixed h, given a graph G with n vertices that does not contain K _h as a topological minor, our O(n ^3.5 + k ^O(1)) time algorithm constructs a subgraph G′ of G, such that if the domination number of G is k, then the domination number of G′ is also k and G′ has at most k ^c vertices, where c is a constant that depends only on h. This result is improved for graphs that do not contain K _3,h as a topological minor, using a simpler algorithm that constructs a subgraph with at most ck vertices, where c is a constant that depends only on h.

Our results imply that there is a problem kernel of polynomial size for graphs with an excluded minor and a linear kernel for graphs that are K _3,h -minor-free. The only previous kernel results known for the dominating set problem are the existence of a linear kernel for the planar case as well as for graphs of bounded genus. Using the polynomial kernel construction, we give an \(O(n^{3.5} + 2^{O(\sqrt{k})})\) time algorithm for finding a dominating set of size at most k in an H-minor-free graph with n vertices. This improves the running time of the previously best known algorithm.

Shai Gutner

Partitioning into Sets of Bounded Cardinality

Abstract

We show that the partitions of an n-element set into k members of a given set family can be counted in time O((2 − ε) ⁿ ), where ε> 0 depends only on the maximum size among the members of the family. Specifically, we give a simple combinatorial algorithm that counts the perfect matchings in a given graph on n vertices in time O(poly(n)ϕ ⁿ ), where ϕ = 1.618... is the golden ratio; this improves a previous bound based on fast matrix multiplication.

Mikko Koivisto

Two Edge Modification Problems without Polynomial Kernels

Abstract

Given a graph G and an integer k, the Π Edge Completion/Editing/Deletion problem asks whether it is possible to add, edit, or delete at most k edges in G such that one obtains a graph that fulfills the property Π. Edge modification problems have received considerable interest from a parameterized point of view. When parameterized by k, many of these problems turned out to be fixed-parameter tractable and some are known to admit polynomial kernelizations, i.e., efficient preprocessing with a size guarantee that is polynomial in k. This paper answers an open problem posed by Cai (IWPEC 2006), namely, whether the Π Edge Deletion problem, parameterized by the number of deletions, admits a polynomial kernelization when Π can be characterized by a finite set of forbidden induced subgraphs. We answer this question negatively based on recent work by Bodlaender et al. (ICALP 2008) which provided a framework for proving polynomial lower bounds for kernelizability. We present a graph H on seven vertices such that \(\mathcal{H}\)-free Edge Deletion and H-free Edge Editing do not admit polynomial kernelizations, unless \(\mbox{NP}\subseteq \mbox{coNP}/\mbox{poly}\). The application of the framework is not immediate and requires a lower bound for a Not-1-in-3 SAT problem that may be of independent interest.

Stefan Kratsch, Magnus Wahlström

On the Directed Degree-Preserving Spanning Tree Problem

Abstract

In this paper we initiate a systematic study of the Reduced Degree Spanning Tree ( d -RDST) problem, where given a digraph D and a nonnegative integer k, the goal is to construct a spanning out-tree with at most k vertices of reduced out-degree. We show that this problem is fixed-parameter tractable and admits a problem kernel with at most 8k vertices on strongly connected digraphs and O(k ²) vertices on general digraphs. We also give an algorithm for this problem on general digraphs with run-time O ^*(5.942 ^k ). We also consider the dual of d-RDST: given a digraph D and a nonnegative integer k, construct a spanning out-tree of D with at least k vertices of full out-degree. We show that this problem is W[1]-hard on two important digraph classes: directed acyclic graphs and strongly connected digraphs.

Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, Somnath Sikdar

Even Faster Algorithm for Set Splitting!

Abstract

In p -Set Splitting we are given a universe U, a family \(\cal F\) of subsets of U and a positive integer k and the objective is to find a partition of U into W and B such that there are at least k sets in \(\cal F\) that have non-empty intersection with both B and W. In this paper we study p -Set Splitting from kernelization and algorithmic view points. Given an instance \((U,{\cal F},k)\) of p -Set Splitting, our kernelization algorithm obtains an equivalent instance with at most 2k sets and k elements in polynomial time. Finally, we give a fixed parameter tractable algorithm for p -Set Splitting running in time O(1.9630 ^k  + N), where N is the size of the instance. Both our kernel and our algorithm improve over the best previously known results. Our kernelization algorithm utilizes a classical duality theorem for a connectivity notion in hypergraphs. We believe that the duality theorem we make use of, will turn out to be an important tool from combinatorial optimization in obtaining kernelization algorithms.

Daniel Lokshtanov, Saket Saurabh

Stable Assignment with Couples: Parameterized Complexity and Local Search

Abstract

We study the Hospitals/Residents with Couples problem, a variant of the classical Stable Marriage problem. This is the extension of the Hospitals/Residents problem where residents are allowed to form pairs and submit joint rankings over hospitals. We use the framework of parameterized complexity, considering the number of couples as a parameter. We also apply a local search approach, and examine the possibilities for giving FPT algorithms applicable in this context. Furthermore, we also investigate the matching problem containing couples that is the simplified version of the Hospitals/Residents problem modeling the case when no preferences are given.

Dániel Marx, Ildikó Schlotter

Improved Parameterized Algorithms for the Kemeny Aggregation Problem

Abstract

We give improvements over fixed parameter tractable (FPT) algorithms to solve the Kemeny aggregation problem, where the task is to summarize a multi-set of preference lists, called votes, over a set of alternatives, called candidates, into a single preference list that has the minimum total τ-distance from the votes. The τ-distance between two preference lists is the number of pairs of candidates that are ordered differently in the two lists. We study the problem for preference lists that are total orders. We develop algorithms of running times \(O^*(1.403^{k_t})\), \(O^*(5.823^{k_t/m})\leq O^*(5.823^{k_{avg}})\) and \(O^*(4.829^{k_{max}})\) for the problem, ignoring the polynomial factors in the O ^* notation, where k _t is the optimum total τ-distance, m is the number of votes, and k _avg (resp. k _max ) is the average (resp. maximum) over pairwise τ-distances of votes. Our algorithms improve the best previously known running times of \(O^*(1.53^{k_t})\) and \(O^*(16^{k_{avg}})\leq O^*(16^{k_{max}})\) [3,4], which also implies an \(O^*(16^{2k_t/m})\) running time. We also show how to enumerate all optimal solutions in \(O^*(36^{k_t/m}) \leq O^*(36^{k_{avg}})\) time.

Narges Simjour

Computing Pathwidth Faster Than 2 n

Abstract

Computing the Pathwidth of a graph is the problem of finding a tree decomposition of minimum width, where the decomposition tree is a path. It can be easily computed in \(\mathcal{O}^*(2^n)\) time by using dynamic programming over all vertex subsets. For some time now there has been an open problem if there exists an algorithm computing Pathwidth with running time \(\mathcal{O}^*(c^n)\) for c < 2. In this paper we show that such an algorithm with c = 1.9657 exists, and that there also exists an approximation algorithm and a constant τ such that an opt + τ approximation can be obtained in \(\mathcal{O}^*(1.89^ n)\) time.

Karol Suchan, Yngve Villanger

Backmatter