Marthe Bonamy, Oscar Defrain, Marc Heinrich, Jean-Florent Raymond, Michał Pilipczuk
2018-10-01
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for
-free graphs and variants. This answers a question of Kant'e et al. about enumeration in bipartite graphs.
Haitao Wang
2019-03-04
Let
be a polygonal domain of holes and vertices. We study the problem of constructing a data structure that can compute a shortest path between and in under the metric for any two query points and . To do so, a standard approach is to first find a set of "gateways" for and a set of "gateways" for such that there exist a shortest - path containing a gateway of and a gateway of , and then compute a shortest - path using these gateways. Previous algorithms all take quadratic time to solve this problem. In this paper, we propose a divide-and-conquer technique that solves the problem in time. As a consequence, we construct a data structure of size in time such that each query can be answered in time.
Gaurav Menghani, Dhruv Matani
2019-03-04
A Level Ancestory query LA(
, ) asks for the the ancestor of the node at a depth . We present a simple solution, which pre-processes the tree in time with extra space, and answers the queries in time. Though other optimal algorithms exist, this is a simple enough solution that could be taught and implemented easily.
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi
2019-03-04
Bidimensionality is the most common technique to design subexponential-time parameterized algorithms on special classes of graphs, particularly planar graphs. The core engine behind it is a combinatorial lemma of Robertson, Seymour and Thomas that states that every planar graph either has a
-grid as a minor, or its treewidth is . However, bidimensionality theory cannot be extended directly to several well-known classes of geometric graphs. Nevertheless, a relaxation of this lemma has been proven useful for unit disk graphs. Inspired by this, we prove a new decomposition lemma for map graphs. Informally, our lemma states the following. For any map graph , there exists a collection of cliques of with the following property: either contains a -grid as a minor, or it admits a tree decomposition where every bag is the union of of the cliques in the above collection. The new lemma appears to be a handy tool in the design of subexponential parameterized algorithms on map graphs. We demonstrate its usability by designing algorithms on map graphs with running time for the Connected Planar -Deletion problem (that encompasses problems such as Feedback Vertex Set and Vertex Cover). Obtaining subexponential algorithms for Longest Cycle/Path and Cycle Packing is more challenging. We have to construct tree decompositions with more powerful properties and to prove sublinear bounds on the number of ways an optimum solution could "cross" bags in these decompositions. For Longest Cycle/Path, these are the first subexponential-time parameterized algorithms on map graphs. For Feedback Vertex Set and Cycle Packing, we improve upon known -time algorithms on map graphs.
P. A. M. Casares, M. A. Martin-Delgado
2019-02-18
We introduce a new quantum optimization algorithm for Linear Programming (LP) problems based on Interior Point (IP) Predictor-Corrector (PC) methods whose (worst case) time complexity is
. This represents a quantum speed-up in the number of variables in the cost function with respect to the comparable classical Interior Point (IP) algorithms that behave as or depending on the technique employed, where is the number of constraints and the rest of the variables are defined in the introduction. The average time complexity of our algorithm is , which equals the behaviour on of quantum Semidefinite Programming (SDP) algorithms based on multiplicative weight methods when restricted to LP problems and heavily improves on the precision of the algorithm. Unlike the quantum SDP algorithm, the quantum PC algorithm does not depend on size parameters of the primal and dual LP problems ( ), and outputs a feasible and optimal solution whenever it exists.
Palash Dey
2019-01-25
Studying complexity of various bribery problems has been one of the main research focus in computational social choice. In all the models of bribery studied so far, the briber has to pay every voter some amount of money depending on what the briber wants the voter to report and the briber has some budget at her disposal. Although these models successfully capture many real world applications, in many other scenarios, the voters may be unwilling to deviate too much from their true preferences. In this paper, we study the computational complexity of the problem of finding a preference profile which is as close to the true preference profile as possible and still achieves the briber's goal subject to budget constraints. We call this problem Optimal Bribery. We consider three important measures of distances, namely, swap distance, footrule distance, and maximum displacement distance, and resolve the complexity of the optimal bribery problem for many common voting rules. We show that the problem is polynomial time solvable for the plurality and veto voting rules for all the three measures of distance. On the other hand, we prove that the problem is NP-complete for a class of scoring rules which includes the Borda voting rule, maximin, Copeland
for any , and Bucklin voting rules for all the three measures of distance even when the distance allowed per voter is for the swap and maximum displacement distances and for the footrule distance even without the budget constraints (which corresponds to having an infinite budget). For the -approval voting rule for any constant and the simplified Bucklin voting rule, we show that the problem is NP-complete for the swap distance even when the distance allowed is and for the footrule distance even when the distance allowed is even without the budget constraints.
Yanchen Deng, Ziyu Chen, Dingding Chen, Xingqiong Jiang, Qiang Li
2019-02-16
Asymmetric Distributed Constraint Optimization Problems (ADCOPs) have emerged as an important formalism in multi-agent community due to their ability to capture personal preferences. However, the existing search-based complete algorithms for ADCOPs can only use local knowledge to compute lower bounds, which leads to inefficient pruning and prohibits them from solving large scale problems. On the other hand, inference-based complete algorithms (e.g., DPOP) for Distributed Constraint Optimization Problems (DCOPs) require only a linear number of messages, but they cannot be directly applied into ADCOPs due to a privacy concern. Therefore, in the paper, we consider the possibility of combining inference and search to effectively solve ADCOPs at an acceptable loss of privacy. Specifically, we propose a hybrid complete algorithm called PT-ISABB which uses a tailored inference algorithm to provide tight lower bounds and a tree-based complete search algorithm to exhaust the search space. We prove the correctness of our algorithm and the experimental results demonstrate its superiority over other state-of-the-art complete algorithms.
Yusuke Kobayashi
2019-03-04
For a positive integer
and a graph , an additive -spanner of is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus . Minimum Additive -Spanner Problem is to find an additive -spanner with the minimum number of edges in a given graph, which is known to be NP-hard. Since we need to care about global properties of graphs when we deal with additive -spanners, Minimum Additive -Spanner Problem is hard to handle, and hence only few results are known for it. In this paper, we study Minimum Additive -Spanner Problem from the viewpoint of parameterized complexity. We formulate a parameterized version of the problem in which the number of removed edges is regarded as a parameter, and give a fixed-parameter algorithm for it. We also extend our result to -spanners.
Yi Li, Vasileios Nakos
2019-03-03
In this paper we revisit the deterministic version of the Sparse Fourier Transform problem. While the randomized case is well-understood, the main work in the deterministic case is the work of Merhi et al. (J Fourier Anal Appl 2018), which obtains O(k^2 log^{5.5} n) samples and similar runtime with the \ell_2/\ell_1 guarantee. We focus on the stronger \ell_\infty/\ell_1 guarantee and the closely related problem of incoherent matrices. We list our contributions as follows. 1. We give a "for-all" scheme with O(k^2 log n) samples. 2. We give a for-all scheme with O(k^2 log^2 n) samples, and O(k^2 log^3 n) time. 3. We derandomize both schemes in polynomial time in n, such that all subsequent Sparse Fourier Transform "queries" can be answered deterministically in O(nk log n) and O(k^2 log^3 n) time, respectively. 4. We give two different deterministic constructions of incoherent matrices, combinatorial objects that are closely related to \ell_infty/\ell_1 sparse recovery schemes. The first one keeps rows of the Discrete Fourier Matrix, while the second uses Fourier-friendly measurements with the help of the Weil bound from algebraic geometry. Our constructions match previous constructions by DeVore (J Complexity 2007), Amini and Marvasti (IEEE Trans Info Theory 2011) and Nelson, Nguyen and Woodruff (RANDOM 12), where there was no constraint on the form of the incoherent matrix. Our algorithms are nearly sample optimal, since a lower bound of {\Omega}(k^2 + k log n) is known, even for the case where the sensing matrix can be arbitrarily designed. Similarly, for incoherent matrices, a lower bound of {\Omega}(k^2 log n/ log k) is known, indicating that our constructions are nearly optimal.
Yael Hitron, Merav Parter
2019-02-27
We consider the task of measuring time with probabilistic threshold gates implemented by bio-inspired spiking neurons. In the model of spiking neural networks, network evolves in discrete rounds, where in each round, neurons fire in pulses in response to a sufficiently high membrane potential. This potential is induced by spikes from neighboring neurons that fired in the previous round, which can have either an excitatory or inhibitory effect. We first consider a deterministic implementation of a neural timer and show that
(deterministic) threshold gates are both sufficient and necessary. This raised the question of whether randomness can be leveraged to reduce the number of neurons. We answer this question in the affirmative by considering neural timers with spiking neurons where the neuron is required to fire for consecutive rounds with probability at least , and should stop firing after at most rounds with probability for some input parameter . Our key result is a construction of a neural timer with spiking neurons. Interestingly, this construction uses only one spiking neuron, while the remaining neurons can be deterministic threshold gates. We complement this construction with a matching lower bound of neurons. This provides the first separation between deterministic and randomized constructions in the setting of spiking neural networks. Finally, we demonstrate the usefulness of compressed counting networks for synchronizing neural networks.
