Parameterized and Exact Computation

We consider the complexity of deciding, given a graph G and a formula φ of first-order logic in the language of graphs, whether or not G ⊧ φ. In other words, we are interested in the complexity of the satisfaction relation for first-order logic on graphs. More particularly, we look at the complexity of this problem parameterized by the length of the formula φ. This problem (which is known to be AW[*]-complete) includes as special cases many important graph-theoretic problems, including Independent Set, Dominating Set and complete problems at all levels of the W-hierarchy.

A protrusion in a graph is a subgraph of constant treewidth that can be separated from the graph by removing a constant number of vertices. More precisely, given a graph G = (V, E) and S ⊆ V , we denote by \(\partial(S)\) the set of vertices in S that have a neighbour in V \ S.

Symmetry is a common feature of many combinatorial problems. Unfortunately eliminating all symmetry from a problem is often computationally intractable. This paper argues that recent parameterized complexity results provide insight into that intractability and help identify special cases in which symmetry can be dealt with more tractably.

The Colorful Motif problem asks if, given a vertex-colored graph G, there exists a subset S of vertices of G such that the graph induced by G on S is connected and contains every color in the graph exactly once. The problem is motivated by applications in computational biology and is also well-studied from the theoretical point of view. In particular, it is known to be NP-complete even on trees of maximum degree three [Fellows et al, ICALP 2007]. In their pioneering paper that introduced the color-coding technique, Alon et al. [STOC 1995] show, inter alia, that the problem is FPT on general graphs. More recently, Cygan et al. [WG 2010] showed that Colorful Motif is NP-complete on comb graphs, a special subclass of the set of trees of maximum degree three. They also showed that the problem is not likely to admit polynomial kernels on forests.

We continue the study of the kernelization complexity of the Colorful Motif problem restricted to simple graph classes. Surprisingly, the infeasibility of polynomial kernelization persists even when the input is restricted to comb graphs. We demonstrate this by showing a simple but novel composition algorithm. Further, we show that the problem restricted to comb graphs admits polynomially many polynomial kernels. To our knowledge, there are very few examples of problems with many polynomial kernels known in the literature. We also show hardness of polynomial kernelization for certain variants of the problem on trees; this rules out a general class of approaches for showing many polynomial kernels for the problem restricted to trees. Finally, we show that the problem is unlikely to admit polynomial kernels on another simple graph class, namely the set of all graphs of diameter two. As an application of our results, we settle the classical complexity of Connected Dominating Set on graphs of diameter two — specifically, we show that it is NP-complete.

Rank Aggregation is important in many areas ranging from web search over databases to bioinformatics. The underlying decision problem Kemeny Score is NP-complete even in case of four input rankings to be aggregated into a “median ranking”. We study efficient polynomial-time data reduction rules that allow us to find optimal median rankings. On the theoretical side, we improve a result for a “partial problem kernel” from quadratic to linear size. On the practical side, we provide encouraging experimental results with data based on web search and sport competitions, e.g., computing optimal median rankings for real-world instances with more than 100 candidates within milliseconds.

Measure & Conquer (M&C) is the prominent technique for analyzing exact algorithms for computationally hard problems . It tries to balance worse and better situations within the algorithm analysis.

Several obstacles prevent the application of this technique in parameterized algorithmics, making it rarely applied in this area. However, these difficulties can be handled in some situations. We will exemplify this with two problems related to Vertex Cover, namely Connected Vertex Cover and Edge Dominating Set. For both problems, several parameterized algorithms have been published, all based on the idea of first enumerating minimal vertex covers and then producing solutions to the requested problem. Using M&C in this context will improve on the hitherto published running times, offering some unifying view. In contrast to some of the earlier suggested algorithms, ours will use polynomial space.

