Search

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]

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]

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]

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]

We study the Partial Information Network Query (PINQ) problem, which generalizes two problems that often arise in bioinformatics: the Alignment Network Query (ANQ) problem and the Topology-Free Network Query (TFNQ) problem. In both ANQ and TFNQ we have a pattern P and a graph H , and we seek a subgraph of H that resembles P . ANQ requires knowing the topology of P , while TFNQ ignores it. PINQ fits the scenario where partial information is available on the topology of P . Our main result is a parameterized algorithm that handles inputs for PINQ in which P is a set of trees. This algorithm significantly improves the best known O ⁎ running time in solving TFNQ. We also improve the best known O ⁎ running times in solving two special cases of ANQ. [ABSTRACT FROM AUTHOR]

In this article we address two pattern matching problems which have important applications to bioinformatics. First we address the topology-free network query problem: Given a set of labels L, a multiset P of labels from L, a graph H = (V H, E H) and a function L a b e l H : V H → 2 L, we need to find a subtree S of H which is an occurrence of P. We provide a parameterized algorithm with parameter k = | P | that runs in time O * (2 k) and whose space complexity is polynomial. We also consider three variants of this problem. Then we address the alignment network query problem: Given two labeled graphs P and H, we need to find a subgraph S of H whose alignment with P is the best among all such subgraphs. We present two algorithms for cases in which P and H belong to certain families of DAGs. Their running times are polynomial and they are less restrictive than algorithms that are available today for alignment network queries. Topology-free and alignment network queries provide means to study the function and evolution of biological networks, and today, with the increasing amount of knowledge regarding biological networks, they are extremely relevant. [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]