Search

In the deletion version of the list homomorphism problem, we are given graphs G and H, a list $$L(v)\subseteq V(H)$$ for each vertex $$v\in V(G)$$ , and an integer k. The task is to decide whether there exists a set $$W \subseteq V(G)$$ of size at most k such that there is a homomorphism from $$G {\setminus } W$$ to H respecting the lists. We show that DL-Hom( $${H}$$ ), parameterized by k and | H|, is fixed-parameter tractable for any $$(P_6,C_6)$$ -free bipartite graph H; already for this restricted class of graphs, the problem generalizes Vertex Cover, Odd Cycle Transversal, and Vertex Multiway Cut parameterized by the size of the cutset and the number of terminals. We conjecture that DL-Hom( $${H}$$ ) is fixed-parameter tractable for the class of graphs H for which the list homomorphism problem (without deletions) is polynomial-time solvable; by a result of Feder et al. (Combinatorica 19(4):487-505, 1999), a graph H belongs to this class precisely if it is a bipartite graph whose complement is a circular arc graph. We show that this conjecture is equivalent to the fixed-parameter tractability of a single fairly natural satisfiability problem, Clause Deletion Chain-SAT. [ABSTRACT FROM AUTHOR]

We consider an augmentation problem on undirected and directed graphs, where given a directed (an undirected) graph G and p pairs of vertices $$P=\left\{ {\left( {s_1 ,t_1 } \right) ,\ldots ,\left( {s_p ,t_p } \right) } \right\} $$ , one has to find the minimum weight set of arcs (edges) to be added to the graph so that the resulting graph has (can be oriented to have) directed paths between the specified pairs of vertices. In the undirected case, we present an FPT-algorithm with respect to the number of new edges. Also, we have implemented and evaluated the algorithm on some real-world networks to show its efficiency in decreasing the size of input graphs and converting them to much smaller kernels. In the directed case, we consider the complexity of the problem with respect to the various parameters and present some parameterized algorithms and parameterized complexity results for it. [ABSTRACT FROM AUTHOR]

We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we study the kernelization algorithms for several parameterized problems, including Parameterized Co-Path Set problem, Parameterized Path-Contractibility problem and Parameterized Connected Dominating Set on G 7 Graphs problem. Based on simple observations, we give simple kernelization algorithms with kernel sizes 4 k , 3 k + 4 , and O ( k 2 ) , respectively, which improves the previous best results 6 k , 5 k + 3 , and O ( k 3 ) , respectively. [ABSTRACT FROM AUTHOR]

Network reconfiguration is an important research topic in the planning and operation of power distribution networks. In this paper, we study the partition problem on trees with supply and demand from parameterized computation perspective. We analyze the relationship between supply nodes and demand nodes, and give four reduction rules, which result in a kernel of size O ( k 2 ) for the problem. Based on branching technique, a parameterized algorithm of running time O ⁎ ( 2.828 k ) is presented. [ABSTRACT FROM AUTHOR]

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G1, G2, either concludes that one of these graphs has treewidth at least k or determines whether G1 and G2 are isomorphic. The running time of the algorithm on an n-vertex graph is ...⋅n5, and this is the first fixed-parameter algorithm for GRAPH ISOMORPHISM parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in ...⋅n5 time that, for a given graph G on n vertices, either concludes that the treewidth of G is at least k or (i) finds in an isomorphic-invariant way a graph c(G) that is isomorphic to G; (ii) finds an isomorphism-invariant construction term--an algebraic expression that encodes G together with a tree decomposition of G of width less than k. Hence, the isomorphism test reduces to verifying whether the computed isomorphic copies or the construction terms for G1 and G2 are equal. [ABSTRACT FROM AUTHOR]

