Search

The classic K-CYCLE problem asks if a graph G, with vertex-set V(G), has a simple cycle containing all vertices of a given set K⊆V(G). In terms of colored graphs, it can be rephrased as follows: Given a graph G, a set K⊆V(G) and an injective coloring c:K→{1,2,...,|K|}, decide if G has a simple cycle containing each color in {1,2,...,|K|} exactly once. Another problem widely known since the introduction of color coding is COLORFUL CYCLE. Given a graph G and a coloring c:V(G)→{1,2,...,k} for some k∈N, it asks if G has a simple cycle of length k containing each color in {1,2,...,k} exactly once. We study a generalization of these problems: Given a graph G, a set K⊆V(G), a list-coloring L:K→2{1,2,...,k∗} for some k∗∈N and a parameter k∈N, LISTK-CYCLE asks if one can assign a color to each vertex in K so that G has a simple cycle (of arbitrary length) containing exactly k vertices from K with distinct colors. We design a randomized algorithm for LISTK-CYCLE running in time 2knO(1) on an n-vertex graph, matching the best known running times of algorithms for both K-CYCLE and COLORFUL CYCLE. Moreover, unless the Set Cover Conjecture is false, our algorithm is essentially optimal. We also study a variant of LISTK-CYCLE that generalizes the classic HAMILTONICITY problem, where one specifies the size of a solution. Our results integrate three related algebraic approaches, introduced by Björklund, Husfeldt and Taslaman (SODA'12), Björklund, Kaski and Kowalik (STACS'13), and Björklund (FOCS'10). [ABSTRACT FROM AUTHOR]

In the DIRECTED FEEDBACK VERTEX SET (DFVS) problem, we are given a digraph D on n vertices and a positive integer k, and the objective is to check whether there exists a set of vertices S such that F = D − S is an acyclic digraph. In a recent paper, Mnich and van Leeuwen [STACS 2016 ] studied the kernelization complexity of DFVS with an additional restriction on F—namely that F must be an out-forest, an out-tree, or a (directed) pumpkin—with an objective of shedding some light on the kernelization complexity of the DFVS problem, a well known open problem in the area. The vertex deletion problems corresponding to obtaining an out-forest, an out-tree, or a (directed) pumpkin are OUT-FOREST/OUT-TREE/PUMPKIN VERTEX DELETION SET, respectively. They showed that OUT-FOREST/OUT-TREE/PUMPKIN VERTEX DELETION SET admit polynomial kernels. Another open problem regarding DFVS is that, does DFVS admit an algorithm with running time 2O(k)nO(1)? We complement the kernelization programme of Mnich and van Leeuwen by designing fast FPT algorithms for the above mentioned problems. In particular, we design an algorithm for OUT-FOREST VERTEX DELETION SET that runs in time O(2.732knO(1)) and algorithms for PUMPKIN/OUT-TREE VERTEX DELETION SET that runs in time O(2.562knO(1)). As a corollary of our FPT algorithms and the recent result of Fomin et al. [STOC 2016] which gives a relation between FPT algorithms and exact algorithms, we get exact algorithms for OUT-FOREST/OUT-TREE/PUMPKIN VERTEX DELETION SET that run in time O(1.633nnO(1)), O(1.609nnO(1)) and O(1.609nnO(1)), respectively. [ABSTRACT FROM AUTHOR]

A well known result in graph algorithms, due to Edmonds, states that given a digraph D and a positive integer $$\ell $$ , we can test whether D contains $$\ell $$ arc-disjoint out-branchings in polynomial time. However, if we ask whether there exists an out-branching and an in-branching which are arc-disjoint, then the problem becomes NP-complete. In fact, even deciding whether a digraph D contains an out-branching which is arc-disjoint from some spanning tree in the underlying undirected graph remains NP-complete. In this paper we formulate some natural optimization questions around these problems and initiate its study in the realm of parameterized complexity. More precisely, the problems we study are the following: Arc- Disjoint Branchings and Non- Disconnecting Out- Branching. In Arc- Disjoint Branchings ( Non- Disconnecting Out- Branching), a digraph D and a positive integer k are given as input and the goal is to test whether there exist an out-branching and in-branching (respectively, a spanning tree in the underlying undirected graph) that differ on at least k arcs. We obtain the following results for these problems. The algorithm for Non- Disconnecting Out- Branching runs in time $$2^{\mathcal {O}(k)}n^{\mathcal {O}(1)}$$ and the approach we use to obtain this algorithms seems useful in designing other moderately exponential time algorithms for edge/arc partitioning problems. [ABSTRACT FROM AUTHOR]

It is known that the problem of deleting at most κ vertices to obtain a proper interval graph (Proper Interval Vertex Deletion) is fixed parameter tractable. However, whether the problem admits a polynomial kernel or not was open. Here, we answer this question in the affirmative by obtaining a polynomial kernel for Proper Interval Vertex Deletion. This resolves an open question of van Bevern et al. [Graph-Theoretic Concepts in Computer Science (WG 2010), Lecture Notes in Comput. Sci. 6410, Springer, Berlin, 2010, pp. 232-243]. [ABSTRACT FROM AUTHOR]

We give substantially improved exact exponential-time algorithms for a number of NP-hard problems. These algorithms are obtained using a variety of techniques. These techniques include: obtaining exact algorithms by enumerating maximal independent sets in a graph, obtaining exact algorithms from parameterized algorithms and a variant of the usual branch-and-bound technique which we call the "colored" branch-and-bound technique. These techniques are simple in that they avoid detailed case analyses and yield algorithms that can be easily implemented. We show the power of these techniques by applying them to several NP-hard problems and obtaining new improved upper bounds on the running time. The specific problems that we tackle are: (1) the Odd Cycle Transversal problem in general undirected graphs, (2) the Feedback Vertex Set problem in directed graphs of maximum degree 4, (3) Feedback Arc Set problem in tournaments, (4) the 4-Hitting Set problem and (5) the Minimum Maximal Matching and the Edge Dominating Set problems. The algorithms that we present for these problems are the best known and are a substantial improvement over previous best results. For example, for the Minimum Maximal Matching we give an O*(1.4425n) algorithm improving the previous best result of O*(1.4422m) [35]. For the Odd Cycle Transversal problem, we give an O*(1.62n) algorithm which improves the previous time bound of O*(1.7724n) [3]. [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]

The Cycle Packing problem asks whether a given undirected graph G = (V;E) con- tains k vertex-disjoint cycles. Since the publication of the classic Erd}os{Posa theorem in 1965, this problem received significant attention in the fields of graph theory and algorithm design. In particu- lar, this problem is one of the first problems studied in the framework of parameterized complexity. The nonuniform fixed-parameter tractability of Cycle Packing follows from the Robertson{Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time 2O(k2) jV j using exponential space. In the case a solu- tion exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a 2O(k log2 k) jV j-time (deterministic) algorithm using exponential space, which is a consequence of the Erd}os{Posa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on parameterized complexity. Yet, no algorithm that runs in time 2o(k log2 k) jV jO(1), beating the bound 2O(k log2 k) jV jO(1), has been found. In light of this, it seems natural to ask whether the 2O(k log2 k) jV jO(1) bound is essentially optimal. In this paper, we answer this question negatively by developing a 2 O(k log2 k log log k) jV j-time (deterministic) algorithm for Cycle Packing. In the case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound 2O(k log2 k) jV jO(1), our algorithm runs in time linear in jV j, and its space complexity is polynomial in the input size. [ABSTRACT FROM AUTHOR]

VERTEX COVER is one of the most well studied problems in the realm of parameterized algorithms. It admits a kernel with O(ℓ2) edges and 2ℓ vertices where ℓ denotes the size of the vertex cover we are seeking for. A natural question is whether VERTEX COVER is fixed-parameter tractable or admits a polynomial kernel with respect to a parameter k, that is, provably smaller than the size of the vertex cover. Jansen and Bodlaender [STACS 2011, TOCS 2013] raised this question and gave a kernel for VERTEX COVER of size O(f3), where f is the size of a feedback vertex set of the input graph. We continue this line of work and study VERTEX COVER with respect to a parameter that is always smaller than the solution size and incomparable to the size of the feedback vertex set of the input graph. Our parameter is the number of vertices whose removal results in a graph of maximum degree two. While vertex cover with this parameterization can easily be shown to be fixed-parameter tractable (FPT), we show that it has a polynomial kernel. The input to our problem consists of an undirected graph G, S⊆V(G) such that |S|=k and G[V(G)∖S] has maximum degree at most two and a positive integer ℓ. Given (G,S,ℓ), in polynomial time we output an instance (G′,S′,ℓ′) such that |V(G′)| is O(k5), |E(G′)| is O(k6) and G has a vertex cover of size at most ℓ if and only if G′ has a vertex cover of size at most ℓ′. When G[V(G)∖S] has maximum degree at most one, we improve the known kernel bound from O(k3) vertices to O(k2) vertices (and O(k3) edges). More generally, given (G,S,ℓ) where every connected component of G∖S is a clique of at most d vertices (for constant d), in polynomial time, we output an equivalent instance (G′,S′,ℓ′) for the same problem where |V(G′)| is O(kd). We also show that for this problem, when d≥3, a kernel with O(kd−ε) bits cannot exist for any ε>0 unless NP⊆coNP/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]

Abstract: We present a polynomial time algorithm that for any graph G and integer , either finds a spanning tree with at least k internal vertices, or outputs a new graph on at most 3k vertices and an integer such that G has a spanning tree with at least k internal vertices if and only if has a spanning tree with at least internal vertices. In other words, we show that the Maximum Internal Spanning Tree problem parameterized by the number of internal vertices k has a 3k-vertex kernel. Our result is based on an innovative application of a classical min–max result about hypertrees in hypergraphs which states that “a hypergraph H contains a hypertree if and only if H is partition-connected.” [Copyright &y& Elsevier]

We show that for a fixed r, the number of maximal r-regular induced subgraphs in any graph with n vertices is upper bounded by O(cn), where c is a positive constant strictly less than 2. This bound generalizes the well-known result of Moon and Moser, who showed an upper bound of 3n/3 on the number of maximal independent sets of a graph on n vertices. We complement this upper bound result by obtaining an almost tight lower bound on the number of (possible) maximal r-regular induced subgraphs possible in a graph on n vertices. Our upper bound results are algorithmic. That is, we can enumerate all the maximal r-regular induced subgraphs in time (cnnO(1)). A related question is that of finding a maximum-sized r-regular induced subgraph. Given a graph G =(V,E) on n vertices, the Maximum r-Regular Induced Subgraph (M-r-RIS) problem asks for a maximum-sized subset of vertices, R ⊆ V, such that the induced subgraph on R is r-regular. As a by-product of the enumeration algorithm, we get a O (cn) time algorithm for this problem for any fixed constant r, where c is a positive constant strictly less than 2. Furthermore, we use the techniques and results obtained in the paper to obtain improved exact algorithms for a special case of the Induced Subgraph Isomorphism problem, namely, the Induced r-Regular Subgraph Isomorphism problem, where r is a constant, the δ-Separating Maximum Matching problem and the Efficient Edge Dominating Set problem. [ABSTRACT FROM AUTHOR]

We introduce a generic approach for counting subgraphs in a graph. The main idea is to relate counting subgraphs to counting graph homomorphisms. This approach provides new algorithms and unifies several well-known results in algorithms and combinatorics, including the recent algorithm of Björklund, Husfeldt, and Koivisto for computing the chromatic polynomial, the classical algorithm of Kohn et al. for counting Hamiltonian cycles, Ryser's formula for counting perfect matchings of a bipartite graph, and color-coding-based algorithms of Alon, Yuster, and Zwick. By combining our method with known combinatorial bounds, ideas from succinct data structures, partition functions, and the color coding technique, we obtain the following new results. The number of optimal bandwidth permutations of a graph on n vertices excluding a fixed graph as a minor can be computed in time 2n+o(n)), in particular, in time O(2nn³) for trees and in time 2n+O(√n) for planar graphs. Counting all maximum planar subgraphs, subgraphs of bounded genus, or more generally subgraphs excluding a fixed graph M as a minor can be done in 2O(n) time. Counting all subtrees with a given maximum degree (a generalization of counting Hamiltonian paths) of a given graph can be done in time 2O(n). A generalization of Ryser's formula is, Let G be a graph with an independent set of size I. Then the number of perfect matchings in G can be found in time O(2n-ℓn³). Let H be a graph class excluding a fixed graph M as a minor. Then the maximum number of vertex disjoint subgraphs from H in a graph G on n vertices can be found in time 2O(n). In order to show this, we prove that there exists a constant CM depending only on M such that the number of nonisomorphic n-vertex graphs in H is at most cnM. Let F be a k-vertex graph of treewidth t and let G be an n-vertex graph. A subgraph of G isomorphic to F (if one exists) can be found in O(4.32k⋅k⋅t⋅nt+1) expected time using O(log k ⋅ nt+1 space. [ABSTRACT FROM AUTHOR]

A graph is König-Egerváry if the size of a minimum vertex cover equals that of a maximum matching in the graph. These graphs have been studied extensively from a graph-theoretic point of view. In this paper, we introduce and study the algorithmic complexity of finding König-Egerváry subgraphs of a given graph. In particular, given a graph G and a nonnegative integer k, we are interested in the following questions: We show that these problems are NP-complete and study their complexity from the points of view of approximation and parameterized complexity. Towards this end, we first study the algorithmic complexity of Above Guarantee Vertex Cover, where one is interested in minimizing the additional number of vertices needed beyond the maximum matching size for the vertex cover. Further, while studying the parameterized complexity of the problem of deleting k vertices to obtain a König-Egerváry graph, we show a number of interesting structural results on matchings and vertex covers which could be useful in other contexts. [ABSTRACT FROM AUTHOR]

Abstract: Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well-known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets. In this paper we study partial covering problems in graphs in the realm of parameterized complexity. Classical (non-partial) version of all these problems has been intensively studied in planar graphs and in graphs excluding a fixed graph H as a minor. However, the techniques developed for parameterized version of non-partial covering problems cannot be applied directly to their partial counterparts. The approach we use, to show that various partial covering problems are fixed parameter tractable on planar graphs, graphs of bounded local treewidth and graph excluding some graph as a minor, is quite different from previously known techniques. The main idea behind our approach is the concept of implicit branching. We find implicit branching technique to be interesting on its own and believe that it can be used for some other problems. [Copyright &y& Elsevier]

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]

A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k , whether it is possible to transform one into the other by a sequence of vertex additions/deletions such that each intermediate set remains a feasible solution of size bounded by k . We study reconfiguration variants of two classical vertex-subset problems, namely Independent Set and Dominating Set . We denote the former by Image 1 and the latter by Image 2 . Both Image 1 and Image 2 are PSPACE -complete on graphs of bounded bandwidth and W[1] -hard parameterized by k on general graphs. We show that Image 1 is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere dense. For Image 2 , we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques. [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]

Many problems on graphs can be expressed in the following language: given a graph G = ( V , E ) and a terminal set T ⊆ V , find a minimum size set S ⊆ V which intersects all “structures” (such as cycles or paths) passing through the vertices in T . We refer to this class of problems as terminal set problems. In this paper, we introduce a general method to obtain faster exact exponential time algorithms for several terminal set problems. In the process, we break the O ⁎ ( 2 n ) barrier for the classic Node Multiway Cut , Directed Unrestricted Node Multiway Cut and Directed Subset Feedback Vertex Set problems. [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]

The Disjoint Paths Problem asks, given a graph G and a set of pairs of terminals ( s 1 , t 1 ) , … , ( s k , t k ) , whether there is a collection of k pairwise vertex-disjoint paths linking s i and t i , for i = 1 , … , k . In their f ( k ) ⋅ n 3 algorithm for this problem, Robertson and Seymour introduced the irrelevant vertex technique according to which in every instance of treewidth greater than g ( k ) there is an “irrelevant” vertex whose removal creates an equivalent instance of the problem. This fact is based on the celebrated Unique Linkage Theorem , whose – very technical – proof gives a function g ( k ) that is responsible for an immense parameter dependence in the running time of the algorithm. In this paper we give a new and self-contained proof of this result that strongly exploits the combinatorial properties of planar graphs and achieves g ( k ) = O ( k 3 / 2 ⋅ 2 k ) . Our bound is radically better than the bounds known for general graphs. [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]

We obtain asymptotically tight algorithmic bounds for Max-Cut and Edge Dominating Set problems on graphs of bounded clique-width. We show that on an n-vertex graph of clique-width t both problems (1) cannot be solved in time f(t)no(t) for any function f of t unless exponential time hypothesis fails, and (2) can be solved in time nO(t). [ABSTRACT FROM AUTHOR]

The c-pumpkin is the graph with two vertices linked by c ≥ 1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time 2...(κ)(n...(1) deciding, for any fixed c ≥ 1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex SET, which correspond to the cases c = 1, 2 respectively. Finally, we present an ...(log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint c-pumpkin-models. [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]

Abstract: In this article we provide hardness results and approximation algorithms for the following three natural degree-constrained subgraph problems, which take as input an undirected graph . Let be a fixed integer. The () problem takes as additional input a weight function , and asks for a subset such that the subgraph induced by is connected, has maximum degree at most , and is maximized. The Minimum Subgraph of Minimum Degree () problem involves finding a smallest subgraph of with minimum degree at least . Finally, the Dual Degree-dense -Subgraph () problem consists in finding a subgraph of such that and the minimum degree in is maximized. [Copyright &y& Elsevier]

Abstract: Many local search algorithms are based on searching in the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a naïve brute-force search of the k-exchange neighborhood requires time, which is not practical even for very small values of k. We show that for several classes of sparse graphs, including planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the k-exchange neighborhood for many problems can be found much more efficiently. Our algorithms run in time , where τ is a function depending only on k and c is a constant independent of k and n. We demonstrate the applicability of this approach on a variety of problems including r-Center, Vertex Cover, Odd Cycle Transversal, Max-Cut, and Min-Bisection. In particular, on planar graphs, all our algorithms searching for a k-local improvement run in time , which is polynomial for . We complement these fixed-parameter tractable algorithms for k-local search with parameterized intractability results indicating that brute-force search is unavoidable in more general classes of graphs. [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: A tournament is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance on vertices. In fact, given any fixed , the kernelized instance has at most vertices. Our result improves the previous known bound of on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST. [Copyright &y& Elsevier]

Abstract: In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph. [1.] The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors . The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors , for each vertex, so that the obtained coloring of G is proper. We show that this problem is -hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be -hard, parameterized by treewidth. [2.] An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for , parameterized by the treewidth plus the number of colors. We also show that a list-based variation, List Equitable Coloring is -hard for forests, parameterized by the number of colors on the lists. [3.] The list chromatic number of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list of colors, where each list has length at least r, there is a choice of one color from each vertex list yielding a proper coloring of G. We show that the problem of determining whether , the List Chromatic Number problem, is solvable in linear time on graphs of constant treewidth. [ABSTRACT FROM AUTHOR]