Search

Chromatic $k$ -median is a frequently encountered problem in the determination of the topological structures of chromosomes. This problem considers a set $\mathcal {C}$ of colored clients and a set $\mathcal {F}$ of facilities located in a metric space, where $|\mathcal {C}\cup \mathcal {F}|=n$ . The goal is to open $k$ facilities and assign each client to an opened facility, such that clients with the same color are assigned to different facilities and the sum of the distance from each client to the corresponding facility is minimized. It was known that the chromatic $k$ -median problem is W[2]-hard if parameterized by $k$ . This rules out the probability of obtaining an exact FPT( $k$ )-time algorithm for the problem. In this paper, we give an FPT( $k$ )-time approximation algorithm for chromatic $k$ -median. The algorithm achieves a $(3+\epsilon)$ -approximation and runs in $(k\epsilon ^{-1})^{O(k)}n^{O(1)}$ time. We propose a different random sampling algorithm for opening facilities, which is the crucial step in getting the constant factor parameterized approximation.

Recently it was shown that, if the subtree and chain reduction rules have been applied exhaustively to two unrooted phylogenetic trees, the reduced trees will have at most 15k-9 taxa where k is the TBR (Tree Bisection and Reconnection) distance between the two trees, and that this bound is tight. Here we propose five new reduction rules and show that these further reduce the bound to 11k-9. The new rules combine the ``unrooted generator'' approach introduced in [Kelk and Linz 2018] with a careful analysis of agreement forests to identify (i) situations when chains of length 3 can be further shortened without reducing the TBR distance, and (ii) situations when small subtrees can be identified whose deletion is guaranteed to reduce the TBR distance by 1. To the best of our knowledge these are the first reduction rules that strictly enhance the reductive power of the subtree and chain reduction rules., Comment: Accepted for journal publication. This version contains extra figures. Keywords: fixed-parameter tractability, tree bisection and reconnection, generator, kernelization, agreement forest, phylogenetic network, phylogenetic tree, hybridization number

Dirac’s theorem (1952) is a classical result of graph theory, stating that an n-vertex graph (n≥3n≥3) is Hamiltonian if every vertex has degree at least n/2. Both the value n/2 and the requirement for every vertex to have high degree are necessary for the theorem to hold. In this work we give efficient algorithms for determining Hamiltonicity when either of the two conditions are relaxed. More precisely, we show that the Hamiltonian Cycle problem can be solved in time ck⋅nO(1)ck⋅nO(1), for a fixed constant c, if at least n−kn−k vertices have degree at least n/2, or if all vertices have degree at least n/2−kn/2−k. The running time is, in both cases, asymptotically optimal, under the exponential-time hypothesis (ETH). The results extend the range of tractability of the Hamiltonian Cycle problem, showing that it is fixed-parameter tractable when parameterized below a natural bound. In addition, for the first parameterization we show that a kernel with O(k) vertices can be found in polynomial time.

In 2001 Allen and Steel showed that, if subtree and chain reduction rules have been applied to two unrooted phylogenetic trees, the reduced trees will have at most 28k taxa where k is the TBR (Tree Bisection and Reconnection) distance between the two trees. Here we reanalyse Allen and Steel's kernelization algorithm and prove that the reduced instances will in fact have at most 15k-9 taxa. Moreover we show, by describing a family of instances which have exactly 15k-9 taxa after reduction, that this new bound is tight. These instances also have no common clusters, showing that a third commonly-encountered reduction rule, the cluster reduction, cannot further reduce the size of the kernel in the worst case. To achieve these results we introduce and use "unrooted generators" which are analogues of rooted structures that have appeared earlier in the phylogenetic networks literature. Using similar argumentation we show that, for the minimum hybridization problem on two rooted trees, 9k-2 is a tight bound (when subtree and chain reduction rules have been applied) and 9k-4 is a tight bound (when, additionally, the cluster reduction has been applied) on the number of taxa, where k is the hybridization number of the two trees., Comment: One figure added, two small typos fixed. This version to appear in SIDMA (SIAM Journal on Discrete Mathematics)

We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms....

We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree in a given graph. MBT is a natural variant of the well-studied longest path problem, since both can be viewed as finding a maximum-sized tree of bounded degree in a given graph. The connection to longest path motivates the study of MBT in directed acyclic graphs (DAGs), since the longest path problem is solvable efficiently in DAGs. In contrast, we show that MBT in DAGs is in fact hard: it has no efficient $\exp(-O(\log n/ \log \log n))$-approximation algorithm under the exponential time hypothesis, where $n$ is the number of vertices in the input graph. In undirected graphs, we show that MBT has no efficient $\exp(-O(\log^{0.63}{n}))$-approximation under the exponential time hypothesis. Our inapproximability results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming $\text{P}\neq \text{NP}$. In addition to inapproximability results, we present algorithmic results along two different flavors: (1) We design a randomized algorithm to verify if a given directed graph on $n$ vertices contains a binary tree of size $k$ in $2^k \text{poly}(n)$ time. (2) Motivated by the longest heapable subsequence problem, introduced by Byers, Heeringa, Mitzenmacher, and Zervas (ANALCO 2011), which is equivalent to MBT in permutation DAGs, we design efficient algorithms for MBT in bipartite permutation graphs., to be published in European Symposium on Algorithms 2020

