Search

The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We explore this direction for the classic Feedback Vertex Set problem on undirected graphs, leading to a new type of graph structure called antler decomposition , which identifies vertices that belong to an optimal solution. It is an analogue of the celebrated crown decomposition which has been used for Vertex Cover. We develop the graph structure theory around such decompositions and develop fixed-parameter tractable algorithms to find them, parameterized by the number of vertices for which they witness presence in an optimal solution. This reduces the search space of fixed-parameter tractable algorithms parameterized by the solution size that solve Feedback Vertex Set. [ABSTRACT FROM AUTHOR]

This paper studies the problem of finding a path centdian on a tree in which vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. Puerto et al. had an O ( n 5 log ⁡ n ) -time algorithm for this problem. In this paper, we first show that there is a special case which their algorithm does not handle and it is easy to modify their algorithm to cope with this exception. Then, we further present an improved O ( n 4 ) -time algorithm. [ABSTRACT FROM AUTHOR]

A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from π 2 6 − 1 36 + ϵ ≈ 1.617 to 11 7 ≈ 1.571 . Moreover, we show that the algorithm of Khuller et al. [11] for the strongly connected spanning subgraph problem, which achieves an approximation ratio of 1.617, is 1.522-approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results by using interesting conditions for the existence of a second Hamiltonian cycle. [ABSTRACT FROM AUTHOR]

Abstract Shifted combinatorial optimization is a new nonlinear optimization framework broadly extending standard combinatorial optimization, involving the choice of several feasible solutions simultaneously. This framework captures well studied and diverse problems, from sharing and partitioning to so-called vulnerability problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, typically harder. Already with explicitly given input set SCO may be NP -hard. Here we initiate a study of the parameterized complexity of this framework. First we show that SCO over an explicitly given set parameterized by its cardinality may be in XP , FPT or P , depending on the objective function. Second, we study SCO over sets definable in MSO logic (which includes, e.g., the well known MSO-partitioning problems). Our main results are that SCO over MSO definable sets is in XP parameterized by the MSO formula and treewidth (or clique-width) of the input graph, and W [1] -hard even under further severe restrictions. Highlights • Shifted Combinatorial Optimization is an optimization framework involving the choice of several feasible solutions at once. • In this paper, we systematically study SCO, especially from the perspective of parameterized complexity. Our results are: • Parameterized by the size of the feasible set, SCO is XP, FPT and in P for general, decreasing and increasing costs; • For graph properties defined by MSO logic, SCO is in XP parameterized by the formula and the graph tree- or clique-width; • There is an MSO definable partitioning property for which SCO is W[1]-hard over graphs of bounded tree-depth. [ABSTRACT FROM AUTHOR]

