Search

In the Arc Disjoint Cycle Packing problem, we are given a simple directed graph (digraph) G, a positive integer k, and the task is to decide whether there exist k arc disjoint cycles. The problem is known to be W[1]-hard on general digraphs parameterized by the standard parameter k. In this paper we show that the problem admits a polynomial kernel on α-bounded digraphs. That is, we give a polynomial-time algorithm, that given an instance (D,k) of Arc Disjoint Cycle Packing, outputs an equivalent instance (D ′ , k ′) of Arc Disjoint Cycle Packing, such that k ′ ≤ k and the size of D ′ is upper-bounded by a polynomial function of k. For any integer α ≥ 1, the class of α-bounded digraphs, denoted by D α , contains a digraph D such that the maximum size of an independent set in D is at most α. That is, in D, any set of α + 1 vertices has an arc with both end-points in the set. For α = 1, this corresponds to the well-studied class of tournaments. Our results generalize the recent result by Bessy et al. [MFCS, 2019] about Arc Disjoint Cycle Packing on tournaments. [ABSTRACT FROM AUTHOR]

For a family of graphs G , the G - Contraction problem takes as an input a graph G and an integer k , and the goal is to decide if there exists a subset F ⊆ E (G) of size at most k such that G / F is in G. Here, G / F is the graph obtained from G by contracting all the edges in F. In this article, we initiate the study of Grid Contraction from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time 2 O (k) ⋅ | V (G) | O (1) , for this problem. We complement this result by proving that unless ETH fails, there is no algorithm for Grid Contraction with running time 2 o (k) ⋅ | V (G) | O (1). We also present a polynomial kernel for this problem. [ABSTRACT FROM AUTHOR]

In the Maximum Degree Contraction problem, the input is a graph G on n vertices, and integers k, d, and the objective is to check whether G can be transformed into a graph of maximum degree at most d, using at most k edge contractions. A simple brute-force algorithm that checks all possible sets of edges for a solution runs in time n O (k) . As our first result, we prove that this algorithm is asymptotically optimal, upto constants in the exponents, under Exponential Time Hypothesis (ETH). Belmonte, Golovach, van't Hof, and Paulusma studied the problem in the realm of parameterized complexity and proved, among other things, that it admits an FPT algorithm running in time (d + k) 2 k · n O (1) = 2 O (k log (k + d)) · n O (1) , and remains NP-hard for every constant d ≥ 2 (Acta Informatica (2014)). We present a different FPT algorithm that runs in time 2 O (d k) · n O (1) . In particular, our algorithm runs in time 2 O (k) · n O (1) , for every fixed d. In the same article, the authors asked whether the problem admits a polynomial kernel, when parameterized by k + d . We answer this question in the negative and prove that it does not admit a polynomial compression unless NP ⊆ coNP / p o l y . [ABSTRACT FROM AUTHOR]

Every connected graph on n vertices has a cut of size at least n − 1. We call this bound the spanning tree bound. In the Max-Cut Above Spanning Tree (Max-Cut-AST) problem, we are given a connected n-vertex graph G and a non-negative integer k, and the task is to decide whether G has a cut of size at least n − 1 + k. We show that Max-Cut-AST admits an algorithm that runs in time O (8 k n O (1)) , and hence it is fixed parameter tractable with respect to k. Furthermore, we show that Max-Cut-AST has a polynomial kernel of size O (k 5) . [ABSTRACT FROM AUTHOR]

In this paper we continue our study of graph modification problems defined by reducing the rank of the adjacency matrix of the given graph, and extend our results from undirected graphs to modifying the rank of skew-adjacency matrix of oriented graphs. An instance of a graph modification problem takes as input a graph G and a positive integer k, and the objective is to either delete k vertices/edges or edit k edges so that the resulting graph belongs to a particular family F of graphs. Given a fixed positive integer r, we define Fr as the family of oriented graphs where for each G∈Fr, the rank of the skew-adjacency matrix of G is at most r. Using the family Fr we do algorithmic study, both in classical and parameterized complexity, of the following graph modification problems: r-RANK VERTEX DELETION, r-RANK EDGE DELETION. We first show that both the problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2O(klogr)nO(1) for r-RANK VERTEX DELETION, and an algorithm for r-RANK EDGE DELETION running in time 2O(f(r)klogk)nO(1). In addition to our FPT results we design polynomial kernels for these problems. Our main structural result, which is the fulcrum of all our algorithmic results, is that for a fixed integer r the size of any “reduced graph” in Fr is upper bounded by 3r. This result is of independent interest and generalizes a similar result of Kotlov and Lovász regarding reduced oriented graphs of rank r. [ABSTRACT FROM AUTHOR]