Given a graph G, a q-open neighborhood conflict-free coloring or q-ONCF-coloring is a vertex coloring \(c:V(G) \rightarrow \{1,2,\ldots ,q\}\) such that for each vertex \(v \in V(G)\) there is a vertex in N(v) that is uniquely colored from the rest of the vertices in N(v). When we replace N(v) by the closed neighborhood N[v], then we call such a coloring a q-closed neighborhood conflict-free coloring or simply q-CNCF-coloring. In this paper, we study the NP-hard decision questions of whether for a constant q an input graph has a q-ONCF-coloring or a q-CNCF-coloring. We will study these two problems in the parameterized setting. First of all, we study running time bounds on FPT-algorithms for these problems, when parameterized by treewidth. We improve the existing upper bounds, and also provide lower bounds on the running time under ETH and SETH. Secondly, we study the kernelization complexity of both problems, using vertex cover as the parameter. We show that both \((q \ge 2)\)-ONCF-coloring and \((q \ge 3)\)-CNCF-coloring cannot have polynomial kernels when parameterized by the size of a vertex cover unless \(\mathsf {NP \subseteq coNP/poly}\). On the other hand, we obtain a polynomial kernel for 2-CNCF-coloring parameterized by vertex cover. We conclude the study with some combinatorial results. Denote \(\chi _{ON}(G)\) and \(\chi _{CN}(G)\) to be the minimum number of colors required to ONCF-color and CNCF-color G, respectively. Upper bounds on \(\chi _{CN}(G)\) with respect to structural parameters like minimum vertex cover size, minimum feedback vertex set size and treewidth are known. To the best of our knowledge only an upper bound on \(\chi _{ON}(G)\) with respect to minimum vertex cover size was known. We provide tight bounds for \(\chi _{ON}(G)\) with respect to minimum vertex cover size. Also, we provide the first upper bounds on \(\chi _{ON}(G)\) with respect to minimum feedback vertex set size and treewidth.

Imagine that unlabelled tokens are placed on the edges of a graph, such that no two tokens are placed on incident edges. A token can jump to another edge if the edges having tokens remain independent. We study the problem of determining the distance between two token configurations (resp., the corresponding matchings), which is given by the length of a shortest transformation. We give a polynomial-time algorithm for the case that at least one of the two configurations is not inclusion-wise maximal and show that otherwise, the problem admits no polynomial-time sublogarithmic-factor approximation unless P = NP. Furthermore, we show that the distance of two configurations in bipartite graphs is fixed-parameter tractable parameterized by the size $d$ of the symmetric difference of the source and target configurations, and obtain a $d^\varepsilon$-factor approximation algorithm for every $\varepsilon > 0$ if additionally the configurations correspond to maximum matchings. Our two main technical tools are the Edmonds-Gallai decomposition and a close relation to the Directed Steiner Tree problem. Using the former, we also characterize those graphs whose corresponding configuration graphs are connected. Finally, we show that deciding if the distance between two configurations is equal to a given number $\ell$ is complete for the class $D^P$, and deciding if the diameter of the graph of configurations is equal to $\ell$ is $D^P$-hard., 31 pages, 3 figures

For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that 1. the subgraph induced by each cluster is drawn in the interior of the corresponding disk, 2. each edge intersects any disk at most once, and 3. the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Qing-Wen Feng, Robert F. Cohen, and Peter Eades. Planarity for clustered graphs. ESA'95], has only been recently settled [Radoslav Fulek and Csaba D. T\'oth. Atomic Embeddability, Clustered Planarity, and Thickenability. To appear at SODA'20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT algorithm for embedded clustered graphs, when parameterized by the carving-width of the dual graph of the input. This is the first FPT algorithm for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, in the general case, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and T\'oth. To further strengthen the relevance of this result, we show that the C-Planarity Testing problem retains its computational complexity when parameterized by several other graph-width parameters, which may potentially lead to faster algorithms., Comment: Extended version of the paper "C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width" to appear in the Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Given a graph G = ( V , E ) of order n and an n -dimensional non-negative vector d = ( d ( 1 ) , d ( 2 ) , … , d ( n ) ) , called demand vector, the vector domination (resp., total vector domination) is the problem of finding a minimum S ⊆ V such that every vertex v in V ∖ S (resp., in V ) has at least d ( v ) neighbors in S . The (total) vector domination is a generalization of many dominating set type problems, e.g., the (total) dominating set problem, the (total) k -dominating set problem (this k is different from the solution size), and so on, and subexponential fixed-parameter algorithms with respect to solution size for apex-minor-free graphs (so for planar graphs) are known. In this paper, we consider maximization versions of the problems; that is, for a given integer k , the goal is to find an S ⊆ V with size k that maximizes the total sum of satisfied demands. For these problems, we design subexponential fixed-parameter algorithms with respect to k for apex-minor-free graphs.

