检索结果-内蒙古大学图书馆

Resolving Infeasibility of Linear Systems: A Parameterized Approach

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bérczi, Kristóf Göke, Alexander Mendoza-Cadena, Lydia Mirabel Mnich, Matthias MTA-ELTE Momentum Matroid Optimization Research Group MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany MTA-ELTE Momentum Matroid Optimization Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary

Deciding feasibility of large systems of linear equations and inequalities is one of the most fundamental algorithmic tasks. However, due to data inaccuracies or modeling errors, in practical applications one often faces linear systems that are infeasible. Extensive theoretical and practical methods have been proposed for post-infeasibility analysis of linear systems. This generally amounts to detecting a feasibility blocker of small size k, which is a set of equations and inequalities whose removal or perturbation from the large system of size m yields a feasible system. This motivates a parameterized approach towards post-infeasibility analysis, where we aim to find a feasibility blocker of size at most k in fixed-parameter time f(k) · mO(1). We establish parameterized intractability (W[1]- and NP-hardness) results already in very restricted settings for different choices of the parameters maximum size of a deletion set, number of positive/negative right-hand sides, treewidth, pathwidth and treedepth. Additionally, we rule out a polynomial compression for MinFB parameterized by the size of a deletion set and the number of negative right-hand sides. Furthermore, we develop fixed-parameter algorithms parameterized by various combinations of these parameters when every row of the system corresponds to a difference constraint. Our algorithms capture the case of Directed Feedback Arc Set, a fundamental parameterized problem whose fixed-parameter tractability was shown by Chen et al. (STOC 2008). Copyright © 2022, The Authors. All rights reserved.

关键词： Linear systems

Single-Peaked Opinion Updates

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bredereck, Robert George, Anne-Marie Israel, Jonas Kellerhals, Leon Algorithm Engineering Humboldt-Universität Berlin Germany Institut für Informatik TU Clausthal Germany Analytical Solutions and Reasoning University of Oslo Germany Research Group Efficient Algorithms Technische Universität Berlin Germany Algorithmics and Computational Complexity Technische Universität Berlin Germany

We consider opinion diffusion for undirected networks with sequential updates when the opinions of the agents are single-peaked preference rankings. Our starting point is the study of preserving single-peakedness. We identify voting rules that, when given a single-peaked profile, output at least one ranking that is single peaked w.r.t. a single-peaked axis of the input. For such voting rules we show convergence to a stable state of the diffusion process that uses the voting rule as the agents’ update rule. Further, we establish an efficient algorithm that maximises the spread of extreme opinions. Copyright © 2022, The Authors. All rights reserved.

关键词： Machine learning

Teleportation of quantum coherence

学校读者我要写书评

暂无评论

Physical Review A 2023年第4期108卷 042620-042620页

作者： Sohail Arun K. Pati Vijeth Aradhya Indranil Chakrabarty Subhasree Patro Quantum Information and Computation Group Harish-Chandra Research Institute A CI of Homi Bhabha National Institute Chhatnag Road Jhunsi Prayagraj 211019 India Centre for Quantum Science and Technology International Institute of Information Technology Hyderabad Gachibowli Hyderabad-500032 Telangana India Center for Security Theory and Algorithmic Research International Institute of Information Technology Hyderabad Gachibowli Hyderabad-500032 Telangana India Department of Computer Science National University of Singapore 117417 Singapore Computer science and physics department Utrecht University 3584 CS Utrecht The Netherlands Algorithms and complexity group QuSoft Centrum Wiskunde and Informatica 1098XG Amsterdam The Netherlands

We investigate whether it is possible to teleport the coherence of an unknown quantum state from Alice to Bob by communicating a smaller number of classical bits in comparison to what is required for teleporting an unknown quantum state. We find that we cannot achieve perfect teleportation of coherence with one bit of classical communication for an arbitrary qubit. However, we find that if the qubit is partially known, i.e., chosen from the equatorial and polar circles of the Bloch sphere, then teleportation of coherence is possible with the transfer of one cbit of information when we have maximally entangled states as a shared resource. In the case of the resource being a nonmaximally entangled state, we can teleport the coherence with a certain probability of success. In a general teleportation protocol for coherence, we derive a compact formula for the final state at Bob's laboratory in terms of the composition of the completely positive maps corresponding to the shared resource state and a joint positive operator-valued measure (POVM) performed by Alice on her qubit and the unknown state. Using this formula, we show that teleportation of the coherence of a partially known state with real matrix elements is perfectly possible with the help of a maximally entangled state as a resource. Furthermore, we explore the teleportation of coherence with Werner states and show that even when Werner states become separable, the amount of teleported coherence is nonzero, implying the possibility of teleportation of coherence without entanglement.

