Search

Multiwinner elections have proven to be a fruitful research topic with many real-world applications. We contribute to this line of research by improving the state of the art regarding the computational complexity of computing good committees. More formally, given a set of candidates C , a set of voters V —each ranking the candidates according to their preferences, and an integer k; a multiwinner voting rule identifies a k-sized committee, based on these given voter preferences. In this paper we consider several utilitarian and egailitarian ordered weighted average scoring rules, which are an extensively-researched family of rules (and a subfamily of the family of committee scoring rules). First, we improve the result of Betzler et al. (JAIR 47:475–519, 2013), which gave a O (n n) algorithm for computing winner under the Chamberlin–Courant rule, where n is the number of voters; to a running time of O (2 n) , which is optimal. Furthermore, we study the parameterized complexity of the Pessimist voting rule and describe a few tractable and intractable cases. Apart from such utilitarian voting rules, we extend our study and consider egalitarian median and egalitarian mean (both committee scoring rules), showing some tractable and intractable results, based on nontrivial structural observations. [ABSTRACT FROM AUTHOR]

We study a set of voting problems where given an election E = (C , Π V) (where C is the set of candidates and Π V is a set of votes), and a non-empty subset of candidates J , the question under consideration is: Can we modify the election in a way so that none of the candidates in J wins the election? The modification operations allowed are that of either adding or deleting some candidates. Yang and Wang (2017) [44] introduced these problems as the Resolute Control problem , a generalization of the destructive control problem where J is a singleton. They studied parameterized complexity of Resolute Control for voting rules Borda (both addition and deletion), Maximin (addition), and Copeland (both addition and deletion). They primarily consider | J | as parameter. In this paper we study Resolute Control parameterized by the other natural parameters viz., the number of candidates added or deleted. We show that the Resolute Control for Borda (both addition and deletion), Maximin (addition) and Copeland (deletion) are W[2]-hard. We complement this by showing that when the number of voters is odd, Copeland (deletion) is FPT parameterized by the sum of the number of deleted candidates and the size of the feedback arc set of the majority graph of the election. [ABSTRACT FROM AUTHOR]

Balanced Stable Marriage (BSM) is a central optimization version of the classic Stable Marriage (SM) problem. We study BSM from the viewpoint of Parameterized Complexity. Informally, the input of BSM consists of n men, n women, and an integer k. Each person a has a (sub)set of acceptable partners, A (a) , whom a ranks strictly; we use p a (b) to denote the position of b ∈ A (a) in a 's preference list. The objective is to decide whether there exists a stable matching μ such that balance (μ) ≜ max ⁡ { ∑ (m , w) ∈ μ p m (w) , ∑ (m , w) ∈ μ p w (m) } ≤ k. In SM , all stable matchings match the same set of agents, A ⋆ which can be computed in polynomial time. As balance (μ) ≥ | A ⋆ | 2 for any stable matching μ , BSM is trivially fixed-parameter tractable (FPT) with respect to k. Thus, a natural question is whether BSM is FPT with respect to k − | A ⋆ | 2. With this viewpoint in mind, we draw a line between tractability and intractability in relation to the target value. This line separates additional natural parameterizations higher/lower than ours (e.g., we automatically resolve the parameterization k − | A ⋆ | 2). The two extreme stable matchings are the man-optimal μ M and the woman-optimal μ W. Let O M = ∑ (m , w) ∈ μ M p m (w) , and O W = ∑ (m , w) ∈ μ W p w (m). In this work, we prove that • BSM parameterized by t = k − min ⁡ { O M , O W } admits (1) a kernel where the number of people is linear in t , and (2) a parameterized algorithm whose running time is single exponential in t. • BSM parameterized by t = k − max ⁡ { O M , O W } is W[1]-hard. [ABSTRACT FROM AUTHOR]

Intra-species genetic variability assessment is an effective tool in formulating genetic improvement and germplasm conservation strategies. Houttuynia cordata Thunb. is a semidomesticated medicinal herb consumed widely in traditional diet in North-Eastern India. In the present study, an effort has been made to assess the genetic diversity of H. cordata Thunb. from Brahmaputra valley of North-East India. A total of 545 genotypes from 18 populations of H. cordata Thunb. from four different regions, i.e. North-East, North-West, South-East and South-West, with respect to river Brahmaputra were collected and population genetic diversity and structure were analysed using ISSR molecular markers. Population genetic structure analysis using unweighted pair group method with averages (UPGMA)-based hierarchical cluster analysis, principal coordinate analysis (PCoA) and model-based clustering in STRUCTURE program revealed that the population of H. cordata Thunb. grouped according to regional distribution and forms four genetically distinct clusters. The analysis of molecular variance showed that differentiation among regions was significant with 60% genetic variation among region, 3% genetic variation among population within region and 37% genetic variation within population. We found wide variation in Nei's gene diversity (Hj) ranging from 0.07782 in Margherita population to 0.13634 in Barapani population. Furthermore, Nei's gene diversity within population (Nei's Hs) and total gene diversity (Ht) were found to be 0.1081 and 0.1769 respectively. The genetic differentiation among 18 population was high (Fst = 0.3894; p < 0.001) with relatively restricted gene flow (Nm = 0.6564). Based on the result of this study, we suggest ex situ conservation could be an appropriate measure to adequately capture the total genetic diversity of H. cordata Thunb. populations of North-East India by selecting few individuals from different populations. [ABSTRACT FROM AUTHOR]

A graph is called a split graph if its vertex set can be partitioned into a clique and an independent set. Split graphs have rich mathematical structure and interesting algorithmic properties making it one of the most well-studied special graph classes. In the Split Vertex Deletion problem, given a graph and a positive integer k , the objective is to test whether there exists a subset of at most k vertices whose deletion results in a split graph. In this paper, we design a kernel for this problem with O (k 2) vertices, improving upon the previous cubic bound known. Also, by giving a simple reduction from the Vertex Cover problem, we establish that Split Vertex Deletion does not admit a kernel with O (k 2 − ϵ) edges, for any ϵ > 0 , unless NP ⊆ coNP/poly. [ABSTRACT FROM AUTHOR]

In this paper, we study the NP-complete colorful variant of the classic matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, the goal is to decide whether there exists a matching of size at least k such that the edges in the matching have distinct colors. Previously, in [MFCS'17], we studied this problem from the view point of Parameterized Complexity and gave efficient FPT algorithms as well as a quadratic kernel on paths. In this paper we design a quadratic vertex kernel for Rainbow Matching on general graphs; generalizing the earlier quadratic kernel on paths to general graphs. For our kernelization algorithm we combine a graph decomposition method with an application of expansion lemma. [ABSTRACT FROM AUTHOR]

In this paper, we study the NP-complete colorful variant of the classical Matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, this problem asks whether there exists a matching of size at least k such that all the edges in the matching have distinct colors. We first develop a deterministic algorithm that solves Rainbow Matching on paths in time O ⋆ 1 + 5 2 k and polynomial space. This algorithm is based on a curious combination of the method of bounded search trees and a "divide-and-conquer-like" approach, where the branching process is guided by the maintenance of an auxiliary bipartite graph where one side captures "divided-and-conquered" pieces of the path. Our second result is a randomized algorithm that solves Rainbow Matching on general graphs in time O ⋆ (2 k) and polynomial-space. Here, we show how a result by Björklund et al. (J Comput Syst Sci 87:119–139, 2017) can be invoked as a black box, wrapped by a probability-based analysis tailored to our problem. We also complement our two main results by designing kernels for Rainbow Matching on general and bounded-degree graphs. [ABSTRACT FROM AUTHOR]

In this paper we consider a problem that arises from a strategic issue in the stable matching model (with complete preference lists) from the viewpoint of exact-exponential time algorithms. Specifically, we study the STABLE EXTENSION OF PARTIAL MATCHING (SEOPM) problem, where the input consists of the complete preference lists of men, and a partial matching. The objective is to find (if one exists) a set of preference lists of women, such that the men-optimal Gale-Shapley algorithm outputs a perfect matching that contains the given partial matching. Kobayashi and Matsui (Algorithmica 58:151-169, 2010) proved this problem is NP-complete. In this article, we give an exact-exponential algorithm for SEOPM running in time 2O(n), where n denotes the number of men/women. We complement our algorithmic finding by showing that unless Exponential Time Hypothesis (ETH) fails, our algorithm is asymptotically optimal. That is, unless ETH fails, there is no algorithm for SEOPM running in time 2o(n). Our algorithm is a non-trivial combination of a parameterized algorithm for SUBGRAPH ISOMORPHISM, a relationship between stable matching and finding an out-branching in an appropriate graph and enumerating all possible non-isomorphic out-branchings. Our results cover both the cases when the preference lists are strict and complete, and when they are strict but possibly incomplete. [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of NP-hard optimization versions of Stable Matching and Stable Roommates in the presence of ties and incomplete lists. These problems model many real-life situations where solutions have to satisfy certain predefined criterion of suitability and compatibility. Specifically, our objective is to maximize/minimize the size of the stable matching. Our main theorems state that Stable Matching and Stable Roommates admit small kernels. Consequently, we also conclude that Stable Matching is fixed-parameter tractable ( FPT ) with respect to solution size, and that Stable Roommates is FPT with respect to a structural parameter. Finally, we analyze the special case where the input graph is planar. [ABSTRACT FROM AUTHOR]

We consider the k-S erver problem under the advice model of computation when the underlying metric space is sparse. On one side, we introduce Θ(1)-competitive algorithms for a wide range of sparse graphs. These algorithms require advice of (almost) linear size. We show that for graphs of size N and treewidth α, there is an online algorithm that receives O ( n(log α + log log N)) bits of advice and optimally serves any sequence of length n. We also prove that if a graph admits a system of μ collective tree ( q, r)-spanners, then there is a ( q + r)-competitive algorithm which requires O ( n(log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, when provided with O ( n log log N) bits of advice. On the other side, we prove that advice of size Ω( n) is required to obtain a 1-competitive algorithm for sequences of length n even for the 2-server problem on a path metric of size N ≥ 3. Through another lower bound argument, we show that at least $\frac {n}{2}(\log \alpha - 1.22)$ bits of advice is required to obtain an optimal solution for metric spaces of treewidth α, where 4 ≤ α < 2 k. [ABSTRACT FROM AUTHOR]

Access graphs, which have been used previously in connection to competitive analysis and relative worst order analysis to model locality of reference in paging, are considered in connection with relative interval analysis. The algorithms LRU, FIFO, FWF, and FAR are compared using the path, star, and cycle access graphs. In this model, some of the results obtained are not surprising. However, although LRU is found to be strictly better than FIFO on paths, it has worse performance on stars, cycles, and complete graphs, in this model. We solve an open question from Dorrigiv et al. (2009) [13] , obtaining tight bounds on the relationship between LRU and FIFO with relative interval analysis. [ABSTRACT FROM AUTHOR]

We show that for a fixed r, the number of maximal r-regular induced subgraphs in any graph with n vertices is upper bounded by O(cn), where c is a positive constant strictly less than 2. This bound generalizes the well-known result of Moon and Moser, who showed an upper bound of 3n/3 on the number of maximal independent sets of a graph on n vertices. We complement this upper bound result by obtaining an almost tight lower bound on the number of (possible) maximal r-regular induced subgraphs possible in a graph on n vertices. Our upper bound results are algorithmic. That is, we can enumerate all the maximal r-regular induced subgraphs in time (cnnO(1)). A related question is that of finding a maximum-sized r-regular induced subgraph. Given a graph G =(V,E) on n vertices, the Maximum r-Regular Induced Subgraph (M-r-RIS) problem asks for a maximum-sized subset of vertices, R ⊆ V, such that the induced subgraph on R is r-regular. As a by-product of the enumeration algorithm, we get a O (cn) time algorithm for this problem for any fixed constant r, where c is a positive constant strictly less than 2. Furthermore, we use the techniques and results obtained in the paper to obtain improved exact algorithms for a special case of the Induced Subgraph Isomorphism problem, namely, the Induced r-Regular Subgraph Isomorphism problem, where r is a constant, the δ-Separating Maximum Matching problem and the Efficient Edge Dominating Set problem. [ABSTRACT FROM AUTHOR]

Understanding the genes that govern tea plant ( Camellia sinensis) architecture and response to drought stress is urgently needed to enhance breeding in tea with improved water use efficiency. Field drought is a slow mechanism and the plants go through an adaptive process in contrast to the drastic changes of rapid dehydration in case of controlled experiments. We identified a set of drought responsive genes under controlled condition using SSH, and validated the identified genes and their pattern of expression under field drought condition. The study was at three stages of water deficit stress viz., before wilting, wilting and recovery, which revealed a set of genes with higher expression at before wilting stage including dehydrin, abscissic acid ripening protein, glutathione peroxidase, cinnamoyl CoA reductase, calmodulin binding protein. The higher expression of these genes was related with increase tolerance character of DT/TS-463 before wilting, these five tolerant progenies could withstand drought stress and thus are candidates for breeding. We observed that physiological parameter like water use efficiency formed a close group with genes such as calmodulin related, DRM3, hexose transporter, hydrogen peroxide induced protein, ACC oxidase, lipase, ethylene responsive transcription factor and diaminopimelate decarboxylase, during wilting point. Our data provides valuable information for the gene components and the dynamics of gene expression in second and third leaf against drought stress in tea, which could be regarded as candidate targets potentially associated with drought tolerance. We propose that the identified five tolerant progenies on the basis of their drought tolerance can thus be utilised for future breeding programmes. [ABSTRACT FROM AUTHOR]

Tea (Camellia sinensis [L.] O. Kuntze) plant, one of the most important plantation crops in the world, is infected by a fungus called Exobasidium vexans leading to dreaded blister blight disease. The disease may result in crop losses up to 35% which directly affect the tea industry. Solanum tuberosum endo-1,3-beta-D-glucanase was cloned into tea genome via Agrobacteriummediated transformation. The transformation event initially gave 32 kanamycin-resistant plantlets, out of which PCR analysis confirmed only 10 plantlets about the integration of transgene in the plant genome. Real-time PCR study detected transgene expression in six transgenic plantlets. Upregulation of endogenous C. sinensis pathogenesis-related (PR) genes like PR3 (chitinase I) gene and PR5 (thaumatin-like protein) gene also occurred in transgenic plantlets. Detached leaf infection assay showed resistance to E. vexans in greenhouse-acclimated transgenic plantlets. An inhibitory activity against E. vexans was noticed on the detached leaves of transgenic plantlets compared to control. Transgenic plantlets showed resistance to inoculated fungal pathogen by the formation of hypersensitivity reaction area unlike the formation of fungal lesion on control plantlet. Thus, it can be inferred that constitutive expression of the potato endo-1,3-beta-D-glucanase gene can be a strategy to produce blister blight-resistant tea. [ABSTRACT FROM AUTHOR]

Tea is the second most consumed beverage worldwide whose cultivation is greatly challenged by a large variety of biotic and abiotic stresses. Among the biotic factors, the hemipteran pest Helopeltis theivora Waterhouse is particularly devastating in Asia and Africa, rendering the crop unsuitable for any downstream processing. The present study, for the first time, endeavors to dissect the molecular events associated with such infestations and identify potential molecular protagonists influencing Helopeltis tolerance in Assam tea. We analyzed the transcriptome of infested tea plants having contrasting responses to pest feeding by suppression subtractive hybridization and quantified the relative abundances of defense-associated transcripts. We analyzed 445 unigenes derived from 1558 expressed sequence tags (ESTs) from three different infestation conditions. Our study indicate that defense responses to the pest greatly vary in temporal and cultivar-specific manner characterized by an exclusive upregulation of specific defense-associated genes in the tolerant cultivar. Moreover, it was observed that transcripts related to flavonoid biosynthesis, purine metabolism, formate metabolism, jasmonic acid biosynthesis and signaling, and cell wall metabolism are uniquely enriched in the same. Interestingly, those involved in caffeine biosynthesis remain comparatively low and unaltered. We report higher trichome densities on the abaxial surface of the leaf in tolerant cultivar while puncture causes their tender reorientation. SEM of the insect mouthparts reveal higher concentrations of sensilla-like structures near the distal end and tip of the proboscis which are known to act as chemoreceptors in other hemipterans. Our investigation provides the first ever glimpse of Helopeltis-induced defense gene network and provides the much needed platform for improvement of the crop for better Helopeltis tolerance through breeding and transgenic approaches. On a wider perspective, the study will augment our understanding of molecular responses to phloem herbivory in plants. [ABSTRACT FROM AUTHOR]

Pathogenesis related protein1 gene induced after pathogen infection in plants have been frequently used as marker gene for systemic acquired resistance. We have carried out isolation, annotation and expression of CsPR1, a potential disease resistance gene. The full length cDNA consist of 671 bp in length containing 162 amino acids with a signal peptide of 22 amino acids and 17.92 kDa predicted molecular weight. Recombinant CsPR1 was successfully expressed in BL21(DE3)pLysS cells using pET 43.1 EK LIC vector system and was purified. Three dimensional models were generated using Phyre2 and I-TASSER and built a compact structure consisting beta sheets surrounded by alpha helixes. The models were validated by MolProbity and RAMPAGE servers. Validation of modelled structures based on Ramachandran plot, revealed I-TASSER produce better quality and reliable 3D model. Purified recombinant CsPR1 and in silico generated 3D models from this study provide foundation for comprehensive functional and structural characterization of CsPR1 protein. [ABSTRACT FROM AUTHOR]