Search

In this paper we study a generalization of classic Feedback Vertex Set problem in the realm of multivariate complexity analysis. We say that a graph F is an l -forest if we can delete at most l edges from F to get a forest. That is, F is at most l edges away from being a forest. In this paper we introduce the Almost Forest Deletion problem, where given a graph G and integers k and l , the question is whether there exists a subset of at most k vertices such that its deletion leaves us an l -forest. We show that this problem admits an algorithm with running time 2 O ( k + l ) n O ( 1 ) and a kernel of size O ( k l ( k + l ) ) . We also show that the problem admits a 2 O ( tw ) n O ( 1 ) algorithm on bounded treewidth graphs, using which we design a subexponential algorithm for the problem on planar graphs. [ABSTRACT FROM AUTHOR]

Abstract: The parameterized feedback vertex (arc) set problem is to find whether there are k vertices (arcs) in a given graph whose removal makes the graph acyclic. The parameterized complexity of this problem in general directed graphs is a long standing open problem. We investigate the problems on tournaments, a well studied class of directed graphs. We consider both weighted and unweighted versions. We also address the parametric dual problems which are also natural optimization problems. We show that they are fixed parameter tractable not just in tournaments but in oriented directed graphs (where there is at most one directed arc between a pair of vertices). More specifically, the dual problem we show fixed parameter tractable are: Given an oriented directed graph, is there a subset of k vertices (arcs) that forms an acyclic directed subgraph of the graph? Our main results include: [ ] an 1 [1] is the exponent of the best matrix multiplication algorithm. algorithm for weighted feedback vertex set problem, and an algorithm for weighted feedback arc set problem in tournaments; [ ] an algorithm for the dual of feedback vertex set problem (maximum vertex induced acyclic graph) in oriented directed graphs, and an algorithm for the dual of feedback arc set problem (maximum arc induced acyclic graph) in general directed graphs. We also show that the dual of feedback vertex set is —hard in general directed graphs and the feedback arc set problem is fixed parameter tractable in dense directed graphs. Our results are the first non-trivial results for these problems. [Copyright &y& Elsevier]

We study a set of voting problems where given an election E = (C , Π V) (where C is the set of candidates and Π V is a set of votes), and a non-empty subset of candidates J , the question under consideration is: Can we modify the election in a way so that none of the candidates in J wins the election? The modification operations allowed are that of either adding or deleting some candidates. Yang and Wang (2017) [44] introduced these problems as the Resolute Control problem , a generalization of the destructive control problem where J is a singleton. They studied parameterized complexity of Resolute Control for voting rules Borda (both addition and deletion), Maximin (addition), and Copeland (both addition and deletion). They primarily consider | J | as parameter. In this paper we study Resolute Control parameterized by the other natural parameters viz., the number of candidates added or deleted. We show that the Resolute Control for Borda (both addition and deletion), Maximin (addition) and Copeland (deletion) are W[2]-hard. We complement this by showing that when the number of voters is odd, Copeland (deletion) is FPT parameterized by the sum of the number of deleted candidates and the size of the feedback arc set of the majority graph of the election. [ABSTRACT FROM AUTHOR]

Balanced Stable Marriage (BSM) is a central optimization version of the classic Stable Marriage (SM) problem. We study BSM from the viewpoint of Parameterized Complexity. Informally, the input of BSM consists of n men, n women, and an integer k. Each person a has a (sub)set of acceptable partners, A (a) , whom a ranks strictly; we use p a (b) to denote the position of b ∈ A (a) in a 's preference list. The objective is to decide whether there exists a stable matching μ such that balance (μ) ≜ max ⁡ { ∑ (m , w) ∈ μ p m (w) , ∑ (m , w) ∈ μ p w (m) } ≤ k. In SM , all stable matchings match the same set of agents, A ⋆ which can be computed in polynomial time. As balance (μ) ≥ | A ⋆ | 2 for any stable matching μ , BSM is trivially fixed-parameter tractable (FPT) with respect to k. Thus, a natural question is whether BSM is FPT with respect to k − | A ⋆ | 2. With this viewpoint in mind, we draw a line between tractability and intractability in relation to the target value. This line separates additional natural parameterizations higher/lower than ours (e.g., we automatically resolve the parameterization k − | A ⋆ | 2). The two extreme stable matchings are the man-optimal μ M and the woman-optimal μ W. Let O M = ∑ (m , w) ∈ μ M p m (w) , and O W = ∑ (m , w) ∈ μ W p w (m). In this work, we prove that • BSM parameterized by t = k − min ⁡ { O M , O W } admits (1) a kernel where the number of people is linear in t , and (2) a parameterized algorithm whose running time is single exponential in t. • BSM parameterized by t = k − max ⁡ { O M , O W } is W[1]-hard. [ABSTRACT FROM AUTHOR]