Simon's problem is one of the most important problems demonstrating the power of quantum computers. In this paper, we propose another exact quantum algorithm for solving Simon's problem with O ( n ) queries, which is simple, concrete and does not rely on special query oracles. Our algorithm combines Simon's algorithm with the quantum amplitude amplification technique to ensure its determinism. In particular, we show that Simon's problem can be solved by a classical deterministic algorithm with O ( 2 n ) queries (as we are aware, there were no classical deterministic algorithms for solving Simon's problem with O ( 2 n ) queries). Combining some previous results, we obtain the optimal separation in exact query complexities for Simon's problem: Θ ( n ) versus Θ ( 2 n ) . [ABSTRACT FROM AUTHOR]

In the Undirected Eulerian Edge Deletion problem, we are given an undirected graph and an integer k , and the objective is to delete k edges such that the resultant graph is a connected graph in which all the vertices have even degrees. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion . In this paper, using the technique of computing representative families of co-graphic matroids we design algorithms which solve these problems in time 2 O ( k ) n O ( 1 ) , improving the algorithms by Cygan et al. [Algorithmica, 2014] and affirmatively answer the open problem posed by them. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. [ABSTRACT FROM AUTHOR]

The Maximum Agreement Forest problem has been extensively studied in phylogenetics. Most previous work is on two binary phylogenetic trees. In this paper, we study a generalized version of the problem: the Maximum Agreement Forest problem on multiple rooted multifurcating phylogenetic trees, from the perspective of parameterized algorithms. By taking advantage of a new branch-and-bound strategy, a parameterized algorithm with running time O ( 2.42 k m 3 n 4 ) is presented for the problem, assuming that all polytomies in the multifurcating phylogenetic trees are hard. [ABSTRACT FROM AUTHOR]

There has been an increasing growth in numerous applications that naturally generate large volumes of uncertain data. By the advent of such applications, the support of advanced analysis query processing such as the top- k and reverse top- k for uncertain big data has become important. In this paper, we model firstly probabilistic reverse top- k queries over uncertain big data for the discrete situation, in both monochromatic and bichromatic cases, denoted by MPRT and BPRT queries, respectively. We determine the partitions of solution space of MPRT queries and provide in theory a mathematical model for solving arbitrary dimensional data space. Additionally, we propose effective pruning heuristics to reduce the search space of BPRT queries. Moreover, efficient query procedures are presented seamlessly with integration of the proposed pruning strategies. Extensive experiments demonstrate the efficiency and effectiveness of our proposed approaches with various experimental settings. [ABSTRACT FROM AUTHOR]

Several logics for expressing coalitional ability under resource bounds have been proposed and studied in the literature. Previous work has shown that if only consumption of resources is considered or the total amount of resources produced or consumed on any path in the system is bounded, then the model-checking problem for several standard logics, such as Resource-Bounded Coalition Logic (RB-CL) and Resource-Bounded Alternating-Time Temporal Logic (RB-ATL) is decidable. However, for coalition logics with unbounded resource production and consumption, only some undecidability results are known. In this paper, we show that the model-checking problem for RB-ATL with unbounded production and consumption of resources is decidable but EXPSPACE-hard. We also investigate some tractable cases and provide a detailed comparison to a variant of the resource logic RAL, together with new complexity results. [ABSTRACT FROM AUTHOR]

Many problems on graphs can be expressed in the following language: given a graph G = ( V , E ) and a terminal set T ⊆ V , find a minimum size set S ⊆ V which intersects all “structures” (such as cycles or paths) passing through the vertices in T . We refer to this class of problems as terminal set problems. In this paper, we introduce a general method to obtain faster exact exponential time algorithms for several terminal set problems. In the process, we break the O ⁎ ( 2 n ) barrier for the classic Node Multiway Cut , Directed Unrestricted Node Multiway Cut and Directed Subset Feedback Vertex Set problems. [ABSTRACT FROM AUTHOR]

Today's propositional satisfiability (SAT) solvers are extremely powerful and can be used as an efficient back-end for solving NP-complete problems. However, many fundamental problems in logic, in knowledge representation and reasoning, and in artificial intelligence are located at the second level of the Polynomial Hierarchy or even higher, and hence for these problems polynomial-time transformations to SAT are not possible, unless the hierarchy collapses. Recent research shows that in certain cases one can break through these complexity barriers by fixed-parameter tractable (fpt) reductions to SAT which exploit structural aspects of problem instances in terms of problem parameters. These reductions are more powerful because their running times can grow superpolynomially in the problem parameters. In this paper we develop a general theoretical framework that supports the classification of parameterized problems on whether they admit such an fpt-reduction to SAT or not. [ABSTRACT FROM AUTHOR]

Recent research in algorithmic robotics considers combinatorial filters , which concisely capture the discrete structure underlying many reasoning problems for robots. An important recent result is that the filter minimization problem —Given a filter, find the smallest equivalent filter—is NP-hard. This paper extends that result along several dimensions, including hardness proofs for some natural special cases and for approximation, and new results analyzing the only known algorithm for this problem. We show that this problem is not fixed-parameter tractable for any of the obvious parameters, but it is fixed-parameter tractable for a certain combination of new parameters. [ABSTRACT FROM AUTHOR]

In this paper, we consider the applications of digital fingerprinting in oblivious transfer (OT) and present the solutions to the anti-piracy problem in OT protocols. OT protocols can be applied to goods purchasing, pay-per-view TV and sensitive database access while maintaining the users' privacy. In these applications, if the users redistribute the messages that they acquired from the server's database or sell them to others, then both of the server's privacy and benefits will be damaged. Prior to this work, such an anti-piracy problem has never been considered in the OT protocols, even though it is an essential problem to make OT protocols adoptable in practice. In this work, we consider this problem for the first time and present practical solutions, by combining a digital fingerprinting scheme into OT, to provide the pirate-tracing in OT protocols. By performance analysis, our solutions turn out to be practical. [ABSTRACT FROM AUTHOR]

Buresh-Oppenheim proved that the NP search problem to find nontrivial factors of integers of a special form belongs to Papadimitriou's class PPA, and is probabilistically reducible to a problem in PPP. In this paper, we use ideas from bounded arithmetic to extend these results to arbitrary integers. We show that general integer factoring is reducible in randomized polynomial time to a PPA problem and to the problem WeakPigeon ∈ PPP . Both reductions can be derandomized under the assumption of the generalized Riemann hypothesis. We also show (unconditionally) that PPA contains some related problems, such as square root computation modulo n , and finding quadratic nonresidues modulo n . [ABSTRACT FROM AUTHOR]

Wireless Mesh Networks (WMNs) are an important networking paradigm that offer cost effective Internet connectivity. The performance and operability of WMNs depend, among other factors, on the placement of network nodes in the area. Among the most important objectives in designing a WMN is the formation of a mesh backbone to achieve high user coverage. Given a number of router nodes to deploy, a deployment area and positions of client nodes in the area, an optimization problem can be formulated aiming to find the placement of router nodes so as to maximize network connectivity and user coverage. This optimization problem belongs to facility location problems, which are computationally hard to solve to optimality. In this paper we present the implementation and evaluation of Tabu Search (TS) for the problem of mesh router node placement in WMNs. The experimental evaluation showed the efficiency of TS in solving a benchmark of instances. [ABSTRACT FROM AUTHOR]

Pancake Flipping is the problem of sorting a stack of pancakes of different sizes (that is, a permutation), when the only allowed operation is to insert a spatula anywhere in the stack and to flip the pancakes above it (that is, to perform a prefix reversal). In the burnt variant, one side of each pancake is marked as burnt, and it is required to finish with all pancakes having the burnt side down. Computing the optimal scenario for any stack of pancakes and determining the worst-case stack for any stack size have been challenges for over more than three decades. Beyond being an intriguing combinatorial problem in itself, it also yields applications, e.g. in parallel computing and computational biology. In this paper, we show that the Pancake Flipping problem, in its original (unburnt) variant, is NP -hard, thus answering the long-standing question of its computational complexity. [ABSTRACT FROM AUTHOR]

This paper studies the problem of finding the path median on a tree in which vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. An O ( n 2 ) -time algorithm is presented, improving the previous upper bound from O ( n 4 ) . [ABSTRACT FROM AUTHOR]

Since Chandra and Toueg introduced the failure detector abstraction for crash-prone systems, several algorithms implementing failure detectors in partially synchronous systems have been proposed. Their performance can be measured by their Communication efficiency , defined as the number of links used forever. In this regard, in a communication-efficient algorithm only n links are used forever, n being the number of processes in the system. In this paper, we present communication optimality , a communication efficiency degree reached when only c links are used forever, c being the number of correct processes. We show that c is the minimum number of links used forever required to implement ◇ P and that c is also optimal for ◇ S and Ω when c < n . Finally, we propose two communication-optimal ◇ P algorithms following respectively one-to-all and one-to-one communication patterns to manage suspicions, showing that there is a trade-off between detection latency and sporadic communication overhead. [ABSTRACT FROM AUTHOR]

This paper proposes a purpose-based access control model in distributed computing environment for privacy preserving policies and mechanisms, and describes algorithms for policy conflicting problems. The mechanism enforces access policy to data containing personally identifiable information. The key component is purpose involved access control models for expressing highly complex privacy-related policies with various features. A policy refers to an access right that a subject can have on an object, based on attribute predicates, obligation actions, and system conditions. Policy conflicting problems may arise when new access policies are generated that are possible to be conflicted to existing policies. As a result of the policy conflicts, private information cannot be well protected. The structure of purpose involved access control policy is studied, and efficient conflict-checking algorithms are developed and implemented. Finally a discussion of our work in comparison with other related work such as EPAL is presented. [ABSTRACT FROM AUTHOR]

Abstract: Minimum Fill-in is a fundamental and classical problem arising in sparse matrix computations. In terms of graphs it can be formulated as a problem of finding a triangulation of a given graph with the minimum number of edges. In this paper, we study the parameterized complexity of local search for the Minimum Fill-in problem in the following form: Given a triangulation H of a graph G, is there a better triangulation, i.e. triangulation with less edges than H, within a given distance from H? We prove that this problem is fixed-parameter tractable (FPT) being parameterized by the distance from the initial triangulation, by providing an algorithm that in time decides if a better triangulation of G can be obtained by swapping at most k edges of H. Our result adds Minimum Fill-in to the list of very few problems for which local search is known to be FPT. [Copyright &y& Elsevier]

Abstract: We consider nondeterministic concurrent games played on event structures and study their determinacy problem—the existence of winning strategies. It is known that when the winning conditions of the games are characterised by a collection of finite winning sets/plays, a restriction (called race-freedom) on the boards where the games are played guarantees determinacy. However the games may no longer be determined when the winning sets are infinite. This paper provides a study of concurrent games and nondeterministic winning strategies by analysing conditions that ensure determinacy when infinitely many events are played, that is, when the winning sets are infinite. The main result is a determinacy theorem for a class of games with a bounded concurrency property and infinite winning sets shown to be finitely decidable. [Copyright &y& Elsevier]

Abstract: In this paper, we study a generalization of the classical minimum cut problem, called Connectivity Preserving Minimum Cut (CPMC) problem, which seeks a minimum cut to separate a pair (or pairs) of source and destination nodes and meanwhile ensure the connectivity between the source and its partner node(s). For this problem, we consider two variants, connectivity preserving minimum node cut (CPMNC) and connectivity preserving minimum edge cut (CPMEC). For CPMNC, we show that it cannot be approximated within α logn for some constant α unless , and cannot be approximated within any unless NP has quasi-polynomial time algorithms. The hardness results hold even for graphs with unit weight and bipartite graphs. For CPMEC, we show that it is in P for planar graphs. [Copyright &y& Elsevier]

Abstract: This paper is a study of weighted counting of the solutions of acyclic conjunctive queries (ACQ). The unweighted quantifier free version of this problem is known to be tractable (for combined complexity), but it is also known that introducing even a single quantified variable makes it -hard. We first show that weighted counting for quantifier free ACQ is still tractable and that even minimalistic extensions of the problem lead to hard cases. We then introduce a new parameter for quantified queries that permits to isolate a large island of tractability. We show that, up to a standard assumption from parameterized complexity, this parameter fully characterizes tractable subclasses for counting weighted solutions for ACQs. Thus we completely determine the tractability frontier for weighted counting for ACQ. [Copyright &y& Elsevier]

Abstract: In this paper we investigate, from a theoretical perspective, the problem of how to build speculative replication protocols for transactional systems layered on top of an Optimistic Atomic Broadcast (OAB) service. The OAB service provides an early, possibly erroneous, guess on transactionʼs final serialization order. This can be exploited to speculatively execute transactions in parallel with the algorithm used to determine their final total delivery (and serialization) order. To maximize the chances of guessing their final serialization order, transactions are executed multiple times, speculating on the possible orderings eventually determined by the OAB service. We formalize the Speculative Transactional Replication (STR) problem by means of a set of properties ensuring that transactions are never activated on inconsistent snapshots, as well as the minimality and completeness of the set of speculatively explored serialization orders. Finally, we present a protocol solving the STR problem, along with simulation results assessing its effectiveness. [Copyright &y& Elsevier]

Abstract: In this paper we study the model-checking problem for probabilistic pushdown automata (pPDA) and branching-time probabilistic logics PCTL and PCTL⁎. We show that model-checking pPDA against general PCTL formulae is undecidable, but we yield positive decidability results for the qualitative fragments of PCTL and PCTL⁎. For these fragments, we also give a complete complexity classification. [Copyright &y& Elsevier]

Abstract: Hierarchical multi-label classification is a complex classification task where the classes involved in the problem are hierarchically structured and each example may simultaneously belong to more than one class in each hierarchical level. In this paper, we extend our previous works, where we investigated a new local-based classification method that incrementally trains a multi-layer perceptron for each level of the classification hierarchy. Predictions made by a neural network in a given level are used as inputs to the neural network responsible for the prediction in the next level. We compare the proposed method with one state-of-the-art decision-tree induction method and two decision-tree induction methods, using several hierarchical multi-label classification datasets. We perform a thorough experimental analysis, showing that our method obtains competitive results to a robust global method regarding both precision and recall evaluation measures. [Copyright &y& Elsevier]

Abstract: Conjunctive queries (CQs) are one of the most fundamental forms of database queries. In general, the evaluation of CQs is -complete. Consequently, there has been an intensive search for tractable fragments. In this paper, we want to initiate a systematic search for tractable fragments of the counting problem of CQs, i.e., the problem of counting the answers to a CQ. We prove several new tractability and intractability results by starting with acyclic conjunctive queries and generalising these results to CQs of bounded hypertree-width. We also extend our study to the counting problem of unions of CQs. [Copyright &y& Elsevier]

Abstract: With the advent of new sequencing technologies able to produce an enormous quantity of short genomic sequences, new tools able to search for them inside a genomic reference sequence have emerged. Because of chemical reading errors or of the variability between organisms, one is interested in finding not only exact occurrences, but also occurrences with up to k mismatches. The contribution of this paper is twofold. On the one hand, we present a generalization of the classical Rabin–Karp string matching algorithm to solve the k-mismatch problem, with average complexity (n text and m pattern lengths, respectively). On the other hand, we show how to employ this idea in conjunction with an index over the text, allowing to search a pattern, with up to k mismatches, in time proportional to its length. This novel tool—rNA (randomized Numerical Aligner)—is in general faster and more accurate than other available tools like SOAP2, BWA, and BOWTIE. rNA executables and source code are freely available at http://iga-rna.sourceforge.net/ . [Copyright &y& Elsevier]

Abstract: Many problems of artificial intelligence, or more generally, many problems of information processing, have a generic solution based on local computation on join trees or acyclic hypertrees. There are several variants of this method all based on the algebraic structure of valuation algebras. A strong requirement underlying this approach is that the elements of a problem decomposition form a join tree. Although it is always possible to construct covering join trees, if the requirement is originally not satisfied, it is not always possible or not efficient to extend the elements of the decomposition to the covering join tree. Therefore in this paper different variants of an axiomatic framework of valuation algebras are introduced which prove sufficient for local computation without the need of an extension of the factors of a decomposition. This framework covers the axiomatic system proposed by Shenoy and Shafer (1990) . A particular emphasis is laid on the important special cases of idempotent algebras and algebras with some notion of division. It is shown that all well-known architectures for local computation like the Shenoy–Shafer architecture, Lauritzen–Spiegelhalter and HUGIN architectures may be adapted to this new framework. Further a new architecture for idempotent algebras is presented. As examples, in addition to the classical instances of valuation algebras, semiring-based valuation algebras, Gaussian potentials and the relational algebra are presented. [Copyright &y& Elsevier]

Abstract: Context-free grammars are widely used for the simple form of their rules. A derivation step consists of the choice of a nonterminal of the sentential form and of an application of a rule rewriting it. Several regulations of the derivation process have been studied to increase the power of context-free grammars. In the resulting grammars, however, not only the symbols to be rewritten are restricted, but also the rules to be applied. In this paper, we study context-free grammars with a simpler restriction where only symbols to be rewritten are restricted, not the rules, in the sense that any rule rewriting the chosen nonterminal can be applied. We prove that these grammars have the same power as random context, matrix, or programmed grammars. We also present two improved normal forms and discuss the characterization of context-sensitive languages by a variant using strings of length at most two instead of symbols. [Copyright &y& Elsevier]

Abstract: The cluster editing problem is a decision problem that, for a graph G and a parameter k, determines if one can apply at most k edge insertion/deletion operations on G so that the resulting graph becomes a union of disjoint cliques. The problem has attracted much attention because of its applications in a variety of areas. In this paper, we present a polynomial-time kernelization algorithm for the problem that produces a kernel of size bounded by 2k. More precisely, we develop an -time algorithm that, on a graph G of n vertices and m edges and a parameter k, produces a graph and a parameter such that , that has at most vertices, and that is a yes-instance if and only if is a yes-instance of the cluster editing problem. This improves the previously best kernel of size 4k for the problem. [Copyright &y& Elsevier]

Abstract: View-based query answering is the problem of answering a query based only on the precomputed answers to a set of views. While this problem has been widely investigated in databases, it is largely unexplored in the context of Description Logic ontologies. Differently from traditional databases, Description Logics may express several forms of incomplete information, and this poses challenging problems in characterizing the semantics of views. In this paper, we first present a general framework for view-based query answering, where we address the above semantical problems by providing two notions of view-based query answering over ontologies, all based on the idea that the precomputed answers to views are the certain answers to the corresponding queries. We also relate such notions to privacy-aware access to ontologies. Then, we provide decidability results, algorithms, and data complexity characterizations for view-based query answering in several Description Logics, ranging from those with limited modeling capability to highly expressive ones. [Copyright &y& Elsevier]

Abstract: We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D. We consider two versions of the problem: 1) Filtering Problem: Determine if there is a match for Q in D. 2) Node Selection Problem: Determine the set of document nodes selected by Q. We consider Conjunctive XPath (CXPath) queries that involve only the child and descendant axes. Let d denote the depth of D, and n denote the number of location steps in Q. Bar-Yossef et al. (2007, 2005) presented lower bounds on the memory space required by any algorithm to solve these two problems. Their lower bounds apply to each query in a large subset of XPath, and are obtained (mostly) using nonrecursive . In this paper, we present larger lower bounds for a different class of queries (namely, CXPath queries with independent predicates), on recursive . One of our results is an lower bound for the node selection problem, for a worst-case Q; is the maximum number of nodes of D that can be candidates for output, at any one instant. So, there is no algorithm for the node selection problem that uses space, for any function f. This shows that some previously published algorithms are incorrect. [Copyright &y& Elsevier]