The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph G and a non-negative integer k, the objective is to test whether there exists a subset S ⊆ V (G) of size at most k such that G - S is a forest. After a long line of improvement, recently, Li and Nederlof [TALG, 2022] designed a randomized algorithm for the problem running in time O ⋆ (2. 7 k) ∗ . In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set S should be an independent set in G), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in G - S has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph G and non-negative integers k , ℓ ∈ N , and the objective is to test whether there exists a vertex subset S of size at most k, such that G - S is ℓ edges away from a forest. In this paper, using the methodology of Li and Nederlof [TALG, 2022], we obtain the current fastest algorithms for all these problems. In particular we obtain the following randomized algorithms. Independent Feedback Vertex Set can be solved in time O ⋆ (2. 7 k) . Pseudo Forest Deletion can be solved in time O ⋆ (2. 85 k) . Almost Forest Deletion can be solved in time O ⋆ (min { 2. 85 k · 8. 54 ℓ , 2. 7 k · 36. 61 ℓ , 3 k · 1. 78 ℓ }) . [ABSTRACT FROM AUTHOR]

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid M , a weight function ω : E (M) → N , and integers k ≥ 1 , d ≥ 1 . The task is to decide if there is a collection of k bases B 1 , ⋯ , B k of M such that the weight of the symmetric difference of any pair of these bases is at least d . The input to the Weighted Diverse Common Independent Sets problem consists of two matroids M 1 , M 2 defined on the same ground set E , a weight function ω : E → N , and integers k ≥ 1 , d ≥ 1 . The task is to decide if there is a collection of k common independent sets I 1 , ⋯ , I k of M 1 and M 2 such that the weight of the symmetric difference of any pair of these sets is at least d . The input to the Diverse Perfect Matchings problem consists of a graph G and integers k ≥ 1 , d ≥ 1 . The task is to decide if G contains k perfect matchings M 1 , ⋯ , M k such that the symmetric difference of any two of these matchings is at least d . We show that none of these problems can be solved in polynomial time unless P = NP . We derive fixed-parameter tractable ( FPT ) algorithms for all three problems with (k , d) as the parameter, and present a p o l y (k , d) -sized kernel for Weighted Diverse Bases. [ABSTRACT FROM AUTHOR]

A class domination coloring (also called cd-Coloring or dominated coloring) of a graph is a proper coloring in which every color class is contained in the neighborhood of some vertex. The minimum number of colors required for any cd-coloring of G , denoted by χ c d (G) , is called the class domination chromatic number (cd-chromatic number) of G. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph G on n vertices, find its cd-chromatic number. (2) Given a graph G and integers k and q , can we delete at most k vertices such that the cd-chromatic number of the resulting graph is at most q ? For the first problem, we give an exact algorithm with running time O (2 n n 4 log n). Also, we show that the problem is FPT with respect to the number q of colors as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with O (q 3) vertices. For the second (deletion) problem, we show NP -hardness for each q ≥ 2. Further, on split graphs, we show that the problem is NP -hard if q is a part of the input and FPT with respect to k and q as combined parameters. As recognizing graphs with cd-chromatic number at most q is NP -hard in general for q ≥ 4 , the deletion problem is unlikely to be FPT when parameterized by the size of the deletion set on general graphs. We show fixed parameter tractability for q ∈ { 2 , 3 } using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines. • An exact algorithm that runs in time O (2 n n 4 log n). • An FPT algorithm parameterized by the number of colors and the treewidth. • FPT algorithms when input graph is restricted to special graph classes. • 3 - cd-Coloring is FPT parameterized by the solution size. [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 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]