International audience; For a (possibly infinite) fixed family of graphs F, we say that a graph G overlays F on a hypergraph H if V (H) is equal to V (G) and the subgraph of G induced by every hyperedge of H contains some member of F as a spanning subgraph. While it is easy to see that the complete graph on |V (H)| overlays F on a hypergraph H whenever the problem admits a solution, the Minimum F-Overlay problem asks for such a graph with the minimum number of edges. This problem allows to generalize some natural problems which may arise in practice. For instance, if the family F contains all connected graphs, then Minimum F-Overlay corresponds to the Minimum Connectivity Inference problem (also known as Subset Interconnection Design problem) introduced for the low-resolution reconstruction of macro-molecular assembly in structural biology, or for the design of networks. Our main contribution is a strong dichotomy result regarding the polynomial vs. NP-hard status with respect to the considered family F. Roughly speaking, we show that the easy cases one can think of (e.g. when edge-less graphs of the right sizes are in F, or if F contains only cliques) are the only families giving rise to a polynomial problem: all others are NP-complete. We then investigate the parameterized complexity of the problem and give similar sufficient conditions on F that give rise to W[1]-hard, W[2]-hard or FPT problems when the parameter is the size of the solution. This yields an FPT/W[1]-hard dichotomy for a relaxed problem , where every hyperedge of H must contain some member of F as a (non necessarily spanning) subgraph.

The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results:We show that an algorithm by Crowston et al. (Algorithmica 72(3):734-757, 2015) for (Signed) Max-Cut Above Edwards-Erd A s Bound can be implemented so as to run in linear time ; this significantly improves the previous analysis with run time .We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards-Erd A s Bound with O(k) vertices, improving a kernel with vertices by Crowston et al. (Theor Comput Sci 513:53-64, 2013).We improve all known kernels for parameterizations above strongly -extendible properties (a generalization of the Max-Cut results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics, Guwahati, 2013) from vertices to O(k) vertices.Therefore, Max Acyclic Subdigraph parameterized above Poljak-Turzik bound admits a kernel with O(k) vertices and can be solved in time; this answers an open question by Crowston et al. (Proceedings of FSTTCS 2012, Leibniz international proceedings in informatics, Hyderabad, 2012).

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most $$2^{{O}(k^3\log k)}$$ . As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time $$2^{{O}(k^2\log k)}\cdot n$$ , where k is the optimum width and n is the number of vertices. While being slower by a $$\log k$$ -factor in the exponent than the fastest known algorithm, given by Thilikos et al. (J Algorithms 56(1):1–24, 2005; J Algorithms 56(1):25–49, 2005), our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts.

Given an $n$-vertex non-negatively real-weighted graph $G$, whose vertices are partitioned into a set of $k$ clusters, a \emph{clustered network design problem} on $G$ consists of solving a given network design optimization problem on $G$, subject to some additional constraint on its clusters. In particular, we focus on the classic problem of designing a \emph{single-source shortest-path tree}, and we analyze its computational hardness when in a feasible solution each cluster is required to form a subtree. We first study the \emph{unweighted} case, and prove that the problem is \np-hard. However, on the positive side, we show the existence of an approximation algorithm whose quality essentially depends on few parameters, but which remarkably is an $O(1)$-approximation when the largest out of all the \emph{diameters} of the clusters is either $O(1)$ or $\Theta(n)$. Furthermore, we also show that the problem is \emph{fixed-parameter tractable} with respect to $k$ or to the number of vertices that belong to clusters of size at least 2. Then, we focus on the \emph{weighted} case, and show that the problem can be approximated within a tight factor of $O(n)$, and that it is fixed-parameter tractable as well. Finally, we analyze the unweighted \emph{single-pair shortest path problem}, and we show it is hard to approximate within a (tight) factor of $n^{1-\epsilon}$, for any $\epsilon>0$., Comment: 21 pages, 3 figures