关键词： Quantum coherence & coherence measures Quantum communication Quantum correlations in quantum information Quantum information theory Quantum protocols

The most general structure of graphs with hamiltonian or hamiltonian connected square

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Ekstein, Jan Fleischner, Herbert Department of Mathematics European Centre of Excellence Ntis - New Technologies for the Information Society Faculty of Applied Sciences University of West Bohemia Pilsen Technická 8 Plzeň306 14 Czech Republic Institute of Logic and Computation Algorithms and Complexity Group Technical University of Vienna Favoritenstrasse 9 - 11 Wien1040 Austria

On the basis of recent results on hamiltonicity, [4], and hamiltonian connectedness, [8], in the square of a 2-block, we determine the most general block-cutvertex structure a graph G may have in order to guarantee that G2 is hamiltonian, hamiltonian connected, respectively. Such an approach was already developed in [9] for hamiltonian total *** Codes 05C38, 05C45 © 2022, CC BY.

关键词： Hamiltonians

A study of 4−cycle systems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bagheri, B.Gh. Khosravi, M. Mahmoodian, E.S. Rashidi, S. Algorithms and Complexity Group Vienna University of Technology Favoritenstrasse 9-11 Vienna1040 Austria Department of Pure Mathematics Faculty of Mathematics and Computer Shahid Bahonar University of Kerman Kerman Iran Department of Mathematical Sciences Sharif University of Technology P.O. Box 11155-9415 Tehran Iran Department of Applied Mathematics Faculty of Mathematics and Computer Shahid Bahonar University of Kerman Kerman Iran

A 4−cycle system is a partition of the edges of the complete graph Kn into 4−cycles. Let C be a collection of cycles of length 4 whose edges partition the edges of Kn. A set of 4-cycles T1 ⊂ C is called a 4-cycle trade if there exists a set T2 of edge-disjoint 4-cycles on the same vertices, such that (C \ T1) ∪ T2 also is a collection of cycles of length 4 whose edges partition the edges of Kn. We study 4−cycle trades of volume two (double-diamonds) and three and show that the set of all 4-CS(9) is connected with respect of trading with trades of volume 2 (double-diamond) and 3. In addition, we present a full rank matrix whose null-space is containing *** Codes 05B30, 05B05 © 2023, CC BY-NC-ND.

关键词： Diamonds

Interplay of periodic dynamics and noise: Insights from a simple adaptive system

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Folz, Frederic Mehlhorn, Kurt Morigi, Giovanna Theoretische Physik Universität des Saarlandes Saarbrücken66123 Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarland Informatics Campus Saarbrücken66123 Germany

We study the dynamics of a simple adaptive system in the presence of noise and periodic damping. The system is composed by two paths connecting a source and a sink, the dynamics is governed by equations that usually describe food search of the paradigmatic Physarum polycephalum. In this work we assume that the two paths undergo damping whose relative strength is periodically modulated in time and analyse the dynamics in the presence of stochastic forces simulating Gaussian noise. We identify different responses depending on the modulation frequency and on the noise amplitude. At frequencies smaller than the mean dissipation rate, the system tends to switch to the path which minimizes dissipation. Synchronous switching occurs at an optimal noise amplitude which depends on the modulation frequency. This behaviour disappears at larger frequencies, where the dynamics can be described by the time-averaged equations. Here, we find metastable patterns that exhibit the features of noise-induced resonances. © 2021, CC BY-NC-SA.

关键词： Dynamics

The Evolution and Implications of the Inosine tRNA Modification

学校读者我要写书评

暂无评论

Journal of Molecular Biology 2025年第16期437卷 169187页

作者： van der Gulik, Peter T.S. Hoff, Wouter D. Algorithms and Complexity Group Centrum Wiskunde & Informatica P.O. Box 94079 Amsterdam 1090 GB Netherlands Department of Microbiology and Molecular Genetics Oklahoma State University Stillwater 74078 OK United States

