Search

We define two new computational problems in the domain of perfect genome rearrangements, and propose three algorithms to solve them. The rearrangement scenarios modeled by the problems consider Reversal and Block Interchange operations, and a PQ-tree is utilized to guide the allowed operations and to compute their weights. In the first problem, Constrained TreeToString Divergence ( CTTSD ), we define the basic structure-informed rearrangement measure. Here, we assume that the gene order members of the gene cluster from which the PQ-tree is constructed are permutations. The PQ-tree representing the gene cluster is ordered such that the series of gene IDs spelled by its leaves is equivalent to that of the reference gene order. Then, a structure-informed genome rearrangement distance is computed between the ordered PQ-tree and the target gene order. The second problem, TreeToString Divergence ( TTSD ), generalizes CTTSD , where the gene order members are not necessarily permutations and the structure informed rearrangement measure is extended to also consider up to d S and d T gene insertion and deletion operations, respectively, when modelling the PQ-tree informed divergence process from the reference gene order to the target gene order. The first algorithm solves CTTSD in O (n γ 2 · (m p · 1. 381 γ + m q)) time and O (n 2) space, where γ is the maximum number of children of a node, n is the length of the string and the number of leaves in the tree, and m p and m q are the number of P-nodes and Q-nodes in the tree, respectively. If one of the penalties of CTTSD is 0, then the algorithm runs in O (n m γ 2) time and O (n 2) space. The second algorithm solves TTSD in O (n 2 γ 2 d T 2 d S 2 m 2 (m p · 5 γ γ + m q)) time and O (d T d S m (m n + 5 γ)) space, where γ is the maximum number of children of a node, n is the length of the string, m is the number of leaves in the tree, m p and m q are the number of P-nodes and Q-nodes in the tree, respectively, and allowing up to d T deletions from the tree and up to d S deletions from the string. The third algorithm is intended to reduce the space complexity of the second algorithm. It solves a variant of the problem (where one of the penalties of TTSD is 0) in O (n γ 2 d T 2 d S 2 m 2 (m p · 4 γ γ 2 n (d T + d S + m + n) + m q)) time and O (γ 2 n m 2 d T d S (d T + d S + m + n)) space. The algorithm is implemented as a software tool, denoted MEM-Rearrange, and applied to the comparative and evolutionary analysis of 59 chromosomal gene clusters extracted from a dataset of 1487 prokaryotic genomes. [ABSTRACT FROM AUTHOR]

Hubs are high-degree nodes within a network, ubiquitous in complex networks such as telecommunication, biological, social and semantic networks. Here, we do not seek a hub that is a single node, but a hub consisting of k nodes. Formally, given a graph G = (V , E) , we a seek a set A ⊆ V of size k that induces a connected subgraph from which at least p edges emanate. Thus, we identify k nodes which can act as a unit (due to the connectivity constraint) that is a hub (due to the cut constraint). This problem, which we call Multi-Node Hub (MNH), is a variant of the classic Max Cut problem. While it is easy to see that MNH is W[1]-hard with respect to the parameter k , our main contribution is a parameterized algorithm that shows that MNH is FPT with respect to the parameter p. [ABSTRACT FROM AUTHOR]

Among the twenty-five papers presented at IPEC, we invited the authors of the papers with the best scores of Program Committee to submit the full extended versions to this volume. We are pleased to present this special issue of Algorithmica dedicated to the 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) which took place September 8-10, 2021. This special issue is a successor of the following special issue volumes of Algorithmica: Volumes 64(1)-2012 and 65(4)-2013 dedicated to IPEC 2010, held in Chennai (India); Volume 71(3)-2015 dedicated to IPEC 2013, held in Sophia Antipolis (France); Volume 75(2)-2016 dedicated to IPEC 2014, held in Wroclaw (Poland); Volume 79(1)-2017 dedicated to IPEC 2015, held in Patras (Greece); Volume 81(2)-2019 dedicated to IPEC 2016, held in Aarhus (Denmark); Volume 81(10)-2019 dedicated to IPEC 2017, held in Vienna (Austria); Volume 82(8)-2020 dedicated to IPEC 2018, held in Helsinki (Finland); Volume 83(8)-2021 dedicated to IPEC 2019, held in Munich (Germany); and Volume 84(8)-2022 dedicated to IPEC 2020, held online. [Extracted from the article]