We know that Tree Contraction does not admit a polynomial kernel unless NP ⊆ coNP/poly , while Path Contraction admits a kernel with O (k) vertices. The starting point of this article is the following natural questions: What is the structure of the family of paths that allows Path Contraction to admit a polynomial kernel? Apart from the size of the solution, what other additional parameters should we consider so we can design polynomial kernels for these basic contraction problems? To design polynomial kernels, we consider the family of trees with the bounded number of leaves (note that the family of paths are trees with at most two leaves). In particular, we study Bounded Tree Contraction. Here, an input is a graph G , integers k and ℓ , and the goal is to decide whether, there is a subset F ⊆ E (G) of size at most k such that G / F is a tree with at most ℓ leaves. We design a kernel with O (k ℓ) vertices and O (k 2 + k ℓ) edges for this problem. We complement this result by giving kernelization lower bound. We also prove similar results for Bounded Out-Tree Contraction and Bounded Cactus Contraction. [ABSTRACT FROM AUTHOR]

Given an undirected graph, its arboricity is the minimum number of edge disjoint forests that its edge set can be partitioned into. We develop the first fully dynamic algorithms to determine the arboricity of a graph under edge insertions and deletions. While our insertion algorithm is based on known static algorithms to determine the arboricity, our deletion algorithm is, to the best of our knowledge, new. Our algorithms take O (m log ⁡ n) time to insert or delete an edge where m is the number of edges in the graph while the best static algorithm to compute arboricity takes O (m 3 / 2 log ⁡ (n 2 / m)) time [9]. We complement our upper bound with a lower bound of amortized Ω (log ⁡ n) time for an update for an algorithm that maintains a forest decomposition of size arboricity of the graph under edge insertions and deletions. [ABSTRACT FROM AUTHOR]

Given a network modeled by a directed graph D = (V , A) , it is natural to ask whether we can partition the vertex set of D into two disjoint subsets V 1 , V 2 (called a 2-partition), such that the digraphs D [ V 1 ] , D [ V 2 ] induced by each of these has one of the two properties of interest. This question gives rise to a rich realm of combinatorial problems. The complexity of many such problems was determined in [2,3]. We analyze a subset of those problems from the viewpoint of parameterized complexity, and present a complete dichotomy of basic, natural properties. More precisely, given a directed graph D = (V , A) and two non-negative integers k 1 and k 2 , we seek a 2-partition (V 1 , V 2) of the vertex set V such that | V 1 | ≥ k 1 , | V 2 | ≥ k 2 , and each of the subdigraphs induced by V 1 and V 2 has a structural property as defined by the problem at hand—for example, D [ V 1 ] is acyclic and D [ V 2 ] is strongly connected. Specifically, we consider the following eight structural properties: being strongly connected; being connected; having an out-branching; having an in-branching; having minimum degree at least one; having minimum semi-degree at least one; being acyclic; and being complete. [ABSTRACT FROM AUTHOR]

An edge-bicolored graph G = ( V , R ∪ B ) is called Red/Blue-split graph if there exists a partition I B and I R of V such that I B and I R are independent sets in ( V , B ) and ( V , R ) , respectively. Red/Blue-split graphs generalize several well studied graph classes including split graphs, bipartite graphs and König–Egerváry graphs. In this paper we consider the algorithmic complexity of various optimization problems like minimum edge (or vertex) deletion and maximum edge (or vertex) induced subgraph related to Red/Blue split graphs. All these problems are NP -hard and thus we look at them from algorithmic paradigms that are meant for coping with NP -hardness. We obtain various hardness as well as algorithmic results for these problems in the realm of approximation algorithms and parameterized complexity. The main tool we use to obtain all our results is polynomial time transformations between appropriate problems. On the way, we also resolve some problems related to inapproximability about certain optimization problems mentioned by Korach et al. (2006) [17] . [ABSTRACT FROM AUTHOR]