A computerized workflow management system may enforce a security policy, specified in terms of authorized actions and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of a security policy may mean that a workflow is unsatisfiable, in the sense that it is impossible to find a valid plan (an assignment of steps to authorized users such that all constraints are satisfied). Work in the literature focuses on the workflow satisfiability problem, a decision problem that outputs a valid plan if the instance is satisfiable (and a negative result otherwise). In this paper, we introduce the BI-OBJECTIVE WORKFLOW SATISFIABILITY PROBLEM (BO-WSP), which enables us to solve optimization problems related to workflows and security policies. In particular, we are able to compute a "least bad" plan when some components of the security policy may be violated. In general, BO-WSP is intractable from both the classical and parameterized complexity point of view (where the parameter is the number of steps). We prove that computing a Pareto front for BO-WSP is fixed-parameter tractable (FPT) if we restrict our attention to user-independent constraints. This result has important practical consequences, since most constraints of practical interest in the literature are user-independent. Our proof is constructive and defines an algorithm, the implementation of which we describe and evaluate. We also present a second algorithm to compute a Pareto front which solves multiples instances of a related problem using mixed integer programming (MIP).We compare the performance of both our algorithms on synthetic instances, and show that the FPT algorithm outperforms the MIP-based one by several orders of magnitude on most instances. Finally, we study the important question of workflow resiliency and prove new results establishing that known decision problems are fixed-parameter tractable when restricted to user-independent constraints.We then propose a new way of modeling the availability of users and demonstrate that many questions related to resiliency in the context of this new model may be reduced to instances of BO-WSP. [ABSTRACT FROM AUTHOR]

A 2-club is a graph of diameter at most two. In the decision version of the 2-Club Cluster Edge Deletion problem, an undirected graph G is given along with an integer k≥0 as parameter, and the question is whether G can be transformed into a disjoint union of 2-clubs by deleting at most k edges. A simple fixed-parameter algorithm solves the problem in O ⁎ (3 k) , and a decade-old algorithm improved this running to O ⁎ (2.74 k) time via a more sophisticated case analysis. Unfortunately, this latter algorithm is shown to have a flawed branching scenario. A fixed-parameter algorithm that breaks the 3 k barrier is presented in this paper, with a running time in O ⁎ (2.692 k). This also improves the previously claimed running time. [ABSTRACT FROM AUTHOR]

In the Vertex Cover Reconfiguration (VCR) problem, given a graph G, positive integers k and ℓ and two vertex covers S and T of G of size at most k, we determine whether S can be transformed into T by a sequence of at most ℓ vertex additions or removals such that every operation results in a vertex cover of size at most k. Motivated by results establishing the W [ 1 ] -hardness of VCR when parameterized by ℓ, we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR remains W [ 1 ] -hard on bipartite graphs, is NP -hard, but fixed-parameter tractable on (regular) graphs of bounded degree and more generally on nowhere dense graphs and is solvable in polynomial time on trees and (with some additional restrictions) on cactus graphs.

Given a graph G = ( V , E ) of order n and an n -dimensional non-negative vector d = ( d ( 1 ) , d ( 2 ) , … , d ( n ) ) , called demand vector, the vector domination (resp., total vector domination) is the problem of finding a minimum S ⊆ V such that every vertex v in V ∖ S (resp., in V ) has at least d ( v ) neighbors in S . The (total) vector domination is a generalization of many dominating set type problems, e.g., the (total) dominating set problem, the (total) k -dominating set problem (this k is different from the solution size), and so on, and subexponential fixed-parameter algorithms with respect to solution size for apex-minor-free graphs (so for planar graphs) are known. In this paper, we consider maximization versions of the problems; that is, for a given integer k , the goal is to find an S ⊆ V with size k that maximizes the total sum of satisfied demands. For these problems, we design subexponential fixed-parameter algorithms with respect to k for apex-minor-free graphs. [ABSTRACT FROM AUTHOR]

Given a finite set X , a collection T of rooted phylogenetic trees on X and an integer k , the Hybridization Number problem asks if there exists a phylogenetic network on X that displays all trees from T and has reticulation number at most k . We show two kernelization algorithms for Hybridization Number , with kernel sizes 4 k ( 5 k ) t and 20 k 2 ( Δ + − 1 ) respectively, with t the number of input trees and Δ + their maximum outdegree. Experiments on simulated data demonstrate the practical relevance of our kernelization algorithms. In addition, we present an n f ( k ) t -time algorithm, with n = | X | and f some computable function of k . [ABSTRACT FROM AUTHOR]

We introduce a new technique for designing fixed-parameter algorithms for cut problems, called randomized contractions. We apply our framework to obtain the first fixed-parameter algorithms (FPT algorithms) with exponential speed up for the STEINER CUT and NODE MULTIWAY CUT-UNCUT problems. We prove that the parameterized version of the UNIQUE LABEL COVER problem, which is the base of the Unique Games Conjecture, can be solved in 2O(k² log ∣Σ∣)n4 log n deterministic time (even in the stronger, vertex-deletion variant), where k is the number of unsatisfied edges and ∣Σ∣ is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of UNIQUE GAMES where the number of edges allowed not to be satisfied is upper bounded by O(√log n) to optimality, which improves over the trivial O(1) upper bound. We prove that the Steiner Cut problem can be solved in 2O(k² log k)n4 log n deterministic time and Õ(2O(k² log k)n²) randomized time, where k is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup presented at FOCS'11. We show how to combine considering "cut" and "uncut" constraints at the same time. More precisely, we define a robust problem, NODE MULTIWAY CUT-UNCUT, that can serve as an abstraction of introducing uncut constraints and show that it admits an algorithm running in 2O(k² log k)n4 log n deterministic time, where k is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan, and Razgon [ACM Trans. Algorithms, 9 (2013), 30], which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle positive real weights. [ABSTRACT FROM AUTHOR]