Reconciling gene trees with a species tree is a fundamental problem to understand the evolution of gene families. Many existing approaches reconcile each gene tree independently. However, it is well-known that the evolution of gene families is interconnected. In this paper, we extend a previous approach to reconcile a set of gene trees with a species tree based on segmental macro-evolutionary events, where segmental duplication events and losses are associated with cost $\delta$ and $\lambda$, respectively. We show that the problem is polynomial-time solvable when $\delta \leq \lambda$ (via LCA-mapping), while if $\delta > \lambda$ the problem is NP-hard, even when $\lambda = 0$ and a single gene tree is given, solving a long standing open problem on the complexity of the reconciliation problem. On the positive side, we give a fixed-parameter algorithm for the problem, where the parameters are $\delta/\lambda$ and the number $d$ of segmental duplications, of time complexity $O(\lceil \frac{\delta}{\lambda} \rceil^{d} \cdot n \cdot \frac{\delta}{\lambda})$. Finally, we demonstrate the usefulness of this algorithm on two previously studied real datasets: we first show that our method can be used to confirm or refute hypothetical segmental duplications on a set of 16 eukaryotes, then show how we can detect whole genome duplications in yeast genomes., Comment: 23 pages, 7 figures, WABI 2018

The NP-hard RAINBOW SUBGRAPH problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most \(k\) vertices. We examine the parameterized complexity of RAINBOW SUBGRAPH for paths, trees, and general graphs. We show that RAINBOW SUBGRAPH is W[1]-hard with respect to the parameter \(k\) and also with respect to the dual parameter \(\ell:=n-k\) where \(n\) is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomial-size problem kernel for the combined parameter \(\ell\) and ``maximum number of colors incident with any vertex''. Additionally, we show APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice.

International audience; Phylogenetic networks are used to display the relationship among different species whose evolution is not treelike, which is the case, for instance, in the presence of hybridization events or horizontal gene transfers. Tree inference methods such as maximum parsimony need to be modified in order to be applicable to networks. In this paper, we discuss two different definitions of maximum parsimony on networks, “hardwired” and “softwired,” and examine the complexity of computing them given a network topology and a character. By exploiting a link with the problem Multiterminal Cut, we show that computing the hardwired parsimony score for 2-state characters is polynomial-time solvable, while for characters with more states this problem becomes NP-hard but is still approximable and fixed parameter tractable in the parsimony score. On the other hand we show that, for the softwired definition, obtaining even weak approximation guarantees is already difficult for binary characters and restricted network topologies, and fixed-parameter tractable algorithms in the parsimony score are unlikely. On the positive side we show that computing the softwired parsimony score is fixed-parameter tractable in the level of the network, a natural parameter describing how tangled reticulate activity is in the network. Finally, we show that both the hardwired and the softwired parsimony scores can be computed efficiently using integer linear programming. The software has been made freely available.

Many relevant intractable problems become tractable if some problem parameter is fixed. However, various problems exhibit very different computational properties, depending on how the runtime required for solving them is related to the fixed parameter chosen. The theory of parameterized complexity deals with such issues, and provides general techniques for identifying fixed-parameter tractable and fixed-parameter intractable problems.We study the parameterized complexity of various problems in AI and nonmonotonic reasoning. We show that a number of relevant parameterized problems in these areas are fixed-parameter tractable. Among these problems are constraint satisfaction problems with bounded treewidth and fixed domain, restricted forms of conjunctive database queries, restricted satisfiability problems, propositional logic programming under the stable model semantics where the parameter is the dimension of a feedback vertex set of the program's dependency graph, and circumscriptive inference from a positive k-CNF restricted to models of bounded size. We also show that circumscriptive inference from a general propositional theory, when the attention is restricted to models of bounded size, is fixed-parameter intractable and is actually complete for a novel fixed-parameter complexity class.

Several forms of reasoning in AI – like abduction, closed world reasoning, circumscription, and disjunctive logic programming – are well known to be intractable. In fact, many of the relevant problems are on the second or third level of the polynomial hierarchy. In this paper, we show how the notion of treewidth can be fruitfully applied to this area. In particular, we show that all these problems become tractable (actually, even solvable in linear time), if the treewidth of the involved formulae or programs is bounded by some constant. Clearly, these theoretical tractability results as such do not immediately yield feasible algorithms. However, we have recently established a new method based on monadic datalog which allowed us to design an efficient algorithm for a related problem in the database area. In this work, we exploit the monadic datalog approach to construct new algorithms for logic-based abduction.

International audience; A safe set of a graph G = (V, E) is a non-empty subset S of V such that for every component A of G[S] and every component B of G[V \ S], we have |A| ≥ |B| whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.

Abstract argumentation frameworks have received a lot of interest in recent years. Most computational problems in this area are intractable but several tractable fragments have been identified. In particular, Dunne showed that many problems can be solved in linear time for argumentation frameworks of bounded tree-width. However, these tractability results, which were obtained via Courcelleʼs Theorem, do not directly lead to efficient algorithms. The goal of this paper is to turn the theoretical tractability results into efficient algorithms and to explore the potential of directed notions of tree-width for defining larger tractable fragments. As a by-product, we will sharpen some known complexity results.