The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G , a positive integer k and the objective is to add/delete k vertices (edges) so that the resulting graph belongs to a particular family, F , of graphs. In general the family F is defined by forbidden subgraph/minor characterization. In this paper rather than taking a structural route to define F , we take algebraic route. More formally, given a fixed positive integer r , we define F r as the family of graphs where for each G ∈ F r , the rank of the adjacency matrix of G is at most r . Using the family F r we initiate algorithmic study, both in classical and parameterized complexity, of following graph modification problems: r - Rank Vertex Deletion , r - Rank Edge Deletion and r - Rank Editing . These problems generalize the classical Vertex Cover problem and a variant of the d - Cluster Editing problem. We first show that all the three problems are NP-Complete . Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2 O ( k log ⁡ r ) n O ( 1 ) for r - Rank Vertex Deletion , and an algorithm for r - Rank Edge Deletion and r - Rank Editing running in time 2 O ( f ( r ) k log ⁡ k ) n O ( 1 ) . We complement our FPT result by designing polynomial kernels for these problems. [ABSTRACT FROM AUTHOR]

To introduce our question and the parameterization, consider the classical Vertex Cover problem. In this problem, the input is a graph G on n vertices and a positive integer ℓ , and the goal is to find a vertex subset S of size at most ℓ such that G − S is an independent set. Further, we want that G [ S ] is highly connected. That is, G [ S ] should be n − k edge-connected. Clearly, the problem is NP -complete, as substituting k = n − 1 , we obtain the Connected Vertex Cover problem. A simple observation also shows that the problem admits an algorithm with running time n O (k). Since the problem is polynomial-time solvable for every fixed integer k , a natural parameter is the integer k. In all the problems we consider, the parameter is k , and the goal is to find a solution S of size at most ℓ , such that G [ S ] is n − k edge-connected and G − S satisfies a property. We show that this version of well-known problems such as Vertex Cover , Feedback Vertex Set , Odd Cycle Transversal and Multiway Cut admit an algorithm with running time f (k) ⋅ n O (1) , that is, they are FPT with the parameter k. One of our main subroutines to obtain these algorithms is an FPT algorithm for n − k edge connected Steiner Subgraph , which could be of an independent interest. Finally, we also show that such an algorithm is not possible for Multicut. [ABSTRACT FROM AUTHOR]

A digraph D is singly connected if for all ordered pairs of vertices u , v ∈ V (D) , there is at most one path in D from u to v. In this paper, we study the Singly Connected Vertex Deletion (SCVD) problem: Given an n -vertex digraph D and a positive integer k , does there exist a set S ⊆ V (D) such that | S | ≤ k and D − S is singly connected? This problem may be seen as a directed counterpart of the (Undirected) Feedback Vertex Set problem, as an undirected graph is singly connected if and only if it is acyclic. SCVD is known to be NP -hard on general digraphs. We study the complexity of SCVD on various classes of digraphs such as tournaments, and various generalisations of tournaments such as digraphs of bounded independence number, in- and out-tournaments and local tournaments. We show that unlike the Feedback Vertex Set on Tournaments (FVST) problem, SCVD is polynomial-time solvable on tournaments. In addition, we show that SCVD is polynomial-time solvable on digraphs of bounded independence number, and on the class of acyclic local tournaments. We also study the parameterized complexity of SCVD, with k as the parameter, on the class of in-tournaments. And we show that on in-tournaments, SCVD admits a fixed-parameter tractable algorithm and a quadratic vertex kernel. We also show that on the class of local tournaments, which is a sub-class of in-tournaments, SCVD admits a linear vertex kernel. [ABSTRACT FROM AUTHOR]

