On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q >= 2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q >= 2, and has been well-studied from the point of view of approximation. Our main focus is the case when q = 2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.

On the Communication Complexity of Secret Key Generation in the Multiterminal Source Model

Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszar and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.

Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR)

QR decomposition (QRD) is a widely used Numerical Linear Algebra (NLA) kernel with applications ranging from SONAR beamforming to wireless MIMO receivers. In this paper, we propose a novel Givens Rotation (GR) based QRD (GR QRD) where we reduce the computational complexity of GR and exploit higher degree of parallelism. This low complexity Column-wise GR (CGR) can annihilate multiple elements of a column of a matrix simultaneously. The algorithm is first realized on a Two-Dimensional (2 D) systolic array and then implemented on REDEFINE which is a Coarse Grained run-time Reconfigurable Architecture (CGRA). We benchmark the proposed implementation against state-of-the-art implementations to report better throughput, convergence and scalability.

Low Complexity Power and Scheduling Policies for Wireless Networks to Provide Quality of Service

We consider optimal power allocation policies for a single server, multiuser system. The power is consumed in transmission of data only. The transmission channel may experience multipath fading. We obtain very efficient, low computational complexity algorithms which minimize power and ensure stability of the data queues. We also obtain policies when the users may have mean delay constraints. If the power required is a linear function of rate then we exploit linearity and obtain linear programs with low complexity.

Impacts of climate change and management responses in tropical forests depend on complex frugivore-mediated seed dispersal

AimBiodiversity outcomes under global change will be influenced by a range of ecological processes, and these processes are increasingly being considered in models of biodiversity change. However, the level of model complexity required to adequately account for important ecological processes often remains unclear. Here we assess how considering realistically complex frugivore-mediated seed dispersal influences the projected climate change outcomes for plant diversity in the Australian Wet Tropics (all 4313 species). LocationThe Australian Wet Tropics, Queensland, Australia. MethodsWe applied a metacommunity model (M-SET) to project biodiversity outcomes using seed dispersal models that varied in complexity, combined with alternative climate change scenarios and habitat restoration scenarios. ResultsWe found that the complexity of the dispersal model had a larger effect on projected biodiversity outcomes than did dramatically different climate change scenarios. Applying a simple dispersal model that ignored spatial, temporal and taxonomic variation due to frugivore-mediated seed dispersal underestimated the reduction in the area of occurrence of plant species under climate change and overestimated the loss of diversity in fragmented tropical forest remnants. The complexity of the dispersal model also changed the habitat restoration approach identified as the best for promoting persistence of biodiversity under climate change. Main conclusionsThe consideration of complex processes such as frugivore-mediated seed dispersal can make an important difference in how we understand and respond to the influence of climate change on biodiversity.

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

Change in Mesoherbivore Browsing Is Mediated by Elephant and Hillslope Position

Elephant are considered major drivers of ecosystems, but their effects within small-scale landscape features and on other herbivores still remain unclear. Elephant impact on vegetation has been widely studied in areas where elephant have been present for many years. We therefore examined the combined effect of short-term elephant presence (< 4 years) and hillslope position on tree species assemblages, resource availability, browsing intensity and soil properties. Short-term elephant presence did not affect woody species assemblages, but did affect height distribution, with greater sapling densities in elephant access areas. Overall tree and stem densities were also not affected by elephant. By contrast, slope position affected woody species assemblages, but not height distributions and densities. Variation in species assemblages was statistically best explained by levels of total cations, Zinc, sand and clay. Although elephant and mesoherbivore browsing intensities were unaffected by slope position, we found lower mesoherbivore browsing intensity on crests with high elephant browsing intensity. Thus, elephant appear to indirectly facilitate the survival of saplings, via the displacement of mesoherbivores, providing a window of opportunity for saplings to grow into taller trees. In the short-term, effects of elephant can be minor and in the opposite direction of expectation. In addition, such behavioural displacement promotes recruitment of saplings into larger height classes. The interaction between slope position and elephant effect found here is in contrast with other studies, and illustrates the importance of examining ecosystem complexity as a function of variation in species presence and topography. The absence of a direct effect of elephant on vegetation, but the presence of an effect on mesoherbivore browsing, is relevant for conservation areas especially where both herbivore groups are actively managed.

Development of cup shaped microneedle array for transdermal drug delivery

Microneedle technology is one of the attractive methods in transdermal drug delivery. However, the clinical applications of this method are limited owing to: complexity in the preparation of multiple coating solutions, drug leakage while inserting the microneedles into the skin and the outer walls of the solid microneedle can hold limited quantity of drug. Here, the authors present the fabrication of an array of rectangular cup shaped silicon microneedles, which provide for reduced drug leakage resulting in improvement of efficiency of drug delivery and possibility of introducing multiple drugs. The fabricated solid microneedles with rectangular cup shaped tip have a total height of 200 mu m. These cup shaped tips have dimensions: 60 x 60 mu m (length x breadth) with a depth of 60 mu m. The cups are filled with drug using a novel in-house built drop coating system. Successful drug dissolution was observed when the coated microneedle was used on mice. Also, using the above method, it is possible to fill the cups selectively with different drugs, which enables simultaneous multiple drug delivery. (C) 2015 American Vacuum Society.

Recent freshwater Ostracoda and Bivalvia from Indo-Nepal border (Tethys Himalaya): Ecological implications

We report for the first time Recent ostracods and bivalves from Central Tethys Himalaya, collected from Changru village, which is situated in the Tinker valley of northwestern Nepal near the Indo-Nepal border. The specimens were collected from the surface sediments of a small pond, shaped by a small tributary of the glacier fed Tinker River. The ostracod species belonging to the families Ilyocyprididae, Cyprididae and Candonidae and one bivalve (Pisidium sp., Family Pisidiidae) have been identified. Psychrodromus olivaccus and Potamocypris villosa are being reported for the first time from India and Nepal. Several broken and unidentifiable gyrogonites of charophyta were also recovered. The ostracod sample, as a whole, points to a shallow freshwater lake environment influenced by slowly running carbonate rich waters under cool temperatures, low mineralization and sparse vegetation. This is in accordance with the occurrence of Pisidium, which is commonly associated with ostracods in the freshwater lakes and streams. The ostracod fauna shows affinity with the fossil and extant forms recovered from the Higher and Tethys Himalaya of NW India. This opens a new opportunity for studying ostracods in the Indian Central Himalaya - a region which otherwise has been ignored until now.

Primates, Provisioning and Plants: Impacts of Human Cultural Behaviours on Primate Ecological Functions

Human provisioning of wildlife with food is a widespread global practice that occurs in multiple socio-cultural circumstances. Provisioning may indirectly alter ecosystem functioning through changes in the eco-ethology of animals, but few studies have quantified this aspect. Provisioning of primates by humans is known to impact their activity budgets, diets and ranging patterns. Primates are also keystone species in tropical forests through their role as seed dispersers; yet there is no information on how provisioning might affect primate ecological functions. The rhesus macaque is a major human-commensal species but is also an important seed disperser in the wild. In this study, we investigated the potential impacts of provisioning on the role of rhesus macaques as seed dispersers in the Buxa Tiger Reserve, India. We studied a troop of macaques which were provisioned for a part of the year and were dependent on natural resources for the rest. We observed feeding behaviour, seed handling techniques and ranging patterns of the macaques and monitored availability of wild fruits. Irrespective of fruit availability, frugivory and seed dispersal activities decreased when the macaques were provisioned. Provisioned macaques also had shortened daily ranges implying shorter dispersal distances. Finally, during provisioning periods, seeds were deposited on tarmac roads that were unconducive for germination. Provisioning promotes human-primate conflict, as commensal primates are often involved in aggressive encounters with humans over resources, leading to negative consequences for both parties involved. Preventing or curbing provisioning is not an easy task as feeding wild animals is a socio-cultural tradition across much of South and South-East Asia, including India. We recommend the initiation of literacy programmes that educate lay citizens about the ill-effects of provisioning and strongly caution them against the practice.

Efficient Low Complexity Power Allocation Policies for Wireless Communication Systems Guaranteeing QoS

We consider near-optimal policies for a single user transmitting on a wireless channel which minimize average queue length under average power constraint. The power is consumed in transmission of data only. We consider the case when the power used in transmission is a linear function of the data transmitted. The transmission channel may experience multipath fading. Later, we also extend these results to the multiuser case. We show that our policies can be used in a system with energy harvesting sources at the transmitter. Next we consider data users which require minimum rate guarantees. Finally we consider the system which has both data and real time users. Our policies have low computational complexity, closed form expression for mean delays and require only the mean arrival rate with no queue length information.

Kernelization complexity of possible winner and coalitional manipulation problems in voting

In the POSSIBLE WINNER problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNER problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge 10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNER problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the COALITIONAL MANIPULATION problem which is an important special case of the POSSIBLE WINNER problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNER problem is harder than the COALITIONAL MANIPULATION problem since the COALITIONAL MANIPULATION problem admits a polynomial kernel whereas the POSSIBLE WINNER problem does not admit a polynomial kernel. (C) 2015 Elsevier B.V. All rights reserved.