FEEDBACK VERTEX SET (FVS) is one of the most well-studied problems in the realm of parameterized complexity. In this problem we are given a graph G and a positive integer k and the objective is to test whether there exists S ⊆ V (G) of size at most k such that G - S is a forest. Thus, FVS is about deleting as few vertices as possible to get a forest. The main goal of this paper is to study the following interesting problem: How can we generalize the family of forests such that the nice structural properties of forests and the interesting algorithmic properties of FVS can be extended to problems on this class? Toward this we define a graph class, F1, that contains all graphs where each connected component can be transformed into a forest by deleting at most l edges. A graph in the class F1 is known as pseudoforest in the literature and we call a graph in Fl an l-pseudoforest. We study the problem of deleting k vertices to get into Fl, l-PSEUDOFOREST DELETION, in the realm of parameterized complexity. We show that l-PSEUDOFOREST DELETION admits an algorithm with running time clknO(1) and admits a kernel of size f(l)k2. Thus, for every fixed l we have a kernel of size O(k2). That is, we get a uniform polynomial kernel for l-pseudoforest Deletion. Our algorithms and uniform kernels involve the use of the expansion lemma and protrusion machinery. [ABSTRACT FROM AUTHOR]

We investigate the parameterized complexity of Generalized Red Blue Set Cover ( Gen-RBSC), a generalization of the classic Set Cover problem and the more recently studied Red Blue Set Cover problem. Given a universe U containing b blue elements and r red elements, positive integers $$k_\ell $$ and $$k_r$$ , and a family $$\mathcal F $$ of $$\ell $$ sets over U, the Gen-RBSC problem is to decide whether there is a subfamily $$\mathcal F '\subseteq \mathcal F $$ of size at most $$k_\ell $$ that covers all blue elements, but at most $$k_r$$ of the red elements. This generalizes Set Cover and thus in full generality it is intractable in the parameterized setting. In this paper, we study a geometric version of this problem, called Gen-RBSC-lines, where the elements are points in the plane and sets are defined by lines. We study this problem for an array of parameters, namely, $$k_\ell , k_r, r, b$$ , and $$\ell $$ , and all possible combinations of them. For all these cases, we either prove that the problem is W-hard or show that the problem is fixed parameter tractable (FPT). In particular, on the algorithmic side, our study shows that a combination of $$k_\ell $$ and $$k_r$$ gives rise to a nontrivial algorithm for Gen-RBSC-lines. On the hardness side, we show that the problem is para-NP-hard when parameterized by $$k_r$$ , and W[1]-hard when parameterized by $$k_\ell $$ . Finally, for the combination of parameters for which Gen-RBSC-lines admits FPT algorithms, we ask for the existence of polynomial kernels. We are able to provide a complete kernelization dichotomy by either showing that the problem admits a polynomial kernel or that it does not contain a polynomial kernel unless $$\text {co{-}NP}\subseteq \text {NP}/\text{ poly }$$ . [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]

In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G \ S is a tree. The problem is NP-complete and even NP-hard to approximate within any factor of OPTc for any constant c. In this paper we give an O(k5) size kernel for the Tree Deletion Set problem. An appealing feature of our kernelization algorithm is a new reduction rule, based on systems of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate. [ABSTRACT FROM AUTHOR]

In the Directed Feedback Arc (Vertex) Set problem, we are given a digraph D with vertex set V( D) and arcs set A( D) and a positive integer k, and the question is whether there is a subset X of arcs (vertices) of size at most k such that the digraph obtained after deleting X from D is an acyclic digraph. In this paper we study these two problems in the realm of parametrized and kernelization complexity. More precisely, for these problems we give polynomial time algorithms, known as kernelization algorithms, on several digraph classes that given an instance ( D, k) of the problem returns an equivalent instance $$(D',k')$$ such that the size of $$D'$$ and $$k'$$ is at most $$k^{O(1)}$$ . We extend previous results for Directed Feedback Arc (Vertex) Set on tournaments to much larger and well studied classes of digraphs. Specifically we obtain polynomial kernels for k-FVS on digraphs with bounded independence number, locally semicomplete digraphs and some totally $$\Phi $$ -decomposable digraphs, including quasi-transitive digraphs. We also obtain polynomial kernels for k-FAS on some totally $$\Phi $$ -decomposable digraphs, including quasi-transitive digraphs. Finally, we design a subexponential algorithm for k-FAS running in time $$2^{O(\sqrt{k} (\log k)^c)}n^d$$ for constants c, d. on locally semicomplete digraphs. [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]