Ever since the legendary publication by Francis Crick in JMB introducing the wobble hypothesis in 1966, inosine has been a permanent part of molecular biology. This review aims to integrate the rich array of novel insights emerging from subsequent research on the adenine-to-inosine modification of tRNA, with an emphasis on the results obtained during the last 5 years. Both the grand panorama of 4 billion years of evolution of life and the medical implications of defects in inosine modification will be reviewed. The most salient insights are that: (1) inosine at position 34 (the first position in the anticodon) is not universally present in the tree of life;(2) in many bacteria just a single homodimeric enzyme (TadA) is responsible for both tRNA inosine modification and mRNA inosine modification;(3) rapid progress is currently being made both in the molecular understanding of the heterodimeric ADAT2/ADAT3 enzyme responsible for inosine modifications in eukaryotes and in experimental capabilities for monitoring both the cytoplasmic tRNA pool and their modifications;(4) for selected tRNAs, inosine modification at position 37 has been demonstrated but this modification remains under-studied;(5) modification of tRNAs known to contain inosine can be incomplete;(6) the GC content of the T-stem is of great importance for wobble behavior, including wobbling behavior of inosine;and (7) the tRNA inosine modification is of direct relevance to human disease. In summary, research on inosine continues to yield important novel insights. © 2025 The Authors

关键词： Eukaryogenesis Inosine Modopathies Nanopore Wobble

complexity of Maker-Breaker Games on Edge Sets of Graphs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Duchêne, Eric Gledel, Valentin Inerney, Fionn Mc Nisse, Nicolas Oijid, Nacim Parreau, Aline Stojaković, Miloš Univ Lyon CNRS INSA Lyon UCBL Centrale Lyon Univ Lyon 2 LIRIS UMR5205 VilleurbanneF-69622 France Université Savoie Mont Blanc CNRS LAMA ChambéryF-73000 France Algorithms and Complexity Group TU Wien Austria Université Côte d’Azur Inria CNRS I3S France Department of Mathematics and Informatics Faculty of Sciences University of Novi Sad Novi Sad Serbia

We study the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the H-game. Maker wins if she claims the edges of a perfect matching in the first, and a copy of a fixed graph H in the second. We prove that deciding who wins the perfect matching game and the H-game is PSPACE-complete, even for the latter in small-diameter graphs if H is a tree. Toward finding the smallest graph H for which the H-game is PSPACE-complete, we also prove that such an H of order 51 and size 57 exists. We then give several positive results for the H-game. As the H-game is already PSPACE-complete when H is a tree, we mainly consider the case where H belongs to a subclass of trees. In particular, we design two linear-time algorithms, both based on structural characterizations, to decide the winners of the P4-game in general graphs and the K1,-game in trees. Then, we prove that the K1,-game in any graph, and the H-game in trees are both FPT parameterized by the length of the game, notably adding to the short list of games with this property, which is of independent interest. Another natural direction to take is to consider the H-game when H is a cycle. While we were unable to resolve this case, we prove that the related arboricity-k game is polynomial-time solvable. In particular, when k = 2, Maker wins this game if she claims the edges of any *** Codes 91A24, 91A43, 91A46 © 2023, CC BY.

关键词： Trees (mathematics)

Crossing-optimal extension of simple drawings

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Ganian, Robert Hamm, Thekla Klute, Fabian Parada, Irene Vogtenhuber, Birgit Algorithms and Complexity Group TU Wien Austria Utrecht University Netherlands TU Eindhoven Netherlands Graz University of Technology Austria

In extension problems of partial graph drawings one is given an incomplete drawing of an input graph G and is asked to complete the drawing while maintaining certain properties. A prominent area where such problems arise is that of crossing minimization. For plane drawings and various relaxations of these, there is a number of tractability as well as lower-bound results exploring the computational complexity of crossing-sensitive drawing extension problems. In contrast, comparatively few results are known on extension problems for the fundamental and broad class of simple drawings, that is, drawings in which each pair of edges intersects in at most one point. In fact, only recently it has been shown that the extension problem of simple drawings is NP-hard even when the task is to insert a single edge. In this paper we present tractability results for the crossing-sensitive extension problem of simple drawings. In particular, we show that the problem of inserting edges into a simple drawing is fixed-parameter tractable when parameterized by the number of edges to insert and an upper bound on newly created crossings. Using the same proof techniques, we are also able to answer several closely related variants of this problem, among others the extension problem for k-plane drawings. Moreover, using a different approach, we provide a single-exponential fixed-parameter algorithm for the case in which we are only trying to insert a single edge into the drawing. © 2020, CC BY.

关键词： Graph theory