We relate the exponential complexities 2 ^s(k)n of k-sat and the exponential complexity 2\(^{s(\pi_{2}3-{\sc SAT})n}\) of Π₂3-sat (evaluating formulas of the form ∀ x ∃ y ∅ (x,y) where ∅ is a 3-CNF in x variables and y variables) and show that s( ∞ ) (the limit of s(k) as k → ∞) is at most s(Π₂3-sat). Therefore, if we assume the Strong Exponential-Time Hypothesis, then there is no algorithm for Π₂3-sat running in time 2 ^cn with c < 1. On the other hand, a nontrivial exponential-time algorithm for Π₂3-sat would provide a k-sat solver with better exponent than all current algorithms for sufficiently large k. We also show several syntactic restrictions of Π₂3-sat have nontrivial algorithms, and provide strong evidence that the hardest cases Π₂3-sat must have a mixture of clauses of two types: one universal literal and two existential literals, or only existential literals. Moreover, the hardest cases must have at least n − o(n) universal variables, and hence only o(n) existential variables. Our proofs involve the construction of efficient minimally unsatisfiable k-cnfs and the application of the Sparsification Lemma.

Kernelization algorithms for the cluster editing problem have been a popular topic in the recent research in parameterized computation. Thus far most kernelization algorithms for this problem are based on the concept of critical cliques. In this paper, we present new observations and new techniques for the study of kernelization algorithms for the cluster editing problem. Our techniques are based on the study of the relationship between cluster editing and graph edge-cuts. As an application, we present an \({\cal O}(n^2)\)-time algorithm that constructs a 2k kernel for the weighted version of the cluster editing problem. Our result meets the best kernel size for the unweighted version for the cluster editing problem, and significantly improves the previous best kernel of quadratic size for the weighted version of the problem.

We show that computing the deficiency is NP-hard even under several severe restrictions placed on the housing market, and thus we consider different parameterizations of the problem. We prove W[1]-hardness for the case where the parameter is the value of the deficiency we aim for. By contrast, we provide an FPT algoritm for computing the deficiency of the market, if the parameter is the number of different house types.

For a formula F in conjunctive normal form (CNF), let sat(F) be the maximum number of clauses of F that can be satisfied by a truth assignment, and let m be the number of clauses in F. It is well-known that for every CNF formula F, sat(F) ≥ m/2 and the bound is tight when F consists of conflicting unit clauses (x) and \((\bar{x})\). Since each truth assignment satisfies exactly one clause in each pair of conflicting unit clauses, it is natural to reduce F to the unit-conflict free (UCF) form. If F is UCF, then Lieberherr and Specker (J. ACM 28(2):411-421, 1981) proved that \({\rm sat}(F)\ge {\hat{\phi}} m\), where \({\hat{\phi}} =(\sqrt{5}-1)/2\).