In the (Vertex) k -Way Cut problem, input is an undirected graph G , an integer s , and the goal is to find a subset S of edges (vertices) of size at most s , such that G − S has at least k connected components. Downey et al. [Electr. Notes Theor. Comput. Sci. 2003] showed that k -Way Cut is W[1]-hard parameterized by k. However, Kawarabayashi and Thorup [FOCS 2011] showed that the problem is fixed-parameter tractable (FPT) in general graphs with respect to the parameter s and provided a O (s s O (s) n 2) time algorithm, where n denotes the number of vertices in G. The best-known algorithm for this problem runs in time s O (s) n O (1) given by Lokshtanov et al. [ACM Tran. of Algo. 2021]. On the other hand, Vertex k -Way Cut is W[1]-hard with respect to either of the parameters, k or s or k + s. These algorithmic results motivate us to look at the problems on special classes of graphs. In this paper, we consider the (Vertex) k -Way Cut problem on subclasses of chordal graphs and obtain the following results. • We first give a sub-exponential FPT algorithm for k -Way Cut running in time 2 O (s log ⁡ s) n O (1) on chordal graphs. • It is "known" that Vertex k -Way Cut is W[1]-hard on chordal graphs, in fact on split graphs, parameterized by k + s. We complement this hardness result by designing polynomial-time algorithms for Vertex k -Way Cut on interval graphs, circular-arc graphs and permutation graphs. [ABSTRACT FROM AUTHOR]

Abstract: Let be an unweighted connected graph on vertices. We show that an embedding of the shortest path metric of into the line with minimum distortion can be found in time . This is the first algorithm breaking the trivial -barrier. [Copyright &y& Elsevier]

Abstract: We provide polynomial time data reduction rules for Connected Dominating Set on planar graphs and analyze these to obtain a linear kernel for the planar Connected Dominating Set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs. [Copyright &y& Elsevier]

Given a graph G = (V , E) , a subset S ⊆ V (G) is said to be a feedback vertex set of G if G − S is a forest. In the Feedback Vertex Set (FVS) problem, we are given an undirected graph G , and a positive integer k , the question is whether there exists a feedback vertex set of size at most k. In this paper, we study three variants of the FVS problem: Unrestricted Fair FVS , Restricted Fair FVS , and Relaxed Fair FVS. In Unrestricted Fair FVS , we are given a graph G and a positive integer ℓ , the question is does there exist a feedback vertex set S ⊆ V (G) (of any size) such that for every vertex v ∈ V (G) , v has at most ℓ neighbours in S. First, we study Unrestricted Fair FVS from different parameterizations such as treewidth, treedepth, and neighbourhood diversity and obtain several results (both tractability and intractability). Next, we study Restricted Fair FVS , where we are also given an integer k in the input and we demand the size of S to be at most k. This problem is trivially NP-complete; we show that Restricted Fair FVS when parameterized by the solution size k and the maximum degree Δ of the graph G , admits a kernel of size O (Δ k). Finally, we study the Relaxed Fair FVS problem, where we want that the size of S is at most k and for every vertex v outside S , v has at most ℓ neighbours in S. We give an FPT algorithm for Relaxed Fair FVS problem running in time c k n O (1) , for a fixed constant c. [ABSTRACT FROM AUTHOR]

We consider the parameterized complexity of the problem of tracking shortest s - t paths in graphs, motivated by applications in security and wireless networks. Given an undirected and unweighted graph with a source s and a destination t , Tracking Shortest Paths asks if there exists a k -sized subset of vertices (referred to as tracking set) that intersects each shortest s - t path in a distinct set of vertices. We first generalize this problem for set systems, namely Tracking Set System , where given a family of subsets of a universe, we are required to find a subset of elements from the universe that has a unique intersection with each set in the family. Tracking Set System is shown to be fixed-parameter tractable due to its relation with a known problem, Test Cover. By a reduction to the well-studied d -hitting set problem, we give a polynomial (with respect to k) kernel for the case when the set sizes are bounded by d. This also helps in solving Tracking Shortest Paths when the input graph diameter is bounded by d. While the results for Tracking Set System show that Tracking Shortest Paths is fixed-parameter tractable, we also give an independent algorithm by using some preprocessing rules, resulting in an improved running time. [ABSTRACT FROM AUTHOR]