In this paper, we explore worst-case solutions for the problems of single and multiple matching on strings in the word-RAM model with word length w. In the first problem, we have to build a data structure based on a pattern p of length m over an alphabet of size @s such that we can answer to the following query: given a text T of length n, where each character is encoded using [email protected] bits return the positions of all the occurrences of p in T (in the following we refer by occ to the number of reported occurrences). For the multi-pattern matching problem we have a set S of d patterns of total length m and a query on a text T consists in finding all positions of all occurrences in T of the patterns in S. As each character of the text is encoded using [email protected] bits and we can read w bits in constant time in the RAM model, we assume that we can read up to @Q(w/[email protected]) consecutive characters of the text in one time step. This implies that the fastest possible query time for both problems is O([email protected]+occ). In this paper we present several different results for both problems which come close to that best possible query time. We first present two different linear space data structures for the first and second problem: the first one answers to single pattern matching queries in time O(n([email protected])+occ) while the second one answers to multiple pattern matching queries to O(n([email protected])+occ) where y is the length of the shortest pattern. We then show how a simple application of the four Russian technique permits to get data structures with query times independent of the length of the shortest pattern (the length of the only pattern in case of single string matching) at the expense of using more space.

The maximum independent set problem is known to be NP-hard for graphs in general, but is solvable in polynomial time for graphs in many special classes. It is also known that the problem is generally intractable from a parameterized point of view. A simple Ramsey argument implies the fixed-parameter tractability of the maximum independent set problem in classes of graphs of bounded clique number. Beyond this observation very little is known about the parameterized complexity of the problem in restricted graph families. In the present paper we develop fpt-algorithms for graphs in some classes extending graphs of bounded clique number.

We present a first thorough theoretical analysis of the Transitivity Editing problem on digraphs. Herein, the task is to make a given digraph transitive by a minimum number of arc insertions or deletions. Transitivity Editing has applications in the detection of hierarchical structure in molecular characteristics of diseases. We demonstrate that if the input digraph does not contain “diamonds”, then there is an optimal solution that performs only arc deletions. This fact helps us construct a first proof of NP-hardness, which also extends to the restricted cases in which the input digraph is acyclic or has maximum degree three. By providing an O(k2)-vertex problem kernel, we answer an open question from the literature. In case of digraphs with maximum degree d, an O(k⋅d)-vertex problem kernel can be shown. Moreover, we improve previous fixed-parameter algorithms, now achieving a running time of O(2.57k+n3) for an n-vertex digraph if k arc modifications are sufficient to make it transitive. Our hardness as well as algorithmic results transfer to Transitivity Deletion, where only arc deletions are allowed.

We introduce overlap cluster graph modification problems where, other than in most previous works, the clusters of the target graph may overlap. More precisely, the studied graph problems ask for a minimum number of edge modifications such that the resulting graph consists of clusters (that is, maximal cliques) that may overlap up to a certain amount specified by the overlap number s. In the case of s-vertex-overlap, each vertex may be part of at most s maximal cliques; s-edge-overlap is analogously defined in terms of edges. We provide a complexity dichotomy (polynomial-time solvable versus NP-hard) for the underlying edge modification problems, develop forbidden subgraph characterizations of “cluster graphs with overlaps”, and study the parameterized complexity in terms of the number of allowed edge modifications, achieving fixed-parameter tractability (in case of constant s-values) and parameterized hardness (in case of unbounded s-values).

We study the parameterized complexity of several minimum label graph problems, in which we are given an undirected graph whose edges are labeled, and a property Π, and we are asked to find a subset of edges satisfying property Π with respect to G that uses the minimum number of labels. These problems have a lot of applications in networking. We show that all the problems under consideration are W[2]-hard when parameterized by the number of used labels, and that they remain W[2]-hard even on graphs whose pathwidth is bounded above by a small constant. On the positive side, we prove that most of these problems are FPT when parameterized by the solution size, that is, the size of the sought edge set. For example, we show that computing a maximum matching or an edge dominating set that uses the minimum number of labels, is FPT when parameterized by the solution size. Proving that some of these problems are FPT requires interesting algorithmic methods that we develop in this paper.

We develop an algorithmically useful refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P). This characterization finds applications in new polynomial-time approximation algorithms and fixed-parameter tractability results for the NP-hard problem to delete a minimum number of rows or columns from a 0/1-matrix such that the remaining submatrix has the C1P.