We introduce another reduction that transforms a UCF CNF formula F into a UCF CNF formula F′, which has a complete matching, i.e., there is an injective map from the variables to the clauses, such that each variable maps to a clause containing that variable or its negation. The formula F′ is obtained from F by deleting some clauses and the variables contained only in the deleted clauses. We prove that \({\rm sat}(F) \ge {\hat{\phi}} m + (1-{\hat{\phi}})(m-m') + n'(2-3{\hat{\phi}})/2\), where n′ and m′ are the number of variables and clauses in F′, respectively. This improves the Lieberherr-Specker lower bound on sat(F).

We show that our new bound has an algorithmic application by considering the following parameterized problem: given a UCF CNF formula F decide whether sat(F) \(\ge {\hat{\phi}} m + k,\) where k is the parameter. This problem was introduced by Mahajan and Raman (J. Algorithms 31(2):335–354, 1999) who conjectured that the problem is fixed-parameter tractable, i.e., it can be solved in time f(k)(nm) ^O(1) for some computable function f of k only. We use the new bound to show that the problem is indeed fixed-parameter tractable by describing a polynomial-time algorithm that transforms any problem instance into an equivalent one with at most \(\lfloor (7+3\sqrt{5})k\rfloor\) variables.

The Pathwidth One Vertex Deletion (POVD) problem, given an undirected graph G and an integer k, asks whether one can delete at most k vertices from G so that the remaining graph has pathwidth at most 1. Recently Philip et al.[14] initiated the study of the parameterized complexity of (POVD) and have shown a quartic kernel and a 7 ^k n ^O(1) algorithm. In this paper we improve these results by showing a quadratic kernel and a 4.65 ^k n ^O(1) algorithm.

We consider the computational complexity of a problem modeling bribery in the context of voting systems. In the scenario of Swap Bribery, each voter assigns a certain price for swapping the positions of two consecutive candidates in his preference ranking. The question is whether it is possible, without exceeding a given budget, to bribe the voters in a way that the preferred candidate wins in the election.

We initiate a parameterized and multivariate complexity analysis of Swap Bribery, focusing on the case of k-approval. We investigate how different cost functions affect the computational complexity of the problem. We identify a special case of k-approval for which the problem can be solved in polynomial time, whereas we prove NP-hardness for a slightly more general scenario. We obtain fixed-parameter tractability as well as W[1]-hardness results for certain natural parameters.

The usefulness of parameterized algorithmics has often depended on what Niedermeier has called “the art of problem parameterization”. In this paper we introduce and explore a novel but general form of parameterization: the number of numbers. Several classic numerical problems, such as Subset Sum, Partition, 3-Partition, Numerical 3-Dimensional Matching, and Numerical Matching with Target Sums, have multisets of integers as input. We initiate the study of parameterizing these problems by the number of distinct integers in the input. We rely on an FPT result for Integer Linear Programming Feasibility to show that all the above-mentioned problems are fixed-parameter tractable when parameterized in this way. In various applied settings, problem inputs often consist in part of multisets of integers or multisets of weighted objects (such as edges in a graph, or jobs to be scheduled). Such number-of-numbers parameterized problems often reduce to subproblems about transition systems of various kinds, parameterized by the size of the system description. We consider several core problems of this kind relevant to number-of-numbers parameterization. Our main hardness result considers the problem: given a non-deterministic Mealy machine M (a finite state automaton outputting a letter on each transition), an input word x, and a census requirement c for the output word specifying how many times each letter of the output alphabet should be written, decide whether there exists a computation of M reading x that outputs a word y that meets the requirement c. We show that this problem is hard for W[1]. If the question is whether there exists an input word x such that a computation of M on x outputs a word that meets c, the problem becomes fixed-parameter tractable.

Several width measures for digraphs have been proposed in the last few years. However, none of them possess all the “nice” properties of treewidth, namely, (1) being algorithmically useful, that is, admitting polynomial-time algorithms for a large class of problems on digraphs of bounded width; and (2) having nice structural properties such as being monotone under taking subdigraphs and some form of arc contractions. As for (1), MSO₁ is the least common denominator of all reasonably expressive logical languages that can speak about the edge/arc relation on the vertex set, and so it is quite natural to demand efficient solvability of all MSO₁-definable problems in this context. (2) is a necessary condition for a width measure to be characterizable by some version of the cops-and-robber game characterizing treewidth. More specifically, we introduce a notion of a directed topological minor and argue that it is the weakest useful notion of minors for digraphs in this context. Our main result states that any reasonable digraph measure that is algorithmically useful and structurally nice cannot be substantially different from the treewidth of the underlying undirected graph.

Given a graph G = (V,E) and an integer k, an edge modification problem for a graph property \({\it \Pi}\) consists in deciding whether there exists a set of edges F of size at most k such that the graph \(H=(V,E\vartriangle F)\) satisfies the property \({\it \Pi}\). In the \({\it \Pi}\) edge-completion problem, the set F of edges is constrained to be disjoint from E; in the \({\it \Pi}\) edge-deletion problem, F is a subset of E; no constraint is imposed on F in the \({\it \Pi}\) edge-editing problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity. When parameterized by the size k of the edge set F, it has been proved that if \({\it \Pi}\) is an hereditary property characterized by a finite set of forbidden induced subgraphs, then the three \({\it \Pi}\) edge-modification problems are FPT [4]. It was then natural to ask [4] whether these problems also admit a polynomial size kernel. Using recent lower bound techniques, Kratsch and Wahlström answered this question negatively [15]. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths and pointed out that the problem is already open in the case of P ₄-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that parameterized cograph edge modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for P _l -free and C _l -free edge deletion problems for large enough l.

The NP-hard general factor problem asks, given a graph and for each vertex a list of integers, whether the graph has a spanning subgraph where each vertex has a degree that belongs to its assigned list. The problem remains NP-hard even if the given graph is bipartite with partition U ⊎ V, and each vertex in U is assigned the list {1}; this subproblem appears in the context of constraint programming as the consistency problem for the extended global cardinality constraint. We show that this subproblem is fixed-parameter tractable when parameterized by the size of the second partite set V. More generally, we show that the general factor problem for bipartite graphs, parameterized by |V |, is fixed-parameter tractable as long as all vertices in U are assigned lists of length 1, but becomes W[1]-hard if vertices in U are assigned lists of length at most 2. We establish fixed-parameter tractability by reducing the problem instance to a bounded number of acyclic instances, each of which can be solved in polynomial time by dynamic programming.

The Grundy number of a graph G, denoted by \({\it \Gamma} (G)\), is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. Trivially \({\it \Gamma(G)\leq \Delta(G)+1}\). In this paper, we show that deciding if \({\it \Gamma(G)\leq \Delta(G)}\) is NP-complete. We then show that deciding if \({\it \Gamma(G)\geq \mid V(G)\mid-k}\) is fixed parameter tractable with respect to the parameter k.

We consider weighted counting of independent sets using a rational weight x: Given a graph with n vertices, count its independent sets such that each set of size k contributes x ^k . This is equivalent to computation of the partition function of the lattice gas with hard-core self-repulsion and hard-core pair interaction. We show the following conditional lower bounds: If counting the satisfying assignments of a 3-CNF formula in n variables (#3SAT) needs time 2^Ω(n) (i.e. there is a c > 0 such that no algorithm can solve #3SAT in time 2 ^cn ), counting the independent sets of size n/3 of an n-vertex graph needs time 2^Ω(n) and weighted counting of independent sets needs time \(2^{\Omega(n/\log^3 n)}\) for all rational weights x ≠ 0.

We have two technical ingredients: The first is a reduction from 3SAT to independent sets that preserves the number of solutions and increases the instance size only by a constant factor. Second, we devise a combination of vertex cloning and path addition. This graph transformation allows us to adapt a recent technique by Dell, Husfeldt, and Wahlén which enables interpolation by a family of reductions, each of which increases the instance size only polylogarithmically.

We show that for every probability p with 0 < p < 1, computation of all-terminal graph reliability with edge failure probability p requires time exponential in \({\it \Omega}(m/\log^2 m)\) for simple graphs of m edges under the Exponential Time Hypothesis.

Inclusion/exclusion branching is a way to branch on requirements imposed on problems, in contrast to the classical branching on parts of the solution. The technique turned out to be useful for finding and counting (minimum) dominating sets (van Rooij et al., ESA 2009). In this paper, we extend the technique to the setting where one is given a set of properties and seeks (or wants to count) solutions that have at least a given number of these properties. Using this extension, we obtain new algorithms for Partial Dominating Set and the parameterised problem k -Set Splitting. In particular, we apply the new idea to the fastest polynomial space algorithm for counting dominating sets, and directly obtain a polynomial space algorithm for Partial Dominating Set with the same running time (up to a linear factor). Combining the new idea with some previous work, we also give a polynomial space algorithm for k -Set Splitting that improves the fastest known result significantly.

The coverability and boundedness problems for Petri nets are known to be Expspace-complete. Given a Petri net, we associate a graph with it. With the vertex cover number k of this graph and the maximum arc weight W as parameters, we show that coverability and boundedness are in ParaPspace. This means that these problems can be solved in space \(\mathcal{O}(ef(k,W)poly(n))\) where ef(k,W) is some exponential function and \(\mathrm{\mathit{poly}}(n)\) is some polynomial in the size of the input. We then extend the ParaPspace result to model checking a logic that can express some generalizations of coverability and boundedness.

Deleting a minimum number of vertices from a graph to obtain a proper interval graph is an NP-complete problem. At WG 2010 van Bevern et al. gave an O((14k + 14) ^k + 1 kn ⁶) time algorithm by combining iterative compression, branching, and a greedy algorithm. We show that there exists a simple greedy O(n + m) time algorithm that solves the Proper Interval Vertex Deletion problem on \(\{claw,net,\allowbreak tent,\allowbreak C_4,C_5,C_6\}\)-free graphs. Combining this with branching on the forbidden structures \(claw,net,tent,\allowbreak C_4,C_5,\) and C ₆ enables us to get an O(kn ⁶ 6 ^k ) time algorithm for Proper Interval Vertex Deletion, where k is the number of deleted vertices.