Given a bipartite graph G = (U ⊎ V , E) , a linear representation of the transversal matroid associated with G on the ground set U , can be constructed in randomized polynomial time. In fact one can get a linear representation deterministically in time 2 O (m 2 n) , where m = | U | and n = | V | , by looping through all the choices made in the randomized algorithm. Other important matroids for which one can obtain linear representation deterministically in time similar to the one for transversal matroids include gammoids and strict gammoids. Strict gammoids are duals of transversal matroids and gammoids are restrictions of strict gammoids. We give faster deterministic algorithms to construct linear representations of transversal matroids, gammoids and strict gammoids. All our algorithms run in time ( m r ) m O (1) , where m is the cardinality of the ground set and r is the rank of the matroid. In the language of parameterized complexity, we give an XP algorithm for finding linear representations of transversal matroids, gammoids and strict gammoids parameterized by the rank of the given matroid. [ABSTRACT FROM AUTHOR]

In the Closest String problem we are given an alphabet Σ, a set of strings S = { s 1 , s 2 , … , s k } over Σ such that | s i | = n and an integer d . The objective is to check whether there exists a string s over Σ such that d H ( s , s i ) ≤ d , i ∈ { 1 , … , k } , where d H ( x , y ) denotes the number of places strings x and y differ at. Closest String is a prototype string problem. This problem together with several of its variants such as Distinguishing String Selection and Closest Substring have been extensively studied from parameterized complexity perspective. These problems have been studied with respect to parameters that are combinations of k , d , | Σ | and n . However, surprisingly the kernelization question for these problems (for the versions when they admit fixed-parameter tractable algorithms) is not studied at all. In this paper we fill this gap in the literature and do a comprehensive study of these problems from kernelization complexity perspective. We settle almost all the problems by either obtaining a polynomial kernel or showing that the problem does not admit a polynomial kernel under a standard assumption in complexity theory. [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of NP-hard optimization versions of Stable Matching and Stable Roommates in the presence of ties and incomplete lists. These problems model many real-life situations where solutions have to satisfy certain predefined criterion of suitability and compatibility. Specifically, our objective is to maximize/minimize the size of the stable matching. Our main theorems state that Stable Matching and Stable Roommates admit small kernels. Consequently, we also conclude that Stable Matching is fixed-parameter tractable ( FPT ) with respect to solution size, and that Stable Roommates is FPT with respect to a structural parameter. Finally, we analyze the special case where the input graph is planar. [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of Minimum Volume Packing and Strip Packing . In the two dimensional version the input consists of a set of rectangles S with integer side lengths. In the Minimum Volume Packing problem, given a set of rectangles S and a number k , the goal is to decide if the rectangles can be packed in a bounding box of volume at most k . In the Strip Packing problem we are given a set of rectangles S , numbers W and k ; the objective is to find if all the rectangles can be packed in a box of dimensions W × k . We prove that the 2-dimensional Volume Packing is in FPT by giving an algorithm that runs in ( 2 ⋅ 2 ) k ⋅ k O ( 1 ) time. We also show that Strip Packing is W[1]-hard even in two dimensions and give an FPT algorithm for a special case of Strip Packing . Some of our results hold for the problems defined in higher dimensions as well. [ABSTRACT FROM AUTHOR]

We investigate the effect of certain natural connectivity constraints on the parameterized complexity of two fundamental graph covering problems, namely Vertex Cover and Edge Cover . Specifically, we impose the additional requirement that each connected component of a solution have at least t vertices (resp. edges from the solution) for a fixed positive integer t , and call the problem t - Total Vertex Cover (resp. t - Total Edge Cover ). In both cases the parameter k is the size of the solution. We show that • both problems remain fixed-parameter tractable with these restrictions, with running times of the form O ⋆ ( c k ) for some constant c > 0 in each case, where the O ⋆ notation hides polynomial factors; • for each fixed t ≥ 2 , t - Total Vertex Cover has no polynomial kernel unless CoNP ⊆ NP / poly ; • for each fixed t ≥ 2 , t - Total Edge Cover has a linear vertex kernel of size t + 1 t k . These results significantly improve earlier work on these problems. We illustrate the utility of the technique used to solve t - Total Vertex Cover , by applying it to derive an O ⋆ ( c k ) -time FPT algorithm for the t - Total Edge Dominating Set problem. Our no-poly-kernel result for t - Total Vertex Cover , and the known NP-hardness result for t - Total Edge Cover , are in stark contrast to the fact that Vertex Cover has a 2 k vertex kernel, and that Edge Cover is solvable in polynomial time. This illustrates how even the slightest connectivity requirement results in a drastic change in the tractability of problems—the curse of connectivity! [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we develop approximation algorithms for a few node deletion problems when the input is restricted to be a bipartite graph. We look at node deletion problems for non-trivial properties which can be characterized by forbidden structure which has a bounded intersection with both the bipartitions. The approximation factors obtained directly depend upon the size of the largest such intersection. Special instances of this general problem include problems such as the Minimum Chain Vertex Deletion, Minimum Dissociation Vertex Deletion, Minimum Bipartite Claw Vertex Deletion, Minimum Bi-complement Vertex Deletion and Minimum Bipartite Threshold Vertex Deletion problems. The algorithms are based upon the techniques of linear programming and iterative rounding. We also use the node deletion algorithms to marginally improve the trivial approximation factor for complementary problem of determining the size of the maximum sized vertex induced subgraph lying in the given graph class and prove the APX-completeness of all of these problems. [Copyright &y& Elsevier]

Abstract: In MaxSat, we are given a CNF formula with variables and clauses; the task is to find a truth assignment satisfying the maximum number of clauses. Let be the number of literals in the clauses of . Then is the expected number of clauses satisfied by a random truth assignment, when the truth values to the variables are distributed uniformly and independently. It is well-known that, in polynomial time, one can find a truth assignment satisfying at least clauses. In the parameterized problem MaxSat-AA, we are to decide whether there is a truth assignment satisfying at least clauses, where is the (nonnegative) parameter. We prove that MaxSat-AA is para-NP-complete and thus, MaxSat-AA is not fixed-parameter tractable unless . This is in sharp contrast to the similar problem MaxLin 2-AA which was recently proved to be fixed-parameter tractable by Crowston et al. (FSTTCS 2011). In fact, we consider a more refined version of MaxSat-AA, Max- -Sat-AA, where for each . Alon et al. (SODA 2010) proved that if is a constant, then Max- -Sat-AA is fixed-parameter tractable. We prove that Max- -Sat-AA is para-NP-complete for any . We also prove that assuming the exponential time hypothesis, Max- -Sat-AA is not even in XP for any integral , where is any real-valued unbounded strictly increasing computable function. This lower bound on cannot be decreased much further as we prove that Max- -Sat-AA is (i) in XP for any and (ii) fixed-parameter tractable for any , where is any real-valued unbounded strictly increasing computable function. The proof uses some results on MaxLin 2-AA. [Copyright &y& Elsevier]

Abstract: We investigate a generalization of the classical Feedback Vertex Set (FVS) problem from the point of view of parameterized algorithms. Independent Feedback Vertex Set (IFVS) is the “independent” variant of the FVS problem and is defined as follows: given a graph and an integer , decide whether there exists , , such that is a forest and is an independent set; the parameter is . Note that the similarly parameterized version of the FVS problem–where there is no restriction on the graph –has been extensively studied in the literature. The connected variant CFVS–where is required to be connected–has received some attention as well. The FVS problem easily reduces to the IFVS problem in a manner that preserves the solution size, and so any algorithmic result for IFVS directly carries over to FVS. We show that IFVS can be solved in time, where is the number of vertices in the input graph , and obtain a cubic () kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless . [Copyright &y& Elsevier]

Abstract: We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph and a positive integer , the Bandwidth problem asks whether there exists a bijective function such that for every edge , . It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains -complete. [Copyright &y& Elsevier]

Abstract: Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the Maximum Independent Set problem, a parameterized and a counting version of -Hitting Set and the Maximum Induced Cluster Subgraph problem. [Copyright &y& Elsevier]