Search

In this paper we consider the Maximum Independent Set problem (MIS) on B 1 -EPG graphs, that is the one-bend ( B 1 ) Edge intersection graphs of Paths on a Grid (EPG graphs). The graph class EPG was introduced in Golumbic et al. (2019) as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class B k -EPG denotes EPG-graphs where every path has at most k bends. The study of MIS on B 1 -EPG graphs has been initiated in Epstein et al. (2013) where authors prove that MIS is NP-complete on B 1 -EPG graphs, and provide a polynomial 4-approximation. In this article we study the approximability and the fixed parameter tractability of MIS on B 1 -EPG. We show that the class of k ≥ 4 subdivided graphs is a subclass of B 1 -EPG, even if there is only one shape of path and if each path has its vertical part or its horizontal part of length at most 1. This implies that there is no PTAS for MIS (and several other classical problems) on these particular B 1 -EPG graphs. On the positive side, we show that if the length of the horizontal part of every path is bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on B 1 -EPG restricted to only three shapes of path, and W [ 1 ] -hard on B 2 -EPG. The status for general B 1 -EPG (with the four shapes) is left open.

Here we show that deciding whether two rooted binary phylogenetic trees on the same set of taxa permit a cherry-picking sequence, a special type of elimination order on the taxa, is NP-complete. This improves on an earlier result which proved hardness for eight or more trees. Via a known equivalence between cherry-picking sequences and temporal phylogenetic networks, our result proves that it is NP-complete to determine the existence of a temporal phylogenetic network that contains topological embeddings of both trees. The hardness result also greatly strengthens previous inapproximability results for the minimum temporal-hybridization number problem. This is the optimization version of the problem where we wish to construct a temporal phylogenetic network that topologically embeds two given rooted binary phylogenetic trees and that has a minimum number of indegree-2 nodes, which represent events such as hybridization and horizontal gene transfer. We end on a positive note, pointing out that fixed parameter tractability results in this area are likely to ensure the continued relevance of the temporal phylogenetic network model., Fixed some tiny things. Accepted for journal publication

Many NP-hard problems on graphs become tractable on graphs of low treewidth, but the corresponding algorithms require access to a tree decomposition of the graph of low (ideally, minimum) width. Unfortunately computation of treewidth is itself NP-hard and a wide variety of exact, heuristic and approximation algorithms have been proposed for this problem. To support this ongoing research we present here ToTo, an open graph database for computation, storage and rapid retrieval of tree decompositions. We hope that the database will become both a central repository for important graphs and benchmark datasets and extend the use of treewidth beyond the usual communities: the database and associated algorithms can be accessed via a web browser and do not require installation of any specialist software. (C) 2016 Elsevier B.V. All rights reserved.