Abstract: A tournament is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance on vertices. In fact, given any fixed , the kernelized instance has at most vertices. Our result improves the previous known bound of on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST. [Copyright &y& Elsevier]

Abstract: We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D; i.e., determine the set of document elements selected by Q. We mainly consider Conjunctive XPath queries that involve only the child and descendant axes. Previously known in-memory algorithms for this problem use space and time. Several previously known algorithms for the streaming version use space and time in the worst case; d denotes the depth of D, and n denotes the number of location steps in Q. Their exponential space requirement could well exceed the space used by the in-memory algorithms. We present an efficient algorithm that uses space and time in the worst case; c denotes the maximum number of elements of D that can be candidates for output, at any one instant. For some worst case Q and D, the memory space used by our algorithm matches our lower bound proved in a different paper; so, our algorithm uses optimal memory space in the worst case. [Copyright &y& Elsevier]

Abstract: In this paper, we study the inverse sorting problem with bound constraints under the -norm and the Hamming distance. For the problem under the -norm, an -time algorithm is presented. For the problem under the Hamming distance, we first show that it has an -time lower bound in the comparison model; and then, we present an -time algorithm. Both of the presented algorithms improve the previous upper bounds from . [Copyright &y& Elsevier]

Abstract: Kernelization is a strong and widely-applied technique in parameterized complexity. A kernelization algorithm, or simply a kernel, is a polynomial-time transformation that transforms any given parameterized instance to an equivalent instance of the same problem, with size and parameter bounded by a function of the parameter in the input. A kernel is polynomial if the size and parameter of the output are polynomially-bounded by the parameter of the input. In this paper we develop a framework which allows showing that a wide range of FPT problems do not have polynomial kernels. Our evidence relies on hypothesis made in the classical world (i.e. non-parametric complexity), and revolves around a new type of algorithm for classical decision problems, called a distillation algorithm, which is of independent interest. Using the notion of distillation algorithms, we develop a generic lower-bound engine that allows us to show that a variety of FPT problems, fulfilling certain criteria, cannot have polynomial kernels unless the polynomial hierarchy collapses. These problems include k-Path, k-Cycle, k-Exact Cycle, k-Short Cheap Tour, k-Graph Minor Order Test, k-Cutwidth, k-Search Number, k-Pathwidth, k-Treewidth, k-Branchwidth, and several optimization problems parameterized by treewidth and other structural parameters. [Copyright &y& Elsevier]

Abstract: In this paper, a new method for handling multicriteria fuzzy decision-making problems based on intuitionistic fuzzy sets is presented. The proposed method allows the degrees of satisfiability and non-satisfiability of each alternative with respect to a set of criteria to be represented by intuitionistic fuzzy sets, respectively. Furthermore, the proposed method allows the decision-maker to assign the degrees of membership and non-membership of the criteria to the fuzzy concept “importance.” The method proposed here can provide a useful way to efficiently help the decision-maker to make his decision. [Copyright &y& Elsevier]

Fixed-parameter tractability (FPT) techniques have recently been successful in solving NP-complete problem instances of practical importance which were too large to be solved with previous methods. In this paper, we show how to enhance this approach through the addition of parallelism, thereby allowing even larger problem instances to be solved in practice. More precisely, we demonstrate the potential of parallelism when applied to the bounded-tree search phase of FPT algorithms. We apply our methodology to the k-Vertex Cover problem which has important applications in, for example, the analysis of multiple sequence alignments for computational biochemistry. We have implemented our parallel FPT method for the k-Vertex Cover problem using C and the MPI communication library, and tested it on a 32-node Beowulf cluster. This is the first experimental examination of parallel FPT techniques. As part of our experiments, we solved larger instances of k-Vertex Cover than in any previously reported implementations. For example, our code can solve problem instances with k&ges;400 in less than 1.5 h. [Copyright &y& Elsevier]

Highlights: [•] This special issue is about Intelligent Data Analysis (IDL). [•] IDL uses methods and software tools to solve data analysis problems. [•] It contains 9 substantially extended and updated papers from ISDA-2011. [•] ISDA (International Conference on Intelligent Systems Design and Applications). [ABSTRACT FROM AUTHOR]