An important goal in microbial computational genomics is to identify crucial events in the evolution of a gene that severely alter the duplication, loss, and mobilization patterns of the gene within the genomes in which it disseminates. In this article, we formalize this microbiological goal as a new pattern-matching problem in the domain of gene tree and species tree reconciliation, denoted "Reconciliation-Scenario Altering Mutation (RSAM) Discovery." We propose an O (m ⋅ n ⋅ k) time algorithm to solve this new problem, wheremandnare the number of vertices of the input gene tree and species tree, respectively, andkis a user-specified parameter that bounds from above the number of optimal solutions of interest. The algorithm first constructs a hypergraph representing thekhighest scoring reconciliation scenarios between the given gene tree and species tree, and then interrogates this hypergraph for subtrees matching a prespecified RSAM pattern. Our algorithm is optimal in the sense that the number of hypernodes in the hypergraph can be lower bounded by Ω (m ⋅ n ⋅ k). We implement the new algorithm as a tool, called RSAM-finder, and demonstrate its application to the identification of RSAMs in toxins and drug resistance elements across a data set spanning hundreds of species. [ABSTRACT FROM AUTHOR]

MAX-CUT is a well-known classical NP-hard problem. This problem asks whether the vertex-set of a given graph G=(V,E) can be partitioned into two disjoint subsets, A and B, such that there exist at least p edges with one endpoint in A and the other endpoint in B. It is well known that if p≤|E|/2, the answer is necessarily positive. A widely-studied variant of particular interest to parameterized complexity, called (k,n-k)-MAX-CUT, restricts the size of the subset A to be exactly k. For the (k,n-k)-MAX-CUT problem, we obtain an O∗(2p)-time algorithm, improving upon the previous best O∗(4p+o(p))-time algorithm, as well as the first polynomial kernel. Our algorithm relies on a delicate combination of methods and notions, including independent sets, depth-search trees, bounded search trees, dynamic programming and treewidth, while our kernel relies on examination of the closed neighborhood of the neighborhood of a certain independent set of the graph G. [ABSTRACT FROM AUTHOR]

The klam value of an algorithm that runs in time O ∗ ( f ( k ) ) is the maximal value k such that f ( k ) < 1 0 20 . Given a graph G and a parameter k , the k - Leaf Spanning Tree ( k - LST ) problem asks if G contains a spanning tree with at least k leaves. This problem has been extensively studied over the past three decades. In 2000, Fellows et al. (2000) asked whether it admits a klam value of 50. A steady progress towards an affirmative answer continued until 5 years ago, when an algorithm of klam value 37 was discovered. Our contribution is twofold. First, we present an O ∗ ( 3 . 18 8 k ) -time parameterized algorithm for k - LST , which shows that the problem admits a klam value of 39. Second, we rely on an application of the bounded search trees technique where the correctness of rules crucially depends on the history of previously applied rules in a non-standard manner, encapsulated in a “dependency claim”. Similar claims may be used to capture the essence of other complex algorithms in a compact, useful manner. [ABSTRACT FROM AUTHOR]

Problems of genome rearrangement are central in both evolution and cancer. Most evolutionary scenarios have been studied under the assumption that the genome contains a single copy of each gene. In contrast, tumor genomes undergo deletions and duplications, and thus, the number of copies of genes varies. The number of copies of each segment along a chromosome is called its copy number profile (CNP). Understanding CNP changes can assist in predicting disease progression and treatment. To date, questions related to distances between CNPs gained little scientific attention. Here we focus on the following fundamental problem, introduced by Schwarz et al.: given two CNPs, u and v, compute the minimum number of operations transforming u into v, where the edit operations are segmental deletions and amplifications. We establish the computational complexity of this problem, showing that it is solvable in linear time and constant space. [ABSTRACT FROM AUTHOR]

We introduce a multivariate approach for solving weighted parameterized problems. By allowing flexible use of parameters, our approach defines a framework for applying the classic bounded search trees technique. In our model, given an instance of size n of a minimization/maximization problem, and a parameter W ≥ 1 , we seek a solution of weight at most/at least W . We demonstrate the usefulness of our approach in solving Vertex Cover , 3- Hitting Set , Edge Dominating Set and Max Internal Out-Branching . While the best known algorithms for these problems admit running times of the form c W n O ( 1 ) , for some c > 1 , our framework yields running times of the form c s n O ( 1 ) , where s ≤ W is the minimum size of a solution of weight at most/at least W . If no such solution exists, s = min ⁡ { W , m } , where m is the maximum size of a solution. In addition, we analyze the parameter t ≤ s , the minimum size of a solution. [ABSTRACT FROM AUTHOR]