We show that the two NP-complete problems of Dodgson Score and Young Score have differing computational complexities when the winner is close to being a Condorcet winner. On the one hand, we present an efficient fixed-parameter algorithm for determining a Condorcet winner in Dodgson elections by a minimum number of switches in the votes. On the other hand, we prove that the corresponding problem for Young elections, where one has to delete votes instead of performing switches, is W[2]-complete. In addition, we study Dodgson elections that allow ties between the candidates and give fixed-parameter tractability as well as W[2]-completeness results depending on the cost model for switching ties.

The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Given a set of permutations (votes) over a set of candidates, one searches for a ''consensus permutation'' that is ''closest'' to the given set of permutations. Unfortunately, the problem is NP-hard. We provide a broad study of the parameterized complexity for computing optimal Kemeny rankings. Besides the three obvious parameters ''number of votes'', ''number of candidates'', and solution size (called Kemeny score), we consider further structural parameterizations. More specifically, we show that the Kemeny score (and a corresponding Kemeny ranking) of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter ''average pairwise Kendall-Tau distance d"a''. We describe a fixed-parameter algorithm with running time 16^@?^d^"^a^@[email protected]?poly. Moreover, we extend our studies to the parameters ''maximum range'' and ''average range'' of positions a candidate takes in the input votes. Whereas Kemeny Score remains fixed-parameter tractable with respect to the parameter ''maximum range'', it becomes NP-complete in the case of an average range of two. This excludes fixed-parameter tractability with respect to the parameter ''average range'' unless P=NP. Finally, we extend some of our results to votes with ties and incomplete votes, where in both cases one no longer has permutations as input.

We investigate the Induced Subgraph Isomorphism problem with non-standard parameterization, where the parameter is the difference |V(G)|−|V(H)| with H and G being the smaller and the larger input graph, respectively. Intuitively, we can interpret this problem as “cleaning” the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We show fixed-parameter tractability of the cases where both H and G are planar and H is 3-connected, or H is a tree and G is arbitrary. We also prove that the problem when H and G are both 3-connected planar graphs is NP-complete without parameterization.

In the NP-hard Cluster Editing problem, we have as input an undirected graph G and an integer k>=0. The question is whether we can transform G, by inserting and deleting at most k edges, into a cluster graph, that is, a union of disjoint cliques. We first confirm a conjecture by Michael Fellows [IWPEC 2006] that there is a polynomial-time kernelization for Cluster Editing that leads to a problem kernel with at most 6k vertices. More precisely, we present a cubic-time algorithm that, given a graph G and an integer k>=0, finds a graph G^' and an integer k^'@?k such that G can be transformed into a cluster graph by at most k edge modifications iff G^' can be transformed into a cluster graph by at most k^' edge modifications, and the problem kernel G^' has at most 6k vertices. So far, only a problem kernel of 24k vertices was known. Second, we show that this bound for the number of vertices of G^' can be further improved to 4k vertices. Finally, we consider the variant of Cluster Editing where the number of cliques that the cluster graph can contain is stipulated to be a constant d>0. We present a simple kernelization for this variant leaving a problem kernel of at most (d+2)k+d vertices.

We study the parameterized complexity of the pseudo-achromatic number problem: Given an undirected graph and a parameter k, determine if the graph can be partitioned into k groups such that every two groups are connected by at least one edge. This problem has been extensively studied in graph theory and combinatorial optimization. We show that the problem has a kernel of at most (k−2)(k+1) vertices that is constructable in time O(mn), where n and m are the number of vertices and edges, respectively, in the graph, and k is the parameter. This directly implies that the problem is fixed-parameter tractable. We also study generalizations of the problem and show that they are parameterized intractable.

We consider new parameterizations of NP-optimization problems that have nontrivial lower and/or upper bounds on their optimum solution size. The natural parameter, we argue, is the quantity above the lower bound or below the upper bound. We show that for every problem in MAX SNP, the optimum value is bounded below by an unbounded function of the input-size, and that the above-guarantee parameterization with respect to this lower bound is fixed-parameter tractable. We also observe that approximation algorithms give nontrivial lower or upper bounds on the solution size and that the above or below guarantee question with respect to these bounds is fixed-parameter tractable for a subclass of NP-optimization problems.We then introduce the notion of ‘tight’ lower and upper bounds and exhibit a number of problems for which the above-guarantee and below-guarantee parameterizations with respect to a tight bound is fixed-parameter tractable or W-hard. We show that if we parameterize “sufficiently” above or below the tight bounds, then these parameterized versions are not fixed-parameter tractable unless P=NP, for a subclass of NP-optimization problems. We also list several directions to explore in this paradigm.