We study a real-life modification of the classical house-swapping problem that is motivated by the existence of engaged pairs and divorcing couples. We show that the problem of finding a new house for the maximum number of agents is inapproximable, but fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

The NP-complete Permutation Pattern Matching problem asks whether a k-permutation P is contained in a n-permutation T as a pattern. This is the case if there exists an order-preserving embedding of P into T. In this paper, we present a fixed-parameter algorithm solving this problem with a worst-case runtime of $${\mathcal O}(1.79^{\mathsf {run}(T)}\cdot n\cdot k)$$ , where $$\mathsf {run}(T)$$ denotes the number of alternating runs of T. This algorithm is particularly well-suited for instances where T has few runs, i.e., few ups and downs. Moreover, since $$\mathsf {run}(T)

The NP-hard Distinct Vectors problem asks to delete as many columns as possible from a matrix such that all rows in the resulting matrix are still pairwise distinct. Our main result is that, for binary matrices, there is a complexity dichotomy for Distinct Vectors based on the maximum ( H ) and the minimum ( h ) pairwise Hamming distance between matrix rows: Distinct Vectors can be solved in polynomial time if H ≤ 2 ⌈ h / 2 ⌉ + 1 , and is NP-complete otherwise. Moreover, we explore connections of Distinct Vectors to hitting sets, thereby providing several fixed-parameter tractability and intractability results also for general matrices. [ABSTRACT FROM AUTHOR]

Co-clustering, that is partitioning a numerical matrix into "homogeneous" submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard, as well as a number of relevant polynomial-time solvable special cases, thus charting the border of tractability for this challenging data clustering problem. For instance, we provide polynomial-time solvability when having to partition the rows and columns into two subsets each (meaning that one obtains four submatrices). When partitioning rows and columns into three subsets each, however, we encounter NP-hardness, even for input matrices containing only values from f0, 1, 2g. [ABSTRACT FROM AUTHOR]

We present efficient fixed-parameter and approximation algorithms for the NP-hard problem of computing a maximum agreement forest (MAF) of a pair of multifurcating (nonbinary) rooted trees. Multifurcating trees arise naturally as a result of statistical uncertainty in current tree construction methods. The size of an MAF corresponds to the subtree prune-and-regraft distance of the two trees and is intimately connected to their hybridization number. These distance measures are essential tools for understanding reticulate evolution, such as lateral gene transfer, recombination, and hybridization. Our algorithms nearly match the running times of the currently best algorithms for the binary case. This is achieved using a combination of efficient branching rules (similar to but more complex than in the binary case) and a novel edge protection scheme that further reduces the size of the search space the algorithms need to explore. [ABSTRACT FROM AUTHOR]

We study parameterized complexity of a generalization of the classical Feedback Vertex Set problem, namely the Group Feedback Vertex Set problem: we are given a graph $$G$$ with edges labeled with group elements, and the goal is to compute the smallest set of vertices that hits all cycles of $$G$$ that evaluate to a non-null element of the group. This problem generalizes not only Feedback Vertex Set, but also Subset Feedback Vertex Set, Multiway Cut and Odd Cycle Transversal . Completing the results of Guillemot (Discrete Optim 8(1):61-71, ), we provide a fixed-parameter algorithm for the parameterization by the size of the cutset only. Our algorithm works even if the group is given as a blackbox performing group operations. [ABSTRACT FROM AUTHOR]