The b-Exact Multicover problem takes a universe U of n elements, a family F of m subsets of U, a function dem : U → { 1 , ... , b } and a positive integer k, and decides whether there exists a subfamily(set cover) F ′ of size at most k such that each element u ∈ U is covered by exactly dem(u) sets of F ′ . The b-Exact Coverage problem also takes the same input and decides whether there is a subfamily F ′ ⊆ F such that there are at least k elements that satisfy the following property: u ∈ U is covered by exactly dem(u) sets of F ′ . Both these problems are known to be NP-complete. In the parameterized setting, when parameterized by k, b-Exact Multicover is W[1]-hard even when b = 1. While b-Exact Coverage is FPT under the same parameter, it is known to not admit a polynomial kernel under standard complexity-theoretic assumptions, even when b = 1. In this paper, we investigate these two problems under the assumption that every set satisfies a given geometric property π. Specifically, we consider the universe to be a set of n points in a real space ℝ d , d being a positive integer. When d = 2 we consider the problem when π requires all sets to be unit squares or lines. When d > 2, we consider the problem where π requires all sets to be hyperplanes in ℝ d . These special versions of the problems are also known to be NP-complete. When parameterized by k, the b-Exact Coverage problem has a polynomial size kernel for all the above geometric versions. The b-Exact Multicover problem turns out to be W[1]-hard for squares even when b = 1, but FPT for lines and hyperplanes. Further, we also consider the b-Exact Max. Multicover problem, which takes the same input and decides whether there is a set cover F ′ such that every element u ∈ U is covered by at least dem(u) sets and at least k elements satisfy the following property: u ∈ U is covered by exactly dem(u) sets of F ′ . To the best of our knowledge, this problem has not been studied before, and we show that it is NP-complete (even for the case of lines). In fact, the problem turns out to be W[1]-hard in the general setting, when parameterized by k. However, when we restrict the sets to lines and hyperplanes, we obtain FPT algorithms. [ABSTRACT FROM AUTHOR]

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]

In the EDGE EDITING TO CONNECTED f-Degree Graph problem we are given a graph G, an integer fc, and a function f assigning integers to vertices of G. The task is to decide whether there is a connected graph F on the same vertex set as G, such that for every vertex v, its degree in F is f(v), and the number of edges in E(G)ΔE(F), the symmetric difference of E(G) and E(F), is at most k. We show that Edge EDITING TO CONNECTED f-DEGREE GRAPH is fixed- parameter tractable (FPT) by providing an algorithm solving the problem on an n-vertex graph in time2O(k)nO(1). We complement this result by showing that the weighted version of the problem with costs 1 and 0 is W[l]-hard when parameterized by k and the maximum value of f even when the input graph is a tree. Our FPT algorithm is based on a nontrivial combination of color-coding and fast computations of representative families over the direct sum matroid of l-elongation of the co-graphic matroid associated with G and a uniform matroid over the set of nonedges of G. We believe that this combination could be useful in designing parameterized algorithms for other edge editing and connectivity problems. [ABSTRACT FROM AUTHOR]

In the Shortest Superstring problem we are given a set of strings $$S=\{s_1, \ldots , s_n\}$$ and integer $$\ell $$ and the question is to decide whether there is a superstring s of length at most $$\ell $$ containing all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time $$2^{\mathcal {O}(k)} {\text {poly}}(n)$$ finds a superstring of length at most $$\ell $$ containing at least k strings of S. We complement this by a lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about 'below guaranteed values' parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization 'below matching' is hard. [ABSTRACT FROM AUTHOR]

Let $${\mathcal {F}}$$ be a family of graphs. Given an n-vertex input graph G and a positive integer k, testing whether G has a vertex subset S of size at most k, such that $$G-S$$ belongs to $${\mathcal {F}}$$ , is a prototype vertex deletion problem. These type of problems have attracted a lot of attention in recent times in the domain of parameterized complexity. In this paper, we study two such problems; when $${\mathcal {F}}$$ is either the family of forests of cacti or the family of forests of odd-cacti. A graph H is called a forest of cacti if every pair of cycles in H intersect on at most one vertex. Furthermore, a forest of cacti H is called a forest of odd cacti, if every cycle of H is of odd length. Let us denote by $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ , the families of forests of cacti and forests of odd cacti, respectively. The vertex deletion problems corresponding to $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with worst case run time $$12^k n^{\mathcal {O}(1)}$$ for both these problems. Our algorithms considerably improve the running time for Diamond Hitting Set and Even Cycle Transversal, compared to what is known about them. [ABSTRACT FROM AUTHOR]

