Статті в журналах з теми "Parameterized complexity algorithms"
Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Parameterized complexity algorithms.
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 статей у журналах для дослідження на тему "Parameterized complexity algorithms".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
Marx, D. "Parameterized Complexity and Approximation Algorithms." Computer Journal 51, no. 1 (March 6, 2007): 60–78. http://dx.doi.org/10.1093/comjnl/bxm048.
2
Dabrowski, Konrad K., Peter Jonsson, Sebastian Ordyniak, and George Osipov. "Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 4 (June 28, 2022): 3724–32. http://dx.doi.org/10.1609/aaai.v36i4.20286.
Анотація:
The simple temporal problem (STP) is one of the most influential reasoning formalisms for representing temporal information in AI. We study the problem of resolving inconsistency of data encoded in the STP. We prove that the problem of identifying a maximally large consistent subset of data is NP-hard. In practical instances, it is reasonable to assume that the amount of erroneous data is small. We therefore parameterize by the number of constraints that need to be removed to achieve consistency. Using tools from parameterized complexity we design fixed-parameter tractable algorithms for two large fragments of the STP. Our main algorithmic results employ reductions to the Directed Subset Feedback Arc Set problem and iterative compression combined with an efficient algorithm for the Edge Multicut problem. We complement our algorithmic results with hardness results that rule out fixed-parameter tractable algorithms for all remaining non-trivial fragments of the STP (under standard complexity-theoretic assumptions). Together, our results give a full classification of the classical and parameterized complexity of the problem.
3
Liu, Yunlong, Jianxin Wang, Jiong Guo, and Jianer Chen. "Complexity and parameterized algorithms for Cograph Editing." Theoretical Computer Science 461 (November 2012): 45–54. http://dx.doi.org/10.1016/j.tcs.2011.11.040.
4
Gasarch, W., and K. M. Kin. "Invitation to Fixed-Parameter Algorithms * Parameterized Complexity Theory * Parameterized Algorithmics: Theory, Practice and Prospects." Computer Journal 51, no. 1 (March 6, 2007): 137–40. http://dx.doi.org/10.1093/comjnl/bxm047.
5
Bulteau, Laurent, and Mathias Weller. "Parameterized Algorithms in Bioinformatics: An Overview." Algorithms 12, no. 12 (December 1, 2019): 256. http://dx.doi.org/10.3390/a12120256.
Анотація:
Bioinformatics regularly poses new challenges to algorithm engineers and theoretical computer scientists. This work surveys recent developments of parameterized algorithms and complexity for important NP-hard problems in bioinformatics. We cover sequence assembly and analysis, genome comparison and completion, and haplotyping and phylogenetics. Aside from reporting the state of the art, we give challenges and open problems for each topic.
6
Kellerhals, Leon, Tomohiro Koana, Pascal Kunz, and Rolf Niedermeier. "Parameterized Algorithms for Colored Clustering." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 4 (June 26, 2023): 4400–4408. http://dx.doi.org/10.1609/aaai.v37i4.25560.
Анотація:
In the Colored Clustering problem, one is asked to cluster edge-colored (hyper-)graphs whose colors represent interaction types. More specifically, the goal is to select as many edges as possible without choosing two edges that share an endpoint and are colored differently. Equivalently, the goal can also be described as assigning colors to the vertices in a way that fits the edge-coloring as well as possible. As this problem is NP-hard, we build on previous work by studying its parameterized complexity. We give a 2ᴼ⁽ᵏ⁾·nᴼ⁽¹⁾-time algorithm where k is the number of edges to be selected and n the number of vertices. We also prove the existence of a problem kernel of size O(k⁵ᐟ²), resolving an open problem posed in the literature. We consider parameters that are smaller than k, the number of edges to be selected, and r, the number of edges that can be deleted. Such smaller parameters are obtained by considering the difference between k or r and some lower bound on these values. We give both algorithms and lower bounds for Colored Clustering with such parameterizations. Finally, we settle the parameterized complexity of Colored Clustering with respect to structural graph parameters by showing that it is W[1]-hard with respect to both vertex cover number and tree-cut width, but fixed-parameter tractable with respect to local feedback edge number.
7
Blažej, Václav, Robert Ganian, Dušan Knop, Jan Pokorný, Šimon Schierreich, and Kirill Simonov. "The Parameterized Complexity of Network Microaggregation." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 5 (June 26, 2023): 6262–70. http://dx.doi.org/10.1609/aaai.v37i5.25771.
Анотація:
Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.
8
Fichte, Johannes K., Markus Hecher, and Arne Meier. "Counting Complexity for Reasoning in Abstract Argumentation." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 2827–34. http://dx.doi.org/10.1609/aaai.v33i01.33012827.
Анотація:
In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a given argumentation framework while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension.
9
Eiben, Eduard, Robert Ganian, Thekla Hamm, and Viktoriia Korchemna. "A Structural Complexity Analysis of Synchronous Dynamical Systems." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 5 (June 26, 2023): 6313–21. http://dx.doi.org/10.1609/aaai.v37i5.25777.
Анотація:
Synchronous dynamical systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption. We study the three most notable problems in synchronous dynamical systems: whether the system will transition to a target configuration from a starting configuration, whether the system will reach convergence from a starting configuration, and whether the system is guaranteed to converge from every possible starting configuration. While all three problems were known to be intractable in the classical sense, we initiate the study of their exact boundaries of tractability from the perspective of structural parameters of the network by making use of the more fine-grained parameterized complexity paradigm. As our first result, we consider treewidth - as the most prominent and ubiquitous structural parameter - and show that all three problems remain intractable even on instances of constant treewidth. We complement this negative finding with fixed-parameter algorithms for the former two problems parameterized by treedepth, a well-studied restriction of treewidth. While it is possible to rule out a similar algorithm for convergence guarantee under treedepth, we conclude with a fixed-parameter algorithm for this last problem when parameterized by treedepth and the maximum in-degree.
10
Feldmann, Andreas Emil, Karthik C. Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. "A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms." Algorithms 13, no. 6 (June 19, 2020): 146. http://dx.doi.org/10.3390/a13060146.
Анотація:
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.
11
Fichte, Johannes. "Backdoors to Tractability of Answer-Set Programming." Proceedings of the AAAI Conference on Artificial Intelligence 27, no. 1 (June 29, 2013): 1662–63. http://dx.doi.org/10.1609/aaai.v27i1.8505.
Анотація:
The practical results of answer-set programming indicate that classical complexity theory is insufficient as a theoretical framework to explain why modern answer-set programming solvers work fast on industrial applications. Complexity analysis by means of parameterized complexity theory seems to be promising, because we think that the reason for the gap between theory and practice is the presence of a "hidden structure" in real-world instances. The application of parameterized complexity theory to answer-set programming would give a crucial understanding of how solver heuristics work. This profound understanding can be used to improve the decision heuristics of modern solvers and yields new efficient algorithms for decision problems in the nonmonotonic setting. My research aims to explain the gap between theoretical upper bounds and the effort to solve real-world instances. I will further develop by means of parameterized complexity exact algorithms which work efficiently for real-world instances. The approach is based on backdoors which are small sets of atoms that represent "clever reasoning shortcuts" through the search space. The concept of backdoors is widely used in the areas of propositional satisfiability and constraint satisfaction. I will show how this concept can be adapted to the nonmonotonic setting and how it can be utilized to improve common algorithms.
12
Bannach, Max, and Till Tantau. "On the Descriptive Complexity of Color Coding." Algorithms 14, no. 3 (March 19, 2021): 96. http://dx.doi.org/10.3390/a14030096.
Анотація:
Color coding is an algorithmic technique used in parameterized complexity theory to detect “small” structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pattern. We transfer color coding to the world of descriptive complexity theory by characterizing—purely in terms of the syntactic structure of describing formulas—when the powerful second-order quantifiers representing a random coloring can be replaced by equivalent, simple first-order formulas. Building on this result, we identify syntactic properties of first-order quantifiers that can be eliminated from formulas describing parameterized problems. The result applies to many packing and embedding problems, but also to the long path problem. Together with a new result on the parameterized complexity of formula families involving only a fixed number of variables, we get that many problems lie in FPT just because of the way they are commonly described using logical formulas.
13
Lee, Chuan-Min. "Clique Transversal Variants on Graphs: A Parameterized-Complexity Perspective." Mathematics 11, no. 15 (July 28, 2023): 3325. http://dx.doi.org/10.3390/math11153325.
Анотація:
The clique transversal problem and its variants have garnered significant attention in the last two decades due to their practical applications in communication networks, social-network theory and transceiver placement for cellular telephones. While previous research primarily focused on determining the polynomial-time solvability or NP-hardness/NP-completeness of specific graphs, this paper adopts a parameterized-complexity approach. It thoroughly explores four clique transversal variants: the d-fold transversal problem, the {d}-clique transversal problem, the signed clique transversal problem and the minus clique transversal problem. The paper presents various findings regarding the parameterized complexity of the clique transversal problem and its variants. It establishes the W[2]-completeness and para-NP-completeness of the d-fold transversal problem, the {d}-clique transversal problem, the signed clique transversal problem and the minus clique transversal problem within specific graph classes. Additionally, it introduces fixed-parameter tractable algorithms for planar graphs and graphs with bounded treewidth, offering efficient solutions for these specific instances of the problems. The research further explores the relationship between planar graphs and graphs with bounded treewidth to enhance the time complexity of the d-fold clique transversal problem and the {d}-clique transversal problem. By analyzing the parameterized complexity of the clique transversal problem and its variants, this research contributes to our understanding of the computational limitations and potentially efficient algorithms for solving these problems.
14
XIE, MINZHU, JIAN'ER CHEN, and JIANXIN WANG. "RESEARCH ON PARAMETERIZED ALGORITHMS OF THE INDIVIDUAL HAPLOTYPING PROBLEM." Journal of Bioinformatics and Computational Biology 05, no. 03 (June 2007): 795–816. http://dx.doi.org/10.1142/s0219720007002710.
Анотація:
The individual haplotyping problem is a computing problem of reconstructing two haplotypes for an individual based on several optimal criteria from one's fragments sequencing data. This paper is based on the fact that the length of a fragment and the number of the fragments covering a SNP (single nucleotide polymorphism) site are both very small compared with the length of a sequenced region and the total number of the fragments and introduces the parameterized haplotyping problems. With m fragments whose maximum length is k1, n SNP sites and the number of the fragments covering a SNP site no more than k2, our algorithms can solve the gapless MSR (Minimum SNP Removal) and MFR (Minimum Fragment Removal) problems in the time complexity O(nk1k2 + m log m + nk2 + mk1) and [Formula: see text] respectively. Since, the value of k1 and k2 are both small (about 10) in practice, our algorithms are more efficient and applicable compared with the algorithms of V. Bafna et al. of time complexity O(mn2) and O(m2n + m3), respectively.
15
Chen, Jianer, and Iyad A. Kanj. "Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms." Journal of Computer and System Sciences 67, no. 4 (December 2003): 833–47. http://dx.doi.org/10.1016/j.jcss.2003.09.003.
16
Golovach, Petr A., and Dimitrios M. Thilikos. "Paths of bounded length and their cuts: Parameterized complexity and algorithms." Discrete Optimization 8, no. 1 (February 2011): 72–86. http://dx.doi.org/10.1016/j.disopt.2010.09.009.
17
Crespelle, Christophe, Pål Grønås Drange, Fedor V. Fomin, and Petr Golovach. "A survey of parameterized algorithms and the complexity of edge modification." Computer Science Review 48 (May 2023): 100556. http://dx.doi.org/10.1016/j.cosrev.2023.100556.
18
Tao, Liangde, Lin Chen, and Guochuan Zhang. "Scheduling Stochastic Jobs - Complexity and Approximation Algorithms." Proceedings of the International Conference on Automated Planning and Scheduling 31 (May 17, 2021): 367–75. http://dx.doi.org/10.1609/icaps.v31i1.15982.
Анотація:
Uncertainty is an omnipresent issue in real-world optimization problems. This paper studies a fundamental problem concerning uncertainty, known as the beta-robust scheduling problem. Given a set of identical machines and a set of jobs whose processing times follow a normal distribution, the goal is to assign jobs to machines such that the probability that all the jobs are completed by a given common due date is maximized. We give the first systematic study on the complexity and algorithms for this problem. A strong negative result is shown by ruling out the existence of any polynomial-time algorithm with a constant approximation ratio for the general problem unless P=NP. On the positive side, we provide the first FPT-AS (fixed parameter tractable approximation scheme) parameterized by the number of different kinds of jobs, which is a common parameter in scheduling problems. It returns a solution arbitrarily close to the optimal solution, provided that the job processing times follow a few different types of distributions. We further complement the theoretical results by implementing our algorithm. The experiments demonstrate that by choosing an appropriate approximation ratio, the algorithm can efficiently compute a near-optimal solution.
19
Sato, T., and Y. Kameya. "Parameter Learning of Logic Programs for Symbolic-Statistical Modeling." Journal of Artificial Intelligence Research 15 (December 1, 2001): 391–454. http://dx.doi.org/10.1613/jair.912.
Анотація:
We propose a logical/mathematical framework for statistical parameter learning of parameterized logic programs, i.e. definite clause programs containing probabilistic facts with a parameterized distribution. It extends the traditional least Herbrand model semantics in logic programming to distribution semantics, possible world semantics with a probability distribution which is unconditionally applicable to arbitrary logic programs including ones for HMMs, PCFGs and Bayesian networks. We also propose a new EM algorithm, the graphical EM algorithm, that runs for a class of parameterized logic programs representing sequential decision processes where each decision is exclusive and independent. It runs on a new data structure called support graphs describing the logical relationship between observations and their explanations, and learns parameters by computing inside and outside probability generalized for logic programs. The complexity analysis shows that when combined with OLDT search for all explanations for observations, the graphical EM algorithm, despite its generality, has the same time complexity as existing EM algorithms, i.e. the Baum-Welch algorithm for HMMs, the Inside-Outside algorithm for PCFGs, and the one for singly connected Bayesian networks that have been developed independently in each research field. Learning experiments with PCFGs using two corpora of moderate size indicate that the graphical EM algorithm can significantly outperform the Inside-Outside algorithm.
20
Wiersema, Roeland, Dylan Lewis, David Wierichs, Juan Carrasquilla, and Nathan Killoran. "Here comes the SU(N): multivariate quantum gates and gradients." Quantum 8 (March 7, 2024): 1275. http://dx.doi.org/10.22331/q-2024-03-07-1275.
Анотація:
Variational quantum algorithms use non-convex optimization methods to find the optimal parameters for a parametrized quantum circuit in order to solve a computational problem. The choice of the circuit ansatz, which consists of parameterized gates, is crucial to the success of these algorithms. Here, we propose a gate which fully parameterizes the special unitary group SU(N). This gate is generated by a sum of non-commuting operators, and we provide a method for calculating its gradient on quantum hardware. In addition, we provide a theorem for the computational complexity of calculating these gradients by using results from Lie algebra theory. In doing so, we further generalize previous parameter-shift methods. We show that the proposed gate and its optimization satisfy the quantum speed limit, resulting in geodesics on the unitary group. Finally, we give numerical evidence to support the feasibility of our approach and show the advantage of our gate over a standard gate decomposition scheme. In doing so, we show that not only the expressibility of an ansatz matters, but also how it's explicitly parameterized.
21
Lin, Mugang, Jianxin Wang, Qilong Feng, and Bin Fu. "Randomized Parameterized Algorithms for the Kidney Exchange Problem." Algorithms 12, no. 2 (February 25, 2019): 50. http://dx.doi.org/10.3390/a12020050.
Анотація:
In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant L (typically 2 ≤ L ≤ 5), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases L = 3 and L ≥ 3 , and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively.
22
Kanj, Iyad A., Luay Nakhleh, and Ge Xia. "The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms." Algorithmica 51, no. 2 (October 9, 2007): 99–128. http://dx.doi.org/10.1007/s00453-007-9046-1.
23
Eiben, Eduard, Fedor Fomin, Fahad Panolan, and Kirill Simonov. "Manipulating Districts to Win Elections: Fine-Grained Complexity." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 1902–9. http://dx.doi.org/10.1609/aaai.v34i02.5559.
Анотація:
Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. Lewenberg, Lev, and Rosenschein [AAMAS 2017] initiated the algorithmic study of a geographically-based manipulation problem, where voters must vote at the ballot box closest to them. In this variant of gerrymandering, for a given set of possible locations of ballot boxes and known political preferences of n voters, the task is to identify locations for k boxes out of m possible locations to guarantee victory of a certain party in at least ℓ districts. Here integers k and ℓ are some selected parameter.It is known that the problem is NP-complete already for 4 political parties and prior to our work only heuristic algorithms for this problem were developed. We initiate the rigorous study of the gerrymandering problem from the perspectives of parameterized and fine-grained complexity and provide asymptotically matching lower and upper bounds on its computational complexity. We prove that the problem is W[1]-hard parameterized by k + n and that it does not admit an f(n,k) · mo(√k) algorithm for any function f of k and n only, unless the Exponential Time Hypothesis (ETH) fails. Our lower bounds hold already for 2 parties. On the other hand, we give an algorithm that solves the problem for a constant number of parties in time (m+n)O(√k).
24
Green, Frederic. "The Book Review Column1." ACM SIGACT News 51, no. 4 (December 14, 2020): 4–5. http://dx.doi.org/10.1145/3444815.3444817.
Анотація:
The three books reviewed in this column are about central ideas in algorithms, complexity, and geometry. The third one brings together topics from the first two by applying techniques of both property testing (the subject of the first book) and parameterized complexity (including its more focused incarnation studied in the second book, kernelization) to geometric problems.
25
Roayaei, Mehdy, and MohammadReza Razzazi. "Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs." International Journal of Foundations of Computer Science 29, no. 07 (November 2018): 1215–30. http://dx.doi.org/10.1142/s0129054118500302.
Анотація:
We consider the directed Steiner network problem, where given a weighted directed graph [Formula: see text] and [Formula: see text] pairs of vertices [Formula: see text], one has to find the minimum weight subgraph [Formula: see text] of [Formula: see text] that contains path from [Formula: see text] to [Formula: see text] for all [Formula: see text]. We search for the main cause of the complexity of the problem and introduce the notions of junction vertex and shared segment in an optimal solution. We study the parameterized complexity of the problem with respect to these parameters and achieve several parameterized hardness results. Also, we present two output-sensitive algorithms for the problem, which are much simpler and easier to implement than the previously best known one; and in addition, when the paths corresponding to the input pairs have few shared vertices or arcs in the optimal solution, these algorithms outperform the previous one.
26
Bredereck, Robert, Piotr Faliszewski, Andrzej Kaczmarczyk, Dušan Knop, and Rolf Niedermeier. "Parameterized Algorithms for Finding a Collective Set of Items." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 1838–45. http://dx.doi.org/10.1609/aaai.v34i02.5551.
Анотація:
We extend the work of Skowron et al. (AIJ, 2016) by considering the parameterized complexity of the following problem. We are given a set of items and a set of agents, where each agent assigns an integer utility value to each item. The goal is to find a set of k items that these agents would collectively use. For each such collective set of items, each agent provides a score that can be described using an OWA (ordered weighted average) operator and we seek a set with the highest total score. We focus on the parameterization by the number of agents and we find numerous fixed-parameter tractability results (however, we also find some W[1]-hardness results). It turns out that most of our algorithms even apply to the setting where each agent has an integer weight.
27
Eiben, Eduard, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak. "Parameterized Complexity of Envy-Free Resource Allocation in Social Networks." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 05 (April 3, 2020): 7135–42. http://dx.doi.org/10.1609/aaai.v34i05.6201.
Анотація:
We consider the classical problem of allocating resources among agents in an envy-free (and, where applicable, proportional) way. Recently, the basic model was enriched by introducing the concept of a social network which allows to capture situations where agents might not have full information about the allocation of all resources. We initiate the study of the parameterized complexity of these resource allocation problems by considering natural parameters which capture structural properties of the network and similarities between agents and items. In particular, we show that even very general fragments of the considered problems become tractable as long as the social network has bounded treewidth or bounded clique-width. We complement our results with matching lower bounds which show that our algorithms cannot be substantially improved.
28
Boudjellal, Nawel, Hayet Roumili, and Djamel Benterki. "Complexity analysis of interior point methods for convex quadratic programming based on a parameterized Kernel function." Boletim da Sociedade Paranaense de Matemática 40 (February 2, 2022): 1–16. http://dx.doi.org/10.5269/bspm.47772.
Анотація:
The kernel functions play an important role in the amelioration of the computational complexity of algorithms. In this paper, we present a primal-dual interior-point algorithm for solving convex quadratic programming based on a new parametric kernel function. The proposed kernel function is not logarithmic and not self-regular. We analysis a large and small-update versions which are based on a new kernel function. We obtain the best known iteration bound for large-update methods, which improves signicantly the so far obtained complexity results. Thisresult is the rst to reach this goal.
29
Bruchertseifer, Jens, and Henning Fernau. "Synchronizing series-parallel deterministic finite automata with loops and related problems." RAIRO - Theoretical Informatics and Applications 55 (2021): 7. http://dx.doi.org/10.1051/ita/2021005.
Анотація:
We study the problem DFA-SW of determining if a given deterministic finite automaton A possesses a synchronizing word of length at most k for automata whose (multi-)graphs are TTSPL, i.e., series-parallel, plus allowing some self-loops. While DFA-SW remains NP-complete on TTSPL automata, we also find (further) restrictions with efficient (parameterized) algorithms. We also study the (parameterized) complexity of related problems, for instance, extension variants of the synchronizing word problem, or the problem of finding smallest alphabet-induced synchronizable sub-automata.
30
Misra, Neeldhara, Frances Rosamond, and Meirav Zehavi. "Special Issue “New Frontiers in Parameterized Complexity and Algorithms”: Foreward by the Guest Editors." Algorithms 13, no. 9 (September 18, 2020): 236. http://dx.doi.org/10.3390/a13090236.
Анотація:
This Special Issue contains eleven articles—surveys and research papers—that represent fresh and ambitious new directions in the area of Parameterized Complexity. They provide ground-breaking research at the frontiers of knowledge, and they contribute to bridging the gap between theory and practice. The scope and impact of the field continues to increase. Promising avenues and new research challenges are highlighted in this Special Issue.
31
Chitnis, Rajesh, Andreas Emil Feldmann, and Pasin Manurangsi. "Parameterized Approximation Algorithms for Bidirected Steiner Network Problems." ACM Transactions on Algorithms 17, no. 2 (June 2021): 1–68. http://dx.doi.org/10.1145/3447584.
Анотація:
The D irected S teiner N etwork (DSN) problem takes as input a directed graph G =( V , E ) with non-negative edge-weights and a set D ⊆ V × V of k demand pairs. The aim is to compute the cheapest network N⊆ G for which there is an s\rightarrow t path for each ( s , t )∈ D. It is known that this problem is notoriously hard, as there is no k 1/4− o (1) -approximation algorithm under Gap-ETH, even when parametrizing the runtime by k [Dinur & Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the parameter k . For the bi -DSNP lanar problem, the aim is to compute a solution N⊆ G whose cost is at most that of an optimum planar solution in a bidirected graph G , i.e., for every edge uv of G the reverse edge vu exists and has the same weight. This problem is a generalization of several well-studied special cases. Our main result is that this problem admits a parameterized approximation scheme (PAS) for k . We also prove that our result is tight in the sense that (a) the runtime of our PAS cannot be significantly improved, and (b) no PAS exists for any generalization of bi-DSNP lanar , under standard complexity assumptions. The techniques we use also imply a polynomial-sized approximate kernelization scheme (PSAKS). Additionally, we study several generalizations of bi -DSNP lanar and obtain upper and lower bounds on obtainable runtimes parameterized by k . One important special case of DSN is the S trongly C onnected S teiner S ubgraph (SCSS) problem, for which the solution network N⊆ G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2-approximation exists for parameter k [Chitnis et al., IPEC 2013]. We give a tight inapproximability result by showing that for k no parameterized (2 − ε)-approximation algorithm exists under Gap-ETH. Additionally, we show that when restricting the input of SCSS to bidirected graphs, the problem remains NP-hard but becomes FPT for k .
32
Kowaluk, Mirosław, and Andrzej Lingas. "A Multi-Dimensional Matrix Product—A Natural Tool for Parameterized Graph Algorithms." Algorithms 15, no. 12 (November 28, 2022): 448. http://dx.doi.org/10.3390/a15120448.
Анотація:
We introduce the concept of a k-dimensional matrix product D of k matrices A1,…,Ak of sizes n1×n,…,nk×n, respectively, where D[i1,…,ik] is equal to ∑ℓ=1nA1[i1,ℓ]×…×Ak[ik,ℓ]. We provide upper bounds on the time complexity of computing the product and solving related problems of computing witnesses and maximum witnesses of the Boolean version of the product in terms of the time complexity of rectangular matrix multiplication. The multi-dimensional matrix product framework is useful in the design of parameterized graph algorithms. First, we apply our results on the multi-dimensional matrix product to the fundamental problem of detecting/counting copies of a fixed pattern graph in a host graph. The recent progress on this problem has not included complete pattern graphs, i.e., cliques (and their complements, i.e., edge-free pattern graphs, in the induced setting). The fastest algorithms for the aforementioned patterns are based on a reduction to triangle detection/counting. We provide an alternative simple method of detection/counting copies of fixed size cliques based on the multi-dimensional matrix product. It is at least as time efficient as the triangle method in cases of K4 and K5. Next, we show an immediate reduction of the k-dominating set problem to the multi-dimensional matrix product. It implies the W[2] hardness of the problem of computing the k-dimensional Boolean matrix product. Finally, we provide an efficient reduction of the problem of finding the lowest common ancestors for all k-tuples of vertices in a directed acyclic graph to the problem of finding witnesses of the Boolean variant of the multi-dimensional matrix product. Although the time complexities of the algorithms resulting from the aforementioned reductions solely match those of the known algorithms, the advantage of our algorithms is simplicity. Our algorithms also demonstrate the versatility of the multi-dimensional matrix product framework.
33
Eiben, Eduard, Robert Ganian, Dusan Knop, and Sebastian Ordyniak. "Solving Integer Quadratic Programming via Explicit and Structural Restrictions." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 1477–84. http://dx.doi.org/10.1609/aaai.v33i01.33011477.
Анотація:
We study the parameterized complexity of Integer Quadratic Programming under two kinds of restrictions: explicit restrictions on the domain or coefficients, and structural restrictions on variable interactions. We argue that both kinds of restrictions are necessary to achieve tractability for Integer Quadratic Programming, and obtain four new algorithms for the problem that are tuned to possible explicit restrictions of instances that we may wish to solve. The presented algorithms are exact, deterministic, and complemented by appropriate lower bounds.
34
STEWART, IAIN A. "ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES." Parallel Processing Letters 22, no. 01 (March 2012): 1250003. http://dx.doi.org/10.1142/s012962641250003x.
Анотація:
We equate a routing algorithm in a (faulty) interconnection network whose underlying graph is a k-ary n-cube or a hypercube, that attempts to route a packet from a fixed source node to a fixed destination node, with the sub-digraph of (healthy) links potentially usable by this routing algorithm as it attempts to route the packet. This gives rise to a naturally defined problem, parameterized by this routing algorithm, relating to whether a packet can be routed from a given source node to a given destination node in one of our interconnection networks in which there are (possibly exponentially many) faulty links. We show that there exist such problems that are PSPACE-complete (all are solvable in PSPACE) but that there are (existing and popular) routing algorithms for which the computational complexity of the corresponding problem is significantly easier (yet still computationally intractable).
35
Gaspers, Serge, Mikko Koivisto, Mathieu Liedloff, Sebastian Ordyniak, and Stefan Szeider. "On Finding Optimal Polytrees." Proceedings of the AAAI Conference on Artificial Intelligence 26, no. 1 (September 20, 2021): 750–56. http://dx.doi.org/10.1609/aaai.v26i1.8217.
Анотація:
Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, finding an optimal network is NP-hard, even if restricted to polytrees of bounded in-degree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. Here, we study the complexity of finding an optimal polytree that can be turned into a branching by deleting some number of arcs or nodes, treated as a parameter. We show that the problem can be solved via a matroid intersection formulation in polynomial time if the number of deleted arcs is bounded by a constant. The order of the polynomial time bound depends on this constant, hence the algorithm does not establish fixed-parameter tractability when parameterized by the number of deleted arcs. We show that a restricted version of the problem allows fixed-parameter tractability and hence scales well with the parameter. We contrast this positive result by showing that if we parameterize by the number of deleted nodes, a somewhat more powerful parameter, the problem is not fixed-parameter tractable, subject to a complexity-theoretic assumption.
36
Elkabbany, Ghada Farouk, Hassan Ibrahim Ahmed, Heba K. Aslan, Young-Im Cho, and Mohamed S. Abdallah. "Lightweight Computational Complexity Stepping up the NTRU Post-Quantum Algorithm Using Parallel Computing." Symmetry 16, no. 1 (December 21, 2023): 12. http://dx.doi.org/10.3390/sym16010012.
Анотація:
The Nth-degree Truncated polynomial Ring Unit (NTRU) is one of the famous post-quantum cryptographic algorithms. Researchers consider NTRU to be the most important parameterized family of lattice-based public key cryptosystems that has been established to the IEEE P1363 standards. Lattice-based protocols necessitate operations on large vectors, which makes parallel computing one of the appropriate solutions to speed it up. NTRUEncrypt operations contain a large amount of data that requires many repetitive arithmetic operations. These operations make it a strong candidate to take advantage of the high degree of parallelism. The main costly operation that is repeated in all NTRU algorithm steps is polynomial multiplication. In this work, a Parallel Post-Quantum NTRUEncrypt algorithm called PPQNTRUEncrypt is proposed. This algorithm exploits the capabilities of parallel computing to accelerate the NTRUEncrypt algorithm. Both analytical and Apache Spark simulation models are used. The proposed algorithm enhanced the NTRUEncrypt algorithm by approximately 49.5%, 74.5%, 87.6%, 92.5%, 93.4%, and 94.5%, assuming that the number of processing elements is 2, 4, 8, 12, 16, and 20 respectively.
37
Abu-Khzam, Faisal N., and Karam Al Kontar. "A Brief Survey of Fixed-Parameter Parallelism." Algorithms 13, no. 8 (August 14, 2020): 197. http://dx.doi.org/10.3390/a13080197.
Анотація:
This paper provides an overview of the field of parameterized parallel complexity by surveying previous work in addition to presenting a few new observations and exploring potential new directions. In particular, we present a general view of how known FPT techniques, such as bounded search trees, color coding, kernelization, and iterative compression, can be modified to produce fixed-parameter parallel algorithms.
38
Faran, Rachel, and Orna Kupferman. "A Parametrized Analysis of Algorithms on Hierarchical Graphs." International Journal of Foundations of Computer Science 30, no. 06n07 (September 2019): 979–1003. http://dx.doi.org/10.1142/s0129054119400252.
Анотація:
Hierarchical graphs are used in order to describe systems with a sequential composition of sub-systems. A hierarchical graph consists of a vector of subgraphs. Vertices in a subgraph may “call” other subgraphs. The reuse of subgraphs, possibly in a nested way, causes hierarchical graphs to be exponentially more succinct than equivalent flat graphs. Early research on hierarchical graphs and the computational price of their succinctness suggests that there is no strong correlation between the complexity of problems when applied to flat graphs and their complexity in the hierarchical setting. That is, the complexity in the hierarchical setting is higher, but all “jumps” in complexity up to an exponential one are exhibited, including no jumps in some problems. We continue the study of the complexity of algorithms for hierarchical graphs, with the following contributions: (1) In many applications, the subgraphs have a small, often a constant, number of exit vertices, namely vertices from which control returns to the calling subgraph. We offer a parameterized analysis of the complexity and point to problems where the complexity becomes lower when the number of exit vertices is bounded by a constant. (2) We describe a general methodology for algorithms on hierarchical graphs. The methodology is based on an iterative compression of subgraphs in a way that maintains the solution to the problems and results in subgraphs whose size depends only on the number of exit vertices, and (3) we handle labeled hierarchical graphs, where edges are labeled by letters from some alphabet, and the problems refer to the languages of the graphs.
39
Cohen, Liron, Adham Jabarin, Andrei Popescu, and Reuben N. S. Rowe. "The Complex(ity) Landscape of Checking Infinite Descent." Proceedings of the ACM on Programming Languages 8, POPL (January 5, 2024): 1352–84. http://dx.doi.org/10.1145/3632888.
Анотація:
Cyclic proof systems, in which induction is managed implicitly, are a promising approach to automatic verification. The soundness of cyclic proof graphs is ensured by checking them against a trace-based Infinite Descent property. Although the problem of checking Infinite Descent is known to be PSPACE-complete, this leaves much room for variation in practice. Indeed, a number of different approaches are employed across the various cyclic proof systems described in the literature. In this paper, we study criteria for Infinite Descent in an abstract, logic-independent setting. We look at criteria based on Büchi automata encodings and relational abstractions, and determine their parameterized time complexities in terms of natural dimensions of cyclic proofs: the numbers of vertices of the proof-tree graphs, and the vertex width—an upper bound on the number of components (e.g., formulas) of a sequent that can be simultaneously tracked for descent. We identify novel algorithms that improve upon the parameterised complexity of the existing algorithms. We implement the studied criteria and compare their performance on various benchmarks.
40
Jonsson, Peter, Victor Lagerkvist, and Biman Roy. "Fine-Grained Time Complexity of Constraint Satisfaction Problems." ACM Transactions on Computation Theory 13, no. 1 (March 2021): 1–32. http://dx.doi.org/10.1145/3434387.
Анотація:
We study the constraint satisfaction problem (CSP) parameterized by a constraint language Γ (CSPΓ) and how the choice of Γ affects its worst-case time complexity. Under the exponential-time hypothesis (ETH), we rule out the existence of subexponential algorithms for finite-domain NP-complete CSPΓ problems. This extends to certain infinite-domain CSPs and structurally restricted problems. For CSPs with finite domain D and where all unary relations are available, we identify a relation S D such that the time complexity of the NP-complete problem CSP({ S D }) is a lower bound for all NP-complete CSPs of this kind. We also prove that the time complexity of CSP({ S D }) strictly decreases when |D| increases (unless the ETH is false) and provide stronger complexity results in the special case when |D|=3.
41
Pourhassan, Mojgan, Feng Shi, and Frank Neumann. "Parameterized Analysis of Multiobjective Evolutionary Algorithms and the Weighted Vertex Cover Problem." Evolutionary Computation 27, no. 4 (December 2019): 559–75. http://dx.doi.org/10.1162/evco_a_00255.
Анотація:
Evolutionary multiobjective optimization for the classical vertex cover problem has been analysed in Kratsch and Neumann ( 2013 ) in the context of parameterized complexity analysis. This article extends the analysis to the weighted vertex cover problem in which integer weights are assigned to the vertices and the goal is to find a vertex cover of minimum weight. Using an alternative mutation operator introduced in Kratsch and Neumann ( 2013 ), we provide a fixed parameter evolutionary algorithm with respect to [Formula: see text], the cost of an optimal solution for the problem. Moreover, we present a multiobjective evolutionary algorithm with standard mutation operator that keeps the population size in a polynomial order by means of a proper diversity mechanism, and therefore, manages to find a 2-approximation in expected polynomial time. We also introduce a population-based evolutionary algorithm which finds a [Formula: see text]-approximation in expected time [Formula: see text].
42
Fomin, Fedor V., Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. "Multiplicative Parameterization Above a Guarantee." ACM Transactions on Computation Theory 13, no. 3 (September 30, 2021): 1–16. http://dx.doi.org/10.1145/3460956.
Анотація:
Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given an instance ( I,k ) of some (parameterized) problem π with a guarantee g(I) , decide whether I admits a solution of size at least (or at most) k + g(I) . Here, g(I) is usually a lower bound on the minimum size of a solution. Since its introduction in 1999 for M AX SAT and M AX C UT (with g(I) being half the number of clauses and half the number of edges, respectively, in the input), analysis of parameterization above a guarantee has become a very active and fruitful topic of research. We highlight a multiplicative form of parameterization above (or, rather, times) a guarantee: Given an instance ( I,k ) of some (parameterized) problem π with a guarantee g(I) , decide whether I admits a solution of size at least (or at most) k · g(I) . In particular, we study the Long Cycle problem with a multiplicative parameterization above the girth g(I) of the input graph, which is the most natural guarantee for this problem, and provide a fixed-parameter algorithm. Apart from being of independent interest, this exemplifies how parameterization above a multiplicative guarantee can arise naturally. We also show that, for any fixed constant ε > 0, multiplicative parameterization above g(I) 1+ε of Long Cycle yields para-NP-hardness, thus our parameterization is tight in this sense. We complement our main result with the design (or refutation of the existence) of fixed-parameter algorithms as well as kernelization algorithms for additional problems parameterized multiplicatively above girth.
43
Gaspers, Serge, and Kamran Najeebullah. "Optimal Surveillance of Covert Networks by Minimizing Inverse Geodesic Length." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 533–40. http://dx.doi.org/10.1609/aaai.v33i01.3301533.
Анотація:
The inverse geodesic length (IGL) is a well-known and widely used measure of network performance. It equals the sum of the inverse distances of all pairs of vertices. In network analysis, IGL of a network is often used to assess and evaluate how well heuristics perform in strengthening or weakening a network. We consider the edge-deletion problem MINIGLED. Formally, given a graph G, a budget k, and a target inverse geodesic length T, the question is whether there exists a subset of edges X with |X| ≤ ck, such that the inverse geodesic length of G − X is at most T.In this paper, we design algorithms and study the complexity of MINIGL-ED. We show that it is NP-complete and cannot be solved in subexponential time even when restricted to bipartite or split graphs assuming the Exponential Time Hypothesis. In terms of parameterized complexity, we consider the problem with respect to various parameters. We show that MINIGL-ED is fixed-parameter tractable for parameter T and vertex cover by modeling the problem as an integer quadratic program. We also provide FPT algorithms parameterized by twin cover and neighborhood diversity combined with the deletion budget k. On the negative side we show that MINIGL-ED is W[1]-hard for parameter tree-width.
44
Cygan, Marek, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. Van Rooij, and Jakub Onufry Wojtaszczyk. "Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time." ACM Transactions on Algorithms 18, no. 2 (April 30, 2022): 1–31. http://dx.doi.org/10.1145/3506707.
Анотація:
For the vast majority of local problems on graphs of small treewidth (where, by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c tw | V | O(1) time algorithms, where tw is the treewidth of the input graph G = ( V,E ) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best–known algorithms were naive dynamic programming schemes running in at least tw tw time. We bridge this gap by introducing a technique we named Cut&Count that allows to produce c tw | V | O(1) time Monte-Carlo algorithms for most connectivity-type problems, including Hamiltonian Path , Steiner Tree , Feedback Vertex Set and Connected Dominating Set . These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H -minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In all these fields we are able to improve the best-known results for some problems. Also, looking from a more theoretical perspective, our results are surprising since the equivalence relation that partitions all partial solutions with respect to extendability to global solutions seems to consist of at least tw tw equivalence classes for all these problems. Our results answer an open problem raised by Lokshtanov, Marx and Saurabh [SODA’11]. In contrast to the problems aimed at minimizing the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be bridged for some problems that aim to maximize the number of connected components like Cycle Packing .
45
Chini, Peter, Roland Meyer, and Prakash Saivasan. "Fine-Grained Complexity of Safety Verification." Journal of Automated Reasoning 64, no. 7 (July 14, 2020): 1419–44. http://dx.doi.org/10.1007/s10817-020-09572-x.
Анотація:
Abstract We study the fine-grained complexity of Leader Contributor Reachability ($${\textsf {LCR}} $$ LCR ) and Bounded-Stage Reachability ($${\textsf {BSR}} $$ BSR ), two variants of the safety verification problem for shared memory concurrent programs. For both problems, the memory is a single variable over a finite data domain. Our contributions are new verification algorithms and lower bounds. The latter are based on the Exponential Time Hypothesis ($${\textsf {ETH}} $$ ETH ), the problem $${\textsf {Set~Cover}} $$ Set Cover , and cross-compositions. $${\textsf {LCR}} $$ LCR is the question whether a designated leader thread can reach an unsafe state when interacting with a certain number of equal contributor threads. We suggest two parameterizations: (1) By the size of the data domain $${\texttt {D}}$$ D and the size of the leader $${\texttt {L}}$$ L , and (2) by the size of the contributors $${\texttt {C}}$$ C . We present algorithms for both cases. The key techniques are compact witnesses and dynamic programming. The algorithms run in $${\mathcal {O}}^*(({\texttt {L}}\cdot ({\texttt {D}}+1))^{{\texttt {L}}\cdot {\texttt {D}}} \cdot {\texttt {D}}^{{\texttt {D}}})$$ O ∗ ( ( L · ( D + 1 ) ) L · D · D D ) and $${\mathcal {O}}^*(2^{{\texttt {C}}})$$ O ∗ ( 2 C ) time, showing that both parameterizations are fixed-parameter tractable. We complement the upper bounds by (matching) lower bounds based on $${\textsf {ETH}} $$ ETH and $${\textsf {Set~Cover}} $$ Set Cover . Moreover, we prove the absence of polynomial kernels. For $${\textsf {BSR}} $$ BSR , we consider programs involving $${\texttt {t}}$$ t different threads. We restrict the analysis to computations where the write permission changes $${\texttt {s}}$$ s times between the threads. $${\textsf {BSR}} $$ BSR asks whether a given configuration is reachable via such an $${\texttt {s}}$$ s -stage computation. When parameterized by $${\texttt {P}}$$ P , the maximum size of a thread, and $${\texttt {t}}$$ t , the interesting observation is that the problem has a large number of difficult instances. Formally, we show that there is no polynomial kernel, no compression algorithm that reduces the size of the data domain $${\texttt {D}}$$ D or the number of stages $${\texttt {s}}$$ s to a polynomial dependence on $${\texttt {P}}$$ P and $${\texttt {t}}$$ t . This indicates that symbolic methods may be harder to find for this problem.
46
Bredereck, Robert, Piotr Faliszewski, Rolf Niedermeier, and Nimrod Talmon. "Large-Scale Election Campaigns: Combinatorial Shift Bribery." Journal of Artificial Intelligence Research 55 (March 16, 2016): 603–52. http://dx.doi.org/10.1613/jair.4927.
Анотація:
We study the complexity of a combinatorial variant of the Shift Bribery problem in elections. In the standard Shift Bribery problem, we are given an election where each voter has a preference order over the set of candidates and where an outside agent, the briber, can pay each voter to rank the briber's favorite candidate a given number of positions higher. The goal is to ensure the victory of the briber's preferred candidate. The combinatorial variant of the problem, introduced in this paper, models settings where it is possible to affect the position of the preferred candidate in multiple votes, either positively or negatively, with a single bribery action. This variant of the problem is particularly interesting in the context of large-scale campaign management problems (which, from the technical side, are modeled as bribery problems). We show that, in general, the combinatorial variant of the problem is highly intractable; specifically, NP-hard, hard in the parameterized sense, and hard to approximate. Nevertheless, we provide parameterized algorithms and approximation algorithms for natural restricted cases.
47
Philip, Aby, Soorya Rethinasamy, Vincent Russo, and Mark M. Wilde. "Schrödinger as a Quantum Programmer: Estimating Entanglement via Steering." Quantum 8 (June 11, 2024): 1366. http://dx.doi.org/10.22331/q-2024-06-11-1366.
Анотація:
Quantifying entanglement is an important task by which the resourcefulness of a quantum state can be measured. Here, we develop a quantum algorithm that tests for and quantifies the separability of a general bipartite state by using the quantum steering effect, the latter initially discovered by Schrödinger. Our separability test consists of a distributed quantum computation involving two parties: a computationally limited client, who prepares a purification of the state of interest, and a computationally unbounded server, who tries to steer the reduced systems to a probabilistic ensemble of pure product states. To design a practical algorithm, we replace the role of the server with a combination of parameterized unitary circuits and classical optimization techniques to perform the necessary computation. The result is a variational quantum steering algorithm (VQSA), a modified separability test that is implementable on quantum computers that are available today. We then simulate our VQSA on noisy quantum simulators and find favorable convergence properties on the examples tested. We also develop semidefinite programs, executable on classical computers, that benchmark the results obtained from our VQSA. Thus, our findings provide a meaningful connection between steering, entanglement, quantum algorithms, and quantum computational complexity theory. They also demonstrate the value of a parameterized mid-circuit measurement in a VQSA.
48
Şeker, Oylum, Pinar Heggernes, Tinaz Ekim, and Z. Caner Taşkın. "Generation of random chordal graphs using subtrees of a tree." RAIRO - Operations Research 56, no. 2 (March 2022): 565–82. http://dx.doi.org/10.1051/ro/2022027.
Анотація:
Chordal graphs form one of the most studied graph classes. Several graph problems that are NP-hard in general become solvable in polynomial time on chordal graphs, whereas many others remain NP-hard. For a large group of problems among the latter, approximation algorithms, parameterized algorithms, and algorithms with moderately exponential or sub-exponential running time have been designed. Chordal graphs have also gained increasing interest during the recent years in the area of enumeration algorithms. Being able to test these algorithms on instances of chordal graphs is crucial for understanding the concepts of tractability of hard problems on graph classes. Unfortunately, only few published papers give algorithms for generating chordal graphs. Even in these papers, only very few methods aim for generating a large variety of chordal graphs. Surprisingly, none of these methods is directly based on the “intersection of subtrees of a tree” characterization of chordal graphs. In this paper, we give an algorithm for generating chordal graphs, based on the characterization that a graph is chordal if and only if it is the intersection graph of subtrees of a tree. Upon generating a random host tree, we give and test various methods that generate subtrees of the host tree. We compare our methods to one another and to existing ones for generating chordal graphs. Our experiments show that one of our methods is able to generate the largest variety of chordal graphs in terms of maximal clique sizes. Moreover, two of our subtree generation methods result in an overall complexity of our generation algorithm that is the best possible time complexity for a method generating the entire node set of subtrees in an “intersection of subtrees of a tree” representation. The instances corresponding to the results presented in this paper, and also a set of relatively small-sized instances are made available online.
49
Baste, Julien, Lars Jaffke, Tomáš Masařík, Geevarghese Philip, and Günter Rote. "FPT Algorithms for Diverse Collections of Hitting Sets." Algorithms 12, no. 12 (November 27, 2019): 254. http://dx.doi.org/10.3390/a12120254.
Анотація:
In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in k + r for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of ‘base’ solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest.
50
De Oliveira Oliveira, Mateus, and Farhad Vadiee. "From Width-Based Model Checking to Width-Based Automated Theorem Proving." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 5 (June 26, 2023): 6297–304. http://dx.doi.org/10.1609/aaai.v37i5.25775.
Анотація:
In the field of parameterized complexity theory, the study of graph width measures has been intimately connected with the development of width-based model checking algorithms for combinatorial properties on graphs. In this work, we introduce a general framework to convert a large class of width-based model-checking algorithms into algorithms that can be used to test the validity of graph-theoretic conjectures on classes of graphs of bounded width. Our framework is modular and can be applied with respect to several well-studied width measures for graphs, including treewidth and cliquewidth. As a quantitative application of our framework, we prove analytically that for several long-standing graph-theoretic conjectures, there exists an algorithm that takes a number k as input and correctly determines in time double-exponential in a polynomial of k whether the conjecture is valid on all graphs of treewidth at most k. These upper bounds, which may be regarded as upper-bounds on the size of proofs/disproofs for these conjectures on the class of graphs of treewidth at most k, improve significantly on theoretical upper bounds obtained using previously available techniques.