We study a broad class of graph partitioning problems. Each problem is defined by two constants, α and α . The input is a graph G, an integer k and a number p, and the objective is to find a subset $U\subseteq V$ of size k, such that α m + α m is at most (or at least) p, where m , m are the cardinalities of the edge sets having both endpoints, and exactly one endpoint, in U, respectively. This class of fixed-cardinality graph partitioning problems (FGPPs) encompasses Max ( k, n − k)- Cut, Min k- Vertex Cover, k- Densest Subgraph, and k- Sparsest Subgraph. Our main result is a 4Δ⋅ n time algorithm for any problem in this class, where Δ ≥ 1 is the maximum degree in the input graph. This resolves an open question posed by Bonnet et al. (Proc. International Symposium on Parameterized and Exact Computation, 2013). We obtain faster algorithms for certain subclasses of FGPPs, parameterized by p, or by ( k + p). In particular, we give a 4⋅ n time algorithm for Max ( k, n − k)- Cut, thus improving significantly the best known p ⋅ n time algorithm by Bonnet et al. [ABSTRACT FROM AUTHOR]

Over the past few decades, a large body of works studied the (in)tractability of various computational problems on grid graphs, which often yield substantially faster algorithms than general graphs. Unfortunately, the recognition of a grid graph is hard—it was shown to be NP-hard already in 1987. In this paper, we provide several positive results in this regard in the framework of parameterized complexity. Specifically, our contribution is threefold. First, we show that the problem is FPT parameterized by k + mcc where mcc is the maximum size of a connected component of G. Second, we present a new parameterization, denoted a G , relating graph distance to geometric distance. We show that the problem is para-NP-hard parameterized by a G , but FPT parameterized by a G on trees, as well as FPT parameterized by k + a G. Third, we show that the recognition of k × r grid graphs is NP-hard on graphs of pathwidth 2 where k = 3. [ABSTRACT FROM AUTHOR]

In this paper, we employ the multilinear detection technique, combined with proper colorings of graphs, to develop algorithms for two problems in bounded degree graphs. We focus mostly on the k-Internal Out-Branching ( k-IOB) problem, which asks if a given directed graph has an out-branching (i.e., a spanning tree with exactly one node of in-degree 0) with at least k internal nodes. The second problem, k-Tree, asks if a given undirected graph G has a (not necessarily induced) copy of a given tree T. That is, k-Tree asks whether T is a subgraph of G. We present an $$O^*(4^k)$$ time randomized algorithm for k-IOB, which improves the $$O^*$$ running time of the previous best known algorithm for this problem. Then, for directed graphs whose underlying (simple, undirected) graphs have bounded degree $$\varDelta $$ , we modify our algorithm to solve k-IOB in time $$O^*(2^{(2-\frac{\varDelta +1}{\varDelta (\varDelta -1)})k})$$ . For k- Tree in graphs of bounded degree 3, we obtain an $$O^*(1.914^k)$$ time randomized algorithm. In particular, all of our algorithms use polynomial space. [ABSTRACT FROM AUTHOR]

Module Motif is a pattern matching problem that was introduced in the context of biological networks. Informally, given a multiset of colors P and a graph H in which each node is associated with a set of colors, it asks if P occurs in a module of H (i.e., in a set of nodes that have the same neighborhood outside the set). We present three parameterized algorithms for this problem, which both measure similarity between matched colors and handle deletions and insertions of colors to P . Moreover, we observe that the running times of two of them might be essentially tight, and prove that the problem is unlikely to admit a polynomial kernel. [ABSTRACT FROM AUTHOR]

Parameterized Approximation is a topic of considerable interest in the field of Parameterized Complexity. In the past decade, new color coding-related techniques, including the breakthrough representative sets technique, have been proven extremely powerful in the design of fast parameterized algorithms. Furthermore, packing problems, which are often solved via color coding-related techniques, have enjoyed a race towards obtaining the fastest parameterized algorithms that solve them. Therefore, it is natural to ask whether packing problems admit efficient parameterized approximation algorithms. In this paper, we answer this question affirmatively. We present tradeoffs that improve the running times of algorithms for well-known special cases of the 3 -Set k -Packing problem at the cost of their accuracy. Consider a packing problem for which there is no known algorithm with approximation ratio α , and a parameter k . If the value of an optimal solution is at least k , we seek a solution of value at least αk ; otherwise, we seek an arbitrary solution. Clearly, if the best known parameterized algorithm that finds a solution of value t runs in time O ⁎ ( f ( t ) ) for some function f , we are interested in running times better than O ⁎ ( f ( α k ) ) . Our main contribution lies in the adaptation of notions fundamental to the representative sets technique to the design of approximation algorithms: We introduce the definition of “approximate lopsided universal sets”, combine partial executions of representative sets-based algorithms with approximation algorithms, and adapt the iterative expansion framework (in the context of representative sets) to the design of parameterized approximation algorithms. Our ideas are intuitive, and may be relevant to the design of other parameterized approximation algorithms. [ABSTRACT FROM AUTHOR]