In the Subset Odd Cycle Transversal (Subset OCT) problem, the input is a graph G, a subset of vertices T and a positive integer k and the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle containing a vertex from T. Clearly, Subset OCT is a generalization of the classic Odd Cycle Transversal problem where the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle in the given graph. We remark that Subset OCT also generalizes the well known Multiway Cut problem, as well as a parity constrained variant, the Odd Multiway Cut problem. Recently, Kakimura, Kawarabayashi, and Kobayashi [Proceedings of SODA, 2012, pp. 1726{1736] proposed a fixed parameter tractable (FPT) algorithm for this problem that runs in time ƒ(k)mn³ using the theory of graph minors, where ƒ is some function, and n and m denote the number of vertices and edges in the graph. However, the dependence of this function on k is at least triple exponential. In this paper, we give the first FPT algorithm for this problem where the exponential dependence of the running time of the algorithm on k is polynomial. Our algorithm avoids the use of the theory of graph minors, is self contained, and runs in time 2O(k³ log k)mn² log² n, thus improving upon the algorithm of Kakimura and co-authors with respect to both the parameter as well as the input size. Our algorithm utilizes a recursive application of "generalized" important separators to reduce the subset version of this problem to the standard version of the problem. [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 study a general class of problems called F-DELETION problems. In an F-DELETION problem, we are asked whether a subset of at most k vertices can be deleted from a graph G such that the resulting graph does not contain as a minor any graph from the family F of forbidden minors. We study the problem parameterized by k, using p-F-DELETION to refer to the parameterized version of the problem. We obtain a number of algorithmic results on the p-F-DELETION problem when F contains a planar graph. We give a linear vertex kernel on graphs excluding t-claw K1,t, the star with t leaves, as an induced subgraph, where t is a fixed integer and an approximation algorithm achieving an approximation ratio of O(log3/2 OPT), where OPT is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when F only contains graph θc as a minor for a fixed integer c. The graph θc consists of two vertices connected by c parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as VERTEX COVER, FEEDBACK VERTEX SET, and DIAMOND HITTING SET. The generic kernelization algorithm is based on a nontrivial application of protrusion techniques, previously used only for problems on topological graph classes. [ABSTRACT FROM AUTHOR]

Let η≥0 be an integer and G be a graph. A set X⊆ V( G) is called a η- treewidth modulator in G if G∖ X has treewidth at most η. Note that a 0-treewidth modulator is a vertex cover, while a 1-treewidth modulator is a feedback vertex set of G. In the η/ ρ- Treewidth Modulator problem we are given an undirected graph G, a ρ-treewidth modulator X⊆ V( G) in G, and an integer ℓ and the objective is to determine whether there exists an η-treewidth modulator Z⊆ V( G) in G of size at most ℓ. In this paper we study the kernelization complexity of η/ ρ- Treewidth Modulator parameterized by the size of X. We show that for every fixed η and ρ that either satisfy 1≤ η< ρ, or η=0 and 2≤ ρ, the η/ ρ- Treewidth Modulator problem does not admit a polynomial kernel unless NP⊆coNP/poly. This resolves an open problem raised by Bodlaender and Jansen (STACS, pp. 177-188, ). Finally, we complement our kernelization lower bounds by showing that ρ/0- Treewidth Modulator admits a polynomial kernel for any fixed ρ. [ABSTRACT FROM AUTHOR]

According to the classical Erdős-Pósa theorem, given a positive integer k, every graph G either contains k vertex disjoint cycles or a set of at most [ABSTRACT FROM AUTHOR]

Abstract: Given a permutation π of and a positive integer k, can π be partitioned into at most k subsequences, each of which is either increasing or decreasing? We give an algorithm with running time that solves this problem, thereby showing that it is fixed parameter tractable. This NP-complete problem is equivalent to deciding whether the cochromatic number of a given permutation graph on n vertices is at most k. Our algorithm solves in fact a more general problem: within the mentioned running time, it decides whether the cochromatic number of a given perfect graph on n vertices is at most k. To obtain our result we use a combination of two well-known techniques within parameterized algorithms: iterative compression and greedy localization. Consequently we name this combination “iterative localization”. We further demonstrate the power of this combination by giving an algorithm with running time that decides whether a given set of n non-overlapping axis-parallel rectangles can be stabbed by at most k of a given set of horizontal and vertical lines. [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]