The NP-complete Closest 4-Leaf Power problem asks, given an undirected graph, whether it can be modified by at most r edge insertions or deletions such that it becomes a 4-leaf power. Herein, a 4-leaf power is a graph that can be constructed by considering an unrooted tree—the 4-leaf root—with leaves one-to-one labeled by the graph vertices, where we connect two graph vertices by an edge iff their corresponding leaves are at distance at most 4 in the tree. Complementing previous work on Closest 2-Leaf Power and Closest 3-Leaf Power, we give the first algorithmic result for Closest 4-Leaf Power, showing that Closest 4-Leaf Power is fixed-parameter tractable with respect to the parameter r.

In this paper the class of mixed Horn formulas is introduced that contain a Horn part and a 2-CNF (conjunctive normal form) (also called quadratic) part. We show that SAT remains NP-complete for such instances and also that any CNF formula can be encoded in terms of a mixed Horn formula in polynomial time. Further, we provide an exact deterministic algorithm showing that SAT for mixed Horn formulas containing n variables is solvable in time O(2^0^.^5^2^8^4^n). A strong argument showing that it is hard to improve a time bound of O(2^n^/^2) for mixed Horn formulas is provided. We also obtain a fixed-parameter tractability classification for SAT restricted to mixed Horn formulas C of at most k variables in its positive 2-CNF part providing the bound O(@?C@?2^0^.^5^2^8^4^k). We further show that the NP-hard optimization problem minimum weight SAT for mixed Horn formulas can be solved in time O(2^0^.^5^2^8^4^n) if non-negative weights are assigned to the variables. Motivating examples for mixed Horn formulas are level graph formulas [B. Randerath, E. Speckenmeyer, E. Boros, P. Hammer, A. Kogan, K. Makino, B. Simeone, O. Cepek, A satisfiability formulation of problems on level graphs, ENDM 9 (2001)] and graph colorability formulas.

International audience; Haplotype assembly is the computational problem of reconstructing the two parental copies, called haplotypes, of each chromosome starting from sequencing reads, called fragments, possibly affected by sequencing errors. Minimum Error Correction (MEC) is a prominent computational problem for haplotype assembly and, given a set of fragments , aims at reconstructing the two haplotypes by applying the minimum number of base corrections. By using novel combinatorial properties of MEC instances, we are able to provide new results on the fixed-parameter tractability and approx-imability of MEC. In particular, we show that MEC is in FPT when para-meterized by the number of corrections, and, on " gapless " instances, it is in FPT also when parameterized by the length of the fragments, whereas the result known in literature forces the reconstruction of complementary haplotypes. Then, we show that MEC cannot be approximated within any constant factor while it is approximable within factor O(log nm) where nm is the size of the input. Finally, we provide a practical 2-approximation algorithm for the Binary MEC, a variant of MEC that has been applied in the framework of clustering binary data.

International audience; The NP-hard Subset Interconnection Design problem, also known as Minimum Topic-Connected Overlay, is motivated by numerous applications including the design of scalable overlay networks and vacuum systems. It has as input a finite set V and a collection of subsets V 1 , V 2 ,. .. , Vm ⊆ V , and asks for a minimum-cardinality edge set E such that for the graph G = (V, E) all induced subgraphs G[V 1 ], G[V 2 ],. .. , G[Vm] are connected. We study Subset In-terconnection Design in the context of polynomial-time data reduction rules that preserve the possibility to construct optimal solutions. Our contribution is threefold: First, we show the incor-rectness of earlier polynomial-time data reduction rules. Second, we show linear-time solvability in case of a constant number m of subsets, implying fixed-parameter tractability for the parameter m. Third, we provide a fixed-parameter tractability result for small subset sizes and tree-like output graphs. To achieve our results, we elaborate on polynomial-time data reduction rules which also may be of practical use in solving Subset Interconnection Design.

We consider the problem of computing a shortest solid cover of an indeterminate string. An indeterminate string may contain non-solid symbols, each of which specifies a subset of the alphabet that could be present at the corresponding position. We also consider covering partial words, which are a special case of indeterminate strings where each non-solid symbol is a don't care symbol. We prove that indeterminate string covering problem and partial word covering problem are NP-complete for binary alphabet and show that both problems are fixed-parameter tractable with respect to $k$, the number of non-solid symbols. For the indeterminate string covering problem we obtain a $2^{O(k \log k)} + n k^{O(1)}$-time algorithm. For the partial word covering problem we obtain a $2^{O(\sqrt{k}\log k)} + nk^{O(1)}$-time algorithm. We prove that, unless the Exponential Time Hypothesis is false, no $2^{o(\sqrt{k})} n^{O(1)}$-time solution exists for either problem, which shows that our algorithm for this case is close to optimal. We also present an algorithm for both problems which is feasible in practice., full version (simplified and corrected); preliminary version appeared at ISAAC 2014; 14 pages, 4 figures

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8kn) and O(8kk+n3), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.

Many NP-complete problems on planar graphs are “fixed-parameter tractable:” Recent theoretical work provided tree decomposition-based fixed-parameter algorithms exactly solving various parameterized problems on planar graphs, among others VERTEX COVER, in time O(ckn). Here, c is some constant depending on the graph problem to be solved, n is the number of graph vertices, and k is the problem parameter (for VERTEX COVER this is the size of the vertex cover).In this paper, we present an experimental study for such tree decomposition-based algorithms focusing on VERTEX COVER. We demonstrate that the tree decomposition-based approach provides a valuable way of exactly solving VERTEX COVER on planar graphs. Doing so, we also demonstrate the impressive power of the so-called Nemhauser/Trotter theorem which provides a VERTEX COVER-specific, extremely useful data reduction through polynomial time preprocessing. Altogether, this underpins the practical importance of the underlying theory.

We present exact algorithms for the NP-complete LONGEST COMMON SUBSEQUENCE problem for sequences with nested arc annotations, a problem occurring in structure comparison of RNA. Given two sequences of length at most n and nested arc structure, one of our algorithms determines (if existent) in O(3.31k1+k2·n) time an arc-preserving subsequence of both sequences, which can be obtained by deleting (together with corresponding arcs) k1 letters from the first and k2 letters from the second sequence. A second algorithm shows that (in case of a four letter alphabet) we can find a length l arc-annotated subsequence in O(12l·l·n) time. This means that the problem is fixed-parameter tractable when parameterized by the number of deletions as well as when parameterized by the subsequence length. Our findings complement known approximation results which give a quadratic time factor-2-approximation for the general and polynomial time approximation schemes for restricted versions of the problem. In addition, we obtain further fixed-parameter tractability results for these restricted versions.

Given a collection C of subsets of size three of a finite set S and a positive integer k, the 3-Hitting Set problem is to determine a subset S' ⊆ S with |S'| ≤ k, so that S' contains at least one element from each subset in C. The problem is NP-complete, and is motivated, for example, by applications in computational biology. Improving previous work, we give an O(2.270k + n) time algorithm for 3-Hitting Set, which is efficient for small values of k, a typical occurrence in some applications. For d-Hitting Set we present an O(ck + n) time algorithm with c = d - 1 + O(d-1).

In the context of CSPs, a strong backdoor is a subset of variables such that every complete assignment yields a residual instance guaranteed to have a specified property. If the property allows efficient solving, then a small strong backdoor provides a reasonable decomposition of the original instance into easy instances. An important challenge is the design of algorithms that can find quickly a small strong backdoor if one exists. We present a systematic study of the parameterized complexity of backdoor detection when the target property is a restricted type of constraint language defined by means of a family of polymorphisms. In particular, we show that under the weak assumption that the polymorphisms are idempotent, the problem is unlikely to be FPT when the parameter is either r (the constraint arity) or k (the size of the backdoor) unless P = NP or FPT = W[2]. When the parameter is k+r, however, we are able to identify large classes of languages for which the problem of finding a small backdoor is FPT., Comment: 16 pages

International audience; Co-clustering, that is partitioning a numerical matrix into " homogeneous " submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting variants of co-clustering are NP-hard. We focus on the basic variant of co-clustering where the homogeneity of a submatrix is defined in terms of minimizing the maximum distance between two entries. In this context, we spot several NP-hard, as well as a number of relevant polynomial-time solvable special cases, thus charting the border of tractability for this challenging data clustering problem. For instance, we provide polynomial-time solvability when having to partition the rows and columns into two subsets each (meaning that one obtains four submatrices). When partitioning rows and columns into three subsets each, however, we encounter NP-hardness, even for input matrices containing only values from {0, 1, 2}.

A well-studied problem in phylogenetics is to determine the minimum number of hybridization events necessary to explain conflicts among several evolutionary trees, e.g. from different genes. An evolutionary history with hybridization events (or, more generally, reticulations) can be described by a rooted leaf-labelled directed acyclic graph, which is called a phylogenetic network. The reticulation number of such a phylogenetic network can be defined as the sum of all indegrees minus the number of vertices plus one. The considered problem can now formally be stated as follows. Given a finite set \(X\), a collection \(\mathcal {T}\) of rooted phylogenetic trees on \(X\) and \(k\in \mathbb {N}^{+}\), the Hybridization Number problem asks if there exists a rooted phylogenetic network on \(X\) that displays all trees from \(\mathcal {T}\) and has reticulation number at most \(k\). We show that Hybridization Number admits a kernel of size \(4k(5k)^t\) if \(\mathcal {T}\) contains \(t\) (not necessarily binary) rooted phylogenetic trees. In addition, we show a slightly different kernel of size \(20k^2(\varDelta ^+-1)\) with \(\varDelta ^+\) the maximum outdegree of the input trees.