Optimal Morse matchings reveal essential structures of cell complexes that lead to powerful tools to study discrete geometrical objects, in particular, discrete 3-manifolds. However, such matchings are known to be NP-hard to compute on 3-manifolds through a reduction to the erasability problem. Here, we refine the study of the complexity of problems related to discrete Morse theory in terms of parameterized complexity. On the one hand, we prove that the erasability problem is W[P]-complete on the natural parameter. On the other hand, we propose an algorithm for computing optimal Morse matchings on triangulations of 3-manifolds, which is fixed-parameter tractable in the treewidth of the bipartite graph representing the adjacency of the 1- and 2-simplices. This algorithm also shows fixed-parameter tractability for problems such as erasability and maximum alternating cycle-free matching. We further show that these results are also true when the treewidth of the dual graph of the triangulated 3-manifold is bounded. Finally, we discuss the topological significance of the chosen parameters and investigate the respective treewidths of simplicial and generalized triangulations of 3-manifolds. [ABSTRACT FROM AUTHOR]

We investigate the problem of orienting the edges of an embedded graph in such a way that the resulting digraph fulfills given in-degree specifications both for the vertices and for the faces of the embedding. This primal-dual orientation problem was first proposed by Frank for the case of planar graphs, in conjunction with the question for a good characterization of the existence of such orientations. We answer this question by showing that a feasible orientation of a planar embedding, if it exists, can be constructed by combining certain parts of a primally feasible orientation and a dually feasible orientation. For the general case of arbitrary embeddings, we show that the number of feasible orientations is bounded by $$2^{2g}$$ , where $$g$$ is the genus of the embedding. Our proof also yields a fixed-parameter algorithm for determining all feasible orientations parameterized by the genus. In contrast to these positive results, however, we also show that the problem becomes $$N\!P$$ -complete even for a fixed genus if only upper and lower bounds on the in-degrees are specified instead of exact values. [ABSTRACT FROM AUTHOR]

The article examines the parameterized complexity of the restriction of the Test Cover problem (T-r-C) in which each edge possesses a maximum of r ≥ 2 vertices. It states that two below-bound parameterizations of T-r-C are fixed-parameter tractable with polynomial kernels: deciding if a test cover of size n - k exists, and deciding if a test cover of size m - k exists where k is the parameter. It also talks about the lower bound on the minimum size of test covers.

Fixed-parameter tractability analysis and scheduling are two core domains of combinatorial optimization which led to deep understanding of many important algorithmic questions. However, even though fixed-parameter algorithms are appealing for many reasons, no such algorithms are known for many fundamental scheduling problems. In this paper we present the first fixed-parameter algorithms for classical scheduling problems such as makespan minimization, scheduling with job-dependent cost functions-one important example being weighted flow time-and scheduling with rejection. To this end, we identify crucial parameters that determine the problems' complexity. In particular, we manage to cope with the problem complexity stemming from numeric input values, such as job processing times, which is usually a core bottleneck in the design of fixed-parameter algorithms. We complement our algorithms with $$\mathsf {W[1]}$$ -hardness results showing that for smaller sets of parameters the respective problems do not allow fixed-parameter algorithms. In particular, our positive and negative results for scheduling with rejection explore a research direction proposed by Dániel Marx. [ABSTRACT FROM AUTHOR]

Flood-It is a combinatorial problem on a colored graph whose aim is to make the graph monochromatic using the minimum number of flooding moves , relatively to a pivot vertex p . A flooding move consists of changing the color of the monochromatic component (maximal monochromatic connected subgraph) containing p . This problem generalizes a combinatorial game named alike which is played on m × n grids. It is known that Flood-It remains NP-hard even for 3 × n grids and for instances with bounded number of colors, diameter, or treewidth. In contrast, in this work we show that Flood-It is fixed-parameter tractable when parameterized by the vertex cover number, and admits a polynomial kernelization when, besides the vertex cover number, the number of colors is an additional parameter. [ABSTRACT FROM AUTHOR]

Every graph property expressible in monadic second-order (MSO) logic, can be checked in linear time on graphs of bounded tree-width by means of finite automata running on terms denoting tree-decompositions. Implementing these automata is difficult because of their huge sizes. Fly-automata (FA) are deterministic automata that compute the necessary states and transitions when running (instead of looking into tables ); they overcome this difficulty. Previously, we constructed FA to check MSO properties of graphs of bounded clique-width . An MSO property with edge quantifications (called an MSO 2 property) is an MSO property of the incidence graph and, graphs of tree-width k have incidence graphs of clique-width O ( k ) . Our existing constructions can be used for MSO 2 properties of graphs of bounded tree-width. We examine concrete aspects of this adaptation. [ABSTRACT FROM AUTHOR]

We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded disjoint paths modulator number (these are each time the respective parameters). Moreover, we obtain that 'only' asking for perfect stable matchings or the mere existence of a stable matching is fixed-parameter tractable with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number. [ABSTRACT FROM AUTHOR]