Given a matroid M = ( E , I ) , and a family S of p -subsets of E , a subfamily S ˆ ⊆ S represents S if for any X ∈ S and Y ⊆ E ∖ X satisfying X ∪ Y ∈ I , there is a set X ˆ ∈ S ˆ disjoint from Y , where X ˆ ∪ Y ∈ I . We show that a powerful technique for computing representative families, introduced by Fomin et al. (2014) [5] , leads to a unified approach for substantially improving the running times of parameterized algorithms for some classic problems. This includes k -Partial Cover , k -Internal Out-Branching , and Long Directed Cycle , among others. Our approach exploits an interesting tradeoff between running time and the representative family size. [ABSTRACT FROM AUTHOR]

The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also attracted attention from the viewpoint of Parameterized complexity. In this paper, we focus on the parameterized complexity of Terrain Guarding (both discrete and continuous) with respect to two natural parameters. First we show that, when parameterized by the number r of reflex vertices in the input terrain, the problem has a polynomial kernel. We also show that, when parameterized by the number c of minima in the terrain, Discrete Orthogonal Terrain Guarding has an XP algorithm. [ABSTRACT FROM AUTHOR]

The ArtGallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of ArtGallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of ArtGallery are all W[1]-hard with respect to k [Bonnet and Miltzow in 24th Annual European Symposium on Algorithms (Aarhus 2016)], the classic variant has an O (log k) -approximation algorithm [Bonnet and Miltzow in 33rd International Symposium on Computational Geometry (Brisbane 2017)], and it may require irrational guards [Abrahamsen et al. in 33rd International Symposium on Computational Geometry (Brisbane 2017)]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be ∃ R -complete [Abrahamsen et al. in 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018)]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Workshop on Fixed-Parameter Computational Geometry (Leiden 2016)]: Is ArtGallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of ArtGallery, this case can also be viewed as the classic DominatingSet problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-VertexArtGallery is solvable in time r O (r 2) · n O (1) . Furthermore, our approach extends to assert that Vertex-BoundaryArtGallery and Boundary-VertexArtGallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-VertexArtGallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions. [ABSTRACT FROM AUTHOR]

Gene clusters are groups of genes that are co-locally conserved across various genomes, not necessarily in the same order. Their discovery and analysis is valuable in tasks such as gene annotation and prediction of gene interactions, and in the study of genome organization and evolution. The discovery of conserved gene clusters in a given set of genomes is a well studied problem, but with the rapid sequencing of prokaryotic genomes a new problem is inspired. Namely, given an already known gene cluster that was discovered and studied in one genomic dataset, to identify all the instances of the gene cluster in a given new genomic sequence. Thus, we define a new problem in comparative genomics, denoted PQ-Tree Search that takes as input a PQ-tree T representing the known gene orders of a gene cluster of interest, a gene-to-gene substitution scoring function h, integer arguments d T and d S , and a new sequence of genes S. The objective is to identify in S approximate new instances of the gene cluster; These instances could vary from the known gene orders by genome rearrangements that are constrained by T, by gene substitutions that are governed by h, and by gene deletions and insertions that are bounded from above by d T and d S , respectively. We prove that PQ-Tree Search is NP-hard and propose a parameterized algorithm that solves the optimization variant of PQ-Tree Search in O ∗ (2 γ) time, where γ is the maximum degree of a node in T and O ∗ is used to hide factors polynomial in the input size. The algorithm is implemented as a search tool, denoted PQFinder, and applied to search for instances of chromosomal gene clusters in plasmids, within a dataset of 1,487 prokaryotic genomes. We report on 29 chromosomal gene clusters that are rearranged in plasmids, where the rearrangements are guided by the corresponding PQ-trees. One of these results, coding for a heavy metal efflux pump, is further analysed to exemplify how PQFinder can be harnessed to reveal interesting new structural variants of known gene clusters. [ABSTRACT FROM AUTHOR]

Given an n-vertex digraph D and a non-negative integer k, the Minimum Directed Bisection problem asks if the vertices of D can be partitioned into two parts, say L and R, such that | L | and | R | differ by at most 1 and the number of arcs from R to L is at most k. This problem is known to be NP-hard even when k = 0 . We investigate the parameterized complexity of this problem on semicomplete digraphs. We show that Minimum Directed Bisection admits a sub-exponential time fixed-parameter tractable algorithm on semicomplete digraphs. We also show that Minimum Directed Bisection admits a polynomial kernel on semicomplete digraphs. To design the kernel, we use (n , k , k 2) -splitters, which, to the best of our knowledge, have never been used before in the design of kernels. We also prove that Minimum Directed Bisection is NP-hard on semicomplete digraphs, but polynomial time solvable on tournaments. [ABSTRACT FROM AUTHOR]

In the Maximum-Duo Preservation String Mapping (Max-Duo PSM) problem, the input consists of two related strings A and B of length n and a nonnegative integer k. The objective is to determine whether there exists a mapping m from the set of positions of A to the set of positions of B that maps only to positions with the same character and preserves at least k duos , which are pairs of adjacent positions. We develop a randomized algorithm that solves Max-Duo PSM in 4 k ⋅ n O (1) time, and a deterministic algorithm that solves this problem in 6.855 k ⋅ n O (1) time. The previous best known (deterministic) algorithm for this problem has (8 e) 2 k + o (k) ⋅ n O (1) running time [Beretta et al. (2016) [1,2] ]. We also show that Max-Duo PSM admits a problem kernel of size O (k 3) , improving upon the previous best known problem kernel of size O (k 6). [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 the Partial Information Network Query (PINQ) problem, we are given a host graph H, and a pattern P whose topology is partially known. We seek a connected subgraph of H that resembles P . PINQ is a generalization of Subgraph Isomorphism, where the topology of P is known, and Graph Motif, where the topology of P is unknown. This generalization addresses the major challenge of analyzing biological networks in the absence of certain topological data. In this paper, we use a non-standard hybridization of algebraic and combinatorial tools to develop an exact parameterized algorithm as well as an FPT-approximation scheme for PINQ. [ABSTRACT FROM AUTHOR]

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]

Fradkin and Seymour (J Comb Theory Ser B 110:19–46, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is structured enough to be exploited algorithmically. In this paper, we further strengthen this belief by showing that several cut problems that admit sub-exponential time parameterized algorithms (a trait uncommon to parameterized algorithms) on tournaments, including Directed Feedback Arc Set, Directed Cutwidth and Optimal Linear Arrangement, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk (in: Proceedings of the Algorithms—ESA 2013—21st Annual European Symposium, Sophia Antipolis, France, September 2–4, 2013, pp. 505–516, 2013), where to get the desired algorithms, it is enough to bound the number of k-cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of k-cuts in transitive tournaments). Specifically, our main technical contribution is a combinatorial result that proves that the yes-instances of the problems (defined above) have a sub-exponential number of k-cuts. We prove this bound by using a combination of chromatic coding, inductive reasoning and exploiting the structural properties of these digraphs. [ABSTRACT FROM AUTHOR]

A class of graphs ℱ ${\rm{ {\mathcal F} }}$ admits the Erdős–Pósa property if for any graph G $G$, either G $G$ has k $k$ vertex‐disjoint "copies" of the graphs in ℱ ${\rm{ {\mathcal F} }}$, or there is a set S⊆V(G) $S\subseteq V(G)$ of f(k) $f(k)$ vertices that intersects all copies of the graphs in ℱ ${\rm{ {\mathcal F} }}$. For any graph class G ${\mathscr{G}}$, it is natural to ask whether the family of obstructions to G ${\mathscr{G}}$ has the Erdős–Pósa property. In this paper, we prove that the family of obstructions to interval graphs—namely, the family of chordless cycles and asteroidal witnesses (AWs)—admits the Erdős–Pósa property. In turn, this yields an algorithm to decide whether a given graph G $G$ has k $k$ vertex‐disjoint AWs and chordless cycles, or there exists a set of O(k2logk) ${\mathscr{O}}({k}^{2}\mathrm{log}k)$ vertices in G $G$ that hits all AWs and chordless cycles. [ABSTRACT FROM AUTHOR]

We study the classic Graph Motif problem. Given a graph G = ( V , E ) with a set of colors for each node, and a multiset M of colors, we seek a subtree T ⊆ G , and a coloring assigning to each node in T a color from its set, such that T carries exactly (also with respect to multiplicity) the colors in M . Graph Motif plays a central role in the study of pattern matching problems, primarily motivated from the analysis of complex biological networks. Previous algorithms for Graph Motif and its variants either rely on techniques for developing randomized algorithms that − if derandomized − render them inefficient, or the algebraic narrow sieves technique for which there is no known derandomization. In this paper, we present fast deterministic parameterized algorithms for Graph Motif and its variants. Specifically, we give such an algorithm for the more general Graph Motif with Deletions problem, followed by faster algorithms for Graph Motif and other well-studied special cases. Our algorithms make non-trivial use of representative families , and a novel tool that we call guiding trees , together enabling the efficient construction of the output tree. [ABSTRACT FROM AUTHOR]

We study the Steiner Tree problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R ⊆ V (G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V \ R . The vertices of R are referred to as terminals and the vertices of V (G) \ R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in n O (t + k) time. We also show that the Steiner Tree problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2 O (k) n O (1) . In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs Fomin (Discret. Comput. Geometry 62(4):879–911, 2019). We mention that the algorithmic results can be made to work for Steiner Tree problem on disk graphs with bounded aspect ratio. Finally, we prove that Steiner Tree problem on disk graphs parameterized by k, is W[1]-hard. [ABSTRACT FROM AUTHOR]

In this paper, we pioneer a study of parameterized automata constructions for languages related to the design of parameterized algorithms. We focus on the k - Distinct language L k ( Σ ) ⊆ Σ k , defined as the set of words of length k over an alphabet Σ whose symbols are all distinct. This language is implicitly related to several breakthrough techniques developed during the last two decades, to design parameterized algorithms for fundamental problems such as k - Path and r - Dimensional k - Matching . Building upon the color coding, divide-and-color and narrow sieves techniques, we obtain the following automata constructions for L k ( Σ ) . We develop non-deterministic automata (NFAs) of sizes 4 k + o ( k ) ⋅ n O ( 1 ) and ( 2 e ) k + o ( k ) ⋅ n O ( 1 ) , where the latter satisfies a ‘bounded ambiguity’ property relevant to approximate counting, as well as a non-deterministic xor automaton (NXA) of size 2 k ⋅ n O ( 1 ) , where n = | Σ | . We show that our constructions can be used to develop both deterministic and randomized algorithms for k - Path , r - Dimensional k -Matching and Module Motif in a natural manner, considering also their approximate counting variants. Our framework is modular and consists of two parts: designing an automaton for k - Distinct , and designing a problem specific automaton, as well as an algorithm for deciding whether the intersection automaton's language is empty, or for counting the number of accepting paths in it. [ABSTRACT FROM AUTHOR]

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]

The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of the equal disk packing problem. In this problem, for a given packing of equal disks into a rectangle, the question is whether by changing positions of a small number of disks, we can allocate space for packing more disks. More formally, in the repacking problem, for a given set of n equal disks packed into a rectangle and integers k and h, we ask whether it is possible by changing positions of at most h disks to pack n+k\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n+k$$\end{document} disks. Thus the problem of packing equal disks is the special case of our problem with n=h=0\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n=h=0$$\end{document}. While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for h=0\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$h=0$$\end{document}. Our main algorithmic contribution is an algorithm that solves the repacking problem in time (h+k)O(h+k)·|I|O(1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(h+k)^{\mathcal {O}(h+k)}\cdot |I|^{\mathcal {O}(1)}$$\end{document}, where |I| is the input size. That is, the problem is fixed-parameter tractable parameterized by k and h. [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]

A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to these problems as Arc-disjoint Cycles in Tournaments (ACT) and Arc-disjoint Triangles in Tournaments (ATT), respectively. Although the maximization version of ACT can be seen as the dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic results seem to exist for ACT. We first show that ACT and ATT are both NP-complete. Then, we show that the problem of determining if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete. Next, we prove that ACT is fixed-parameter tractable via a 2 O (k log k) n O (1) -time algorithm and admits a kernel with O (k) vertices. Then, we show that ATT too has a kernel with O (k) vertices and can be solved in 2 O (k) n O (1) time. Afterwards, we describe polynomial-time algorithms for ACT and ATT when the input tournament has a feedback arc set that is a matching. We also prove that ACT and ATT cannot be solved in 2 o (n) n O (1) time under the exponential-time hypothesis. [ABSTRACT FROM AUTHOR]

Agrawal et al. (ACM Trans Comput Theory 10(4):18:1–18:25, 2018. https://doi.org/10.1145/3265027) studied a simultaneous variant of the classic Feedback Vertex Set problem, called Simultaneous Feedback Vertex Set (Sim-FVS). Here, we consider the edge variant of the problem, namely, Simultaneous Feedback Edge Set (Sim-FES). In this problem, the input is an n-vertex graph G, a positive integer k, and a coloring function col: E (G) → 2 [ α ] , and the objective is to check whether there is an edge subset S of cardinality k in G such that for each i ∈ [ α ] , G i - S is acyclic. Unlike the vertex variant of the problem, when α = 1 , the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for α = 3 , Sim-FES is NP-hard, and does not admit an algorithm of running time 2 o (k) n O (1) unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time 2 ω k α + α log k n O (1) where ω is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when α = 2 . We also give a kernel for Sim-FES with (k α) O (α) vertices. Finally, we consider a "dual" version of the problem called Maximum Simultaneous Acyclic Subgraph and give an FPT algorithm with running time 2 ω q α n O (1) , where q is the number of edges in the output subgraph. [ABSTRACT FROM AUTHOR]

This Special Issue contains eleven articles—surveys and research papers—that represent fresh and ambitious new directions in the area of Parameterized Complexity. They provide ground-breaking research at the frontiers of knowledge, and they contribute to bridging the gap between theory and practice. The scope and impact of the field continues to increase. Promising avenues and new research challenges are highlighted in this Special Issue. [ABSTRACT FROM AUTHOR]

An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy d > 1 contains a cycle of length at least d + 1. The proof of Erdös and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d + 1. But can we decide in polynomial time whether a graph contains a cycle of length at least d + 2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether G contains a cycle of length at least d + k can be done in time 2O(k) .| V (G)| O(1). In other words, deciding whether a 2-connected n-vertex G contains a cycle of length at least d+log n can be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at least d+1 is NP-complete. However, we prove that if graph G is connected, then deciding whether G contains a path of length at least d+k can be done in time 2O(k) .nO(1). We complement these results by showing that the choice of degeneracy as the ``above guarantee parameterization"" is optimal in the following sense: For any ε > 0 it is NP-complete to decide whether a connected (2-connected) graph of degeneracy d has a path (cycle) of length at least (1 + ε )d. [ABSTRACT FROM AUTHOR]

In this paper, we study the NP-complete colorful variant of the classic matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, the goal is to decide whether there exists a matching of size at least k such that the edges in the matching have distinct colors. Previously, in [MFCS'17], we studied this problem from the view point of Parameterized Complexity and gave efficient FPT algorithms as well as a quadratic kernel on paths. In this paper we design a quadratic vertex kernel for Rainbow Matching on general graphs; generalizing the earlier quadratic kernel on paths to general graphs. For our kernelization algorithm we combine a graph decomposition method with an application of expansion lemma. [ABSTRACT FROM AUTHOR]

We give algorithms with running time 2 O (k log k) · n O (1) for the following problems. Given an n-vertex unit disk graph G and an integer k, decide whether G contains a path on exactly/at least k vertices, a cycle on exactly k vertices, a cycle on at least k vertices, a feedback vertex set of size at most k, and a set of k pairwise vertex-disjoint cycles. For the first three problems, no subexponential time parameterized algorithms were previously known. For the remaining two problems, our algorithms significantly outperform the previously best known parameterized algorithms that run in time 2 O (k 0.75 log k) · n O (1) . Our algorithms are based on a new kind of tree decompositions of unit disk graphs where the separators can have size up to k O (1) and there exists a solution that crosses every separator at most O (k) times. The running times of our algorithms are optimal up to the log k factor in the exponent, assuming the exponential time hypothesis. [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]

The family of judicious partitioning problems, introduced by Bollobàs and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection, and Max Cut. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is "judicious" in the sense that neither side is burdened by too many edges, and Balanced JB (BJB) also requires that the sizes of the sides themselves are "balanced" in the sense that neither of them is too large. Both of these problems were defined in the work by Bollobàs and Scott and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is fixed parameter tractable (FPT) (which also proves that JB is FPT). [ABSTRACT FROM AUTHOR]

In the Cycle Packing problem, we are given an undirected graph G, a positive integer r, and the task is to check whether there exist r vertex-disjoint cycles. In this paper, we study Cycle Packing with respect to a structural parameter, namely, distance to proper interval graphs (indifference graphs). In particular, we show that Cycle Packing is fixed-parameter tractable (FPT) when parameterized by t, the size of a proper interval deletion set. For this purpose, we design an algorithm with O (2 O (t log t) n O (1)) running time. Bodlaender et al. (Theor Comput Sci 511:117–136, 2013) studied several structural parameterizations for Cycle Packing and our FPT algorithm fills a gap in their ecology of parameterizations. We combine color coding, greedy strategy and dynamic programming based on structural properties of proper interval graphs in a non-trivial fashion to obtain the FPT algorithm. Our belief is that this approach is quite general and can be useful in solving many other problems with the same parameterization. [ABSTRACT FROM AUTHOR]

The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a long-standing, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and Wahlstrom on representative sets finally answered this question in the affirmative [FOCS 2012]. In this paper, we present an alternative, algebraic compression of the Vertex Cover Above LP problem into the Rank Vertex Cover problem. Here, the input consists of a graph G, a parameter k, and a bijection between V (G) and the set of columns of a representation of a matroid M, and the objective is to find a vertex cover whose rank is upper bounded by k. [ABSTRACT FROM AUTHOR]

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]

In this paper, we study the NP-complete colorful variant of the classical Matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, this problem asks whether there exists a matching of size at least k such that all the edges in the matching have distinct colors. We first develop a deterministic algorithm that solves Rainbow Matching on paths in time O ⋆ 1 + 5 2 k and polynomial space. This algorithm is based on a curious combination of the method of bounded search trees and a "divide-and-conquer-like" approach, where the branching process is guided by the maintenance of an auxiliary bipartite graph where one side captures "divided-and-conquered" pieces of the path. Our second result is a randomized algorithm that solves Rainbow Matching on general graphs in time O ⋆ (2 k) and polynomial-space. Here, we show how a result by Björklund et al. (J Comput Syst Sci 87:119–139, 2017) can be invoked as a black box, wrapped by a probability-based analysis tailored to our problem. We also complement our two main results by designing kernels for Rainbow Matching on general and bounded-degree graphs. [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]

For a target rank r, the rigidity of a matrix A over a field F is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in computational complexity theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of parameterized complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of parameterized complexity. Naturally, given parameters r and k, the Matrix Rigidity problem asks whether the rigidity of A for the target rank r is at most k. We show that in the case F = R or F is any finite field, this problem is fixed-parameter tractable with respect to k+r. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in real algebraic geometry, which are not well known in parameterized complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem. [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]

Given a digraph D and an integer k , Directed Feedback Vertex Set (DFVS) asks whether there exists a set of vertices S of size at most k such that F = D ∖ S is DAG. Mnich and van Leeuwen [ STACS 2016  ] considered the kernelization complexity of DFVS with an additional restriction on F , namely that F must be an out-forest ( Out-Forest Vertex Deletion Set ), an out-tree ( Out-Tree Vertex Deletion Set ), or a (directed) pumpkin ( Pumpkin Vertex Deletion Set ). Their objective was to shed light on the kernelization complexity of DFVS , a well-known open problem in Parameterized Complexity. We improve the kernel sizes of Out-Forest Vertex Deletion Set from O ( k 3 ) to O ( k 2 ) and of Pumpkin Vertex Deletion Set from O ( k 18 ) to O ( k 3 ) . We also prove that the former kernel size is tight under certain complexity theoretic assumptions. [ABSTRACT FROM AUTHOR]

We show two results related to finding trees and paths in graphs. First, we show that in O*(1.657k21/2) time one can either find a k-vertex tree with l leaves in an n-vertex undirected graph or conclude that such a tree does not exist. Our solution can be applied as a subroutine to solve the k-INTERNAL SPANNING Tree problem in O* (min(3.455k, 1.946n)) time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time we break the natural barrier of O*(2n). Second, we show that the running time can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for HAMILTONICITY and k-PATH in any graph of maximum degree Δ = 4,..., 12 or with vector chromatic number at most 8. Our results extend the technique by Björklund [SIAM J. Comput., 43 (2014), pp. 280-299] and Björklund et al. [Narrow Sieves for Parameterized Paths and Packings, CoRR, arXiv:1007. 1161, 2010] to finding structures more general than paths as well as refine it to handle special classes of graphs more efficiently.r [ABSTRACT FROM AUTHOR]

Background: Cancer is an evolutionary process characterized by the accumulation of somatic mutations in a population of cells that form a tumor. One frequent type of mutations is copy number aberrations, which alter the number of copies of genomic regions. The number of copies of each position along a chromosome constitutes the chromosome's copy-number profile. Understanding how such profiles evolve in cancer can assist in both diagnosis and prognosis. Results: We model the evolution of a tumor by segmental deletions and amplifications, and gauge distance from profile a to b by the minimum number of events needed to transform a into b. Given two profiles, our first problem aims to find a parental profile that minimizes the sum of distances to its children. Given k profiles, the second, more general problem, seeks a phylogenetic tree, whose k leaves are labeled by the k given profiles and whose internal vertices are labeled by ancestral profiles such that the sum of edge distances is minimum. Conclusions: For the former problem we give a pseudo-polynomial dynamic programming algorithm that is linear in the profile length, and an integer linear program formulation. For the latter problem we show it is NP-hard and give an integer linear program formulation that scales to practical problem instance sizes. We assess the efficiency and quality of our algorithms on simulated instances. [ABSTRACT FROM AUTHOR]

In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-Set k-Packing ((r, k)-SP) problems. Given a universe U := U1 ··· Ur and an r-uniform family F ⊆ U1 ×· · · × Ur, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F ⊆ 2U , the (r, k)-SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851(r−1)k · |F|· nlog2 n·log W) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851(r−0.5501)k · |F| · n log2 n · log W) for the weighted version of (r, k)-SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)-SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3, k)-DM, running in time O(2.0043k · |F| · n log2 n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(err(k − 1)r log W) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k − 1)r log W) for these problems. [ABSTRACT FROM AUTHOR]