We consider the following problem: given an undirected (mixed) network and a set of ordered source–target pairs, or cause–effect pairs, direct all edges so as to maximize the number of pairs that admit a directed source–target path. This is called the maximum graph orientation problem, and has applications in understanding interactions in protein–protein interaction networks. Since this problem is NP-hard, we take the parameterized complexity viewpoint and study the parameterized (in) tractability of the problem with respect to various parameters on both undirected and mixed networks. In the undirected case, we determine the parameterized complexity of the problem (for non-fixed and fixed paths) with respect to the number of satisfi

We consider an augmentation problem to establish point-to-point connectivity on unweighted graphs where there is no restriction on choosing the augmenting edges (arcs). Given a directed (an undirected) graph G and set P={(s i, t i): 1≤ i≤ m} of pairs of vertices in the graph, one has to find the minimum cardinality set of arcs (edges) to be added to the graph so that the resulting graph has (can be oriented in order to have) directed paths between the specified pairs of vertices. In the case of undirected graphs, an efficient polynomial-time algorithm is presented. In the case of directed graphs, we find that this problem is NP-hard. In addition, we show that it is fixed-parameter tractable with respect to the combined parameter the num

We consider the directed Steiner network problem, where given a weighted directed graph and pairs of vertices , one has to find the minimum weight subgraph of that contains path from to for all . We search for the main cause of the complexity of the problem and introduce the notions of junction vertex and shared segment in an optimal solution. We study the parameterized complexity of the problem with respect to these parameters and achieve several parameterized hardness results. Also, we present two output-sensitive algorithms for the problem, which are much simpler and easier to implement than the previously best known one; and in addition, when the paths corresponding to the input pairs have few shared vertices or arcs in the optima

We consider the following problem: Given an undirected (mixed) network and a set of ordered source-target, or cause-effect pairs, direct all edges so as to maximize the number of pairs that admit a directed source-target path. This is called maximum graph orientation problem, and has applications in understanding interactions in protein-protein interaction networks and protein-DNA interaction networks. We have studied the problem on both undirected and mixed networks. In the undirected case, we determine the parameterized complexity of the problem (for non-fixed and fixed paths) with respect to the number of satisfied pairs, which has been an open problem. Also, we present an exact algorithm which outperforms the previous algorithms on tree

We consider an augmentation problem on undirected and directed graphs, where given a directed (an undirected) graph G and p pairs of vertices , one has to find the minimum weight set of arcs (edges) to be added to the graph so that the resulting graph has (can be oriented to have) directed paths between the specified pairs of vertices. In the undirected case, we present an FPT-algorithm with respect to the number of new edges. Also, we have implemented and evaluated the algorithm on some real-world networks to show its efficiency in decreasing the size of input graphs and converting them to much smaller kernels. In the directed case, we consider the complexity of the problem with respect to the various parameters and present

In this paper, we study the problem of modifying a graph such that the resulting graph has a dominating set of size at most k. Solving this problem determines the minimum number of edges to be added to a given graph such that at most k vertices can dominate all vertices. We show that this problem is NP-hard, and therefore, has no polynomial-time algorithm (unless P= NP). Also, we show that the problem is FPT parameterized by the treewidth of the input graph. Furthermore, we show that the problem parameterized by k is W [2]-hard and belongs to W [P].

DNA computing as a powerful interdisciplinary field has been found to be very useful and applicable for solving NP-complete and intractable problems because of its huge power in parallel processing. In recent years many efforts have been done to solve NP-complete and time consuming problems with the help of DNA computing. In this paper, we use sticker model (one of the most well-known models of DNA computing) to present three DNA algorithms for solving three different NP-complete graph-based problems for the first time: domatic partition, kernel and induced path. Also we have simulated these algorithms to show their correctness.