complexity

‎Let $r\geq 2$. A subset $S$ of vertices of a graph $G$ is a $r$-hop independent dominating set if every vertex outside $S$ is at distance $r$ from a vertex of $S$, and for any pair $v, w\in S$, $d(v, w)\neq r$. A $r$-hop Roman dominating function ($r$HRDF) is a function $f$ on $V(G)$ with values $0,1$ and $2$ having the property that for every vertex $v \in V$ with $f(v) = 0$ there is a vertex $u$ with $f(u)=2$ and $d(u,v)=r$. A $r$-step Roman dominating function ($r$SRDF) is a function $f$ on $V(G)$ with values $0,1$ and $2$ having the property that for every vertex $v$ with $f(v)=0$ or $2$, there is a vertex $u$ with $f(u)=2$ and $d(u,v)=r$. A $r$HRDF $f$ is a $r$-hop Roman independent dominating function if for any pair $v, w$ with non-zero labels under $f$, $d(v, w)\neq r$. We show that the decision problem associated with each of $r$-hop independent domination, $r$-hop Roman domination, $r$-hop Roman independent domination and $r$-step Roman domination is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs.

Let $G$ be a weighted digraph, $s$ and $t$ be two vertices of $G$, and $t$ is reachable from $s$. The logical $s$-$t$ min-cut (LSTMC) problem states how $t$ can be made unreachable from $s$ by removal of some edges of $G$ where (a) the sum of weights of the removed edges is minimum and (b) all outgoing edges of any vertex of $G$ cannot be removed together. If we ignore the second constraint, called the logical removal, the LSTMC problem is transformed to the classic $s$-$t$ min-cut problem. The logical removal constraint applies in situations where non-logical removal is either infeasible or undesired. Although the $s$-$t$ min-cut problem is solvable in polynomial time by the max-flow min-cut theorem, this paper shows the LSTMC problem is NP-Hard, even if $G$ is a DAG with an out-degree of two. Moreover, this paper shows that the LSTMC problem cannot be approximated within $alpha log n$ in a DAG with $n$ vertices for some constant $alpha$. The application of the LSTMC problem is also presented intest case generation of a computer program.

Choosing the appropriate strategy is the most vital decision for an organization. The real-world situation, comprising increasing criteria and alternatives; the criteria interdependency; environmental changes affecting the structure of the organization; the vagueness of the verbal judgments; and Increasing uncertainty about possible futures, forces the decision-makers to consider these two important elements, complexity and uncertainty, in their decision-making approach. While all of the most widely known approaches – the classic, scenario, MCDM, and robustness analysis approaches – have some weaknesses related to either complexity or uncertainty, the approach purposed in this study can overcome them, combining the matrix approach to the robustness analysis (MARA) with the fuzzy ANP method. This approach deals with the environmental uncertainty by reviewing the performance of the strategies among the alternative futures, the uncertainty related to the preference model of the human decision-maker (uncertain judgements) by using fuzzy set theory, specifically Chang’s extent analysis method, considers desired number of scenarios, criteria and options, and collects experts' judgments in an appropriate time, emphasizing interdependences among criteria. The proposed approach is applied to a real-world problem in the automotive industry of Iran and the results are compared with the previous studies.

Let G be a digraph with positive edge weights as well as s and t be two vertices of G. The marking problem (MP) states how to mark some edges of G with T and F, where every path starting at source s will reach target t and the total weight of the marked edges is minimal. When traversing the digraph, T-marked edges should be followed while Fmarked edges should not. The basic applications and properties of the marking problem have been investigated in [1]. This paper provides new contributions to the marking problem as follows: (i) the MP is NP-Complete even if the underlying digraph is an unweighted binary DAG; (ii) the MP cannot be approximated within α logn in an unweighted DAG with n vertices and even in an unweighted binary DAG. Furthermore, a lower bound to the optimal solution of the MP is provided. We also study the complexity and challenges of the marking problem in program flow graphs.

In this paper, we study the directed multicut and directed multimultiway cut problems. The input to the directed multi-multiway cut problem is a weighted directed graph G = (V, E) and k sets S1, S2, ..., Sk of vertices. The goal is to find a subset of edges of minimum total weight whose removal will disconnect all the connections between the vertices in each set Si , for 1 ≤ i ≤ k. A special case of this problem is the directed multicut problem whose input consists of a weighted directed graph G = (V, E) and a set of ordered pairs of vertices (s1, t1), ...,(sk, tk). The goal is to find a subset of edges of minimum total weight whose removal will make for any i, 1 ≤ i ≤ k, there is no directed path from si to ti . In this paper, we present two approximation algorithms for these problems. The so called region growing paradigm is modified and used for these two cut problems on directed graphs. using this paradigm, we give an approximation algorithm for each problem such that both algorithms have the approximation factor of O(k) the same as the previous works done on these problems. However, the previous works need to solve k linear programming, whereas our algorithms require only one linear programming. Therefore, our algorithms improve the running time of the previous algorithms.

The main purpose of this paper is to achieve improvement in the speed of Fuzzy Joint Points (FJP) algorithm. Since FJP approach is a basis for fuzzy neighborhood based clustering algorithms such as Noise-Robust FJP (NRFJP) and Fuzzy Neighborhood DBSCAN (FN-DBSCAN), improving FJP algorithm would an important achievement in terms of these FJP-based meth- ods. Although FJP has many advantages such as robustness, auto detection of the optimal number of clusters by using cluster validity, independency from scale, etc., it is a little bit slow. In order to eliminate this disadvantage, by im- proving the FJP algorithm, we propose a novel Modi ed FJP algorithm, which theoretically runs approximately n= log2 n times faster and which is less com- plex than the FJP algorithm. We evaluated the performance of the Modi ed FJP algorithm both analytically and experimentally.