We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid , a weight function , and integers . The task is to decide if there is a collection of of such that the weight of the symmetric difference of any pair of these bases is at least . The input to the Weighted Diverse Common Independent Sets problem consists of two matroids defined on the same ground set , a weight function , and integers . The task is to decide if there is a collection of of and such that the weight of the symmetric difference of any pair of these sets is at least . The input to the Diverse Perfect Matchings problem consists of a graph and integers . The task is to decide if contains such that the symmetric difference of any two of these matchings is at least . We show that none of these problems can be solved in polynomial time unless . We derive fixed-parameter tractable () algorithms for all three problems with as the parameter, and present a -sized kernel for Weighted Diverse Bases.
Download full-text PDF |
Source |
|---|---|
| http://www.ncbi.nlm.nih.gov/pmc/articles/PMC10869459 | PMC |
| http://dx.doi.org/10.1007/s10107-023-01959-z | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
A robust multimodal brain MRI-based diagnostic model for migraine: validation across different migraine phases and longitudinal follow-up data.
J Headache Pain
January 2025
Department of Brain and Cognitive Engineering, Korea University, Seoul, Republic of Korea.
Inter-individual variability in symptoms and the dynamic nature of brain pathophysiology present significant challenges in constructing a robust diagnostic model for migraine. In this study, we aimed to integrate different types of magnetic resonance imaging (MRI), providing structural and functional information, and develop a robust machine learning model that classifies migraine patients from healthy controls by testing multiple combinations of hyperparameters to ensure stability across different migraine phases and longitudinally repeated data. Specifically, we constructed a diagnostic model to classify patients with episodic migraine from healthy controls, and validated its performance across ictal and interictal phases, as well as in a longitudinal setting.
View Article and Find Full Text PDFSpatial variability of cultural landscape vulnerability and influential factors in ethnic villages of Southeast Guizhou.
Sci Rep
January 2025
Southeast Guizhou Miao & Dong Autonomous Prefecture Housing and Urban - Rural Development Bureau, Southeast Guizhou Miao, 556000, Dong Autonomous Prefecture, China.
In Southeast Guizhou, a region of China rich in ethnic diversity, the cultural landscapes of ethnic villages are increasingly vulnerable under the pressures of urbanization and tourism development. This study assesses the vulnerability of 43 ethnic villages in Leishan County using the Vulnerability Scoring Diagram (VSD) model, which evaluates exposure, sensitivity, and coping ability. Analyses using spatial autocorrelation and geographic weighted regression reveal distinct spatial patterns of vulnerability, with the northern region exhibiting higher vulnerability indices than the southern region.
View Article and Find Full Text PDFOlanzapine exposure disordered lipid metabolism, gut microbiota and behavior in zebrafish (Danio rerio).
Comp Biochem Physiol C Toxicol Pharmacol
January 2025
College of Fisheries, Henan Normal University, Xinxiang 453007, PR China; Engineering Technology Research Center of Henan Province for Aquatic Animal Cultivation, Henan Normal University, Xinxiang 453007, PR China. Electronic address:
Olanzapine (OLZ) is widely used in the treatment of schizophrenia, and its metabolic side effects have garnered significant attention in recent years. Despite this, the specific side effects of OLZ and the underlying mechanisms remain inadequately understood. To address this gap, zebrafish (Danio rerio) were exposed to OLZ at concentrations of 35.
View Article and Find Full Text PDFOverfeeding and overweight rapidly reprogram inflammatory signaling.
Clin Immunol
January 2025
Division of Immunology, Boston Children's Hospital, Boston, MA, United States of America. Electronic address:
Epidemiologic studies have shown a continuous increase in mortality risk associated with overweight, thus highlighting the health risks beginning before the onset of obesity. However, early changes in inflammatory signaling induced by an obesogenic diet remain largely unknown since studies of obesity typically utilize models induced by months of continuous exposure to a high-fat diet. Here, we investigated how short-term overfeeding remodels inflammatory signaling.
View Article and Find Full Text PDFRNAi-mediated knockdown of HcCAT2 depresses the adaptive capacity of Hyphantria cunea larvae to cytisine and coumarin.
Int J Biol Macromol
January 2025
School of Forestry, Northeast Forestry University, Harbin 150040, PR China; Key Laboratory of Sustainable Forest Ecosystem Management-Ministry of Education, Northeast Forestry University, Harbin 150040, PR China. Electronic address:
The diversity of host plants is an important reason for the global spread of Hyphantria cunea. However, no studies have explored the role of the antioxidant defense system with catalase (CAT) as the core at the molecular level in the adaptation of the H. cunea to host plant secondary metabolites.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!