Theory of Computing Blog Aggregator

The P=NP story without symbols.

[ The Movie ]

Dr. Strangelove is the classic 1964 movie about the potential for nuclear war between the US and the Soviet Union during the cold war. The film was directed by Stanley Kubrick and stars Peter Sellers, George Scott, Sterling Hayden, and Slim Pickens.

Today we try to explain the P=NP problem in an “analog” fashion.

In Dr. Strangelove, US President Merkin Muffley wishes to recall a group of US bombers that are incorrectly about to drop nuclear weapons on Russia. He hopes to stop war. Here is the conversation between General Turgidson played by Scott and Muffley played by Sellers, in which Turgidson informs that the recall message will not be received…

Turgidson: …unless the message is preceded by the correct three-letter prefix.

Muffley: Then do you mean to tell me, General Turgidson, that you will be unable to recall the aircraft?

Turgidson: That’s about the size of it. However, we are plowing through every possible three letter combination of the code. But since there are seventeen thousand permutations it’s going to take us about two and a half days to transmit them all.

Muffley: How soon did you say the planes would penetrate Russian radar cover?

Turgidson: About eighteen minutes from now, sir.

This is the problem that P=NP addresses. How do you find a solution to a problem that has many potential solutions? In this case there are over thousands of possible combinations. Since each requires sending a message to an electronic unit that sits on a plane, thousands of miles away, and since messages cannot be sent too often, it will take much too long to find the secret message.

The central P=NP question is: Can we do better than trying all possibilities? The answer is yes—at least in the case of the movie, the secret combination is indeed found. More on that in a moment.

Opening Mechanical Locks

In Dr. Strangelove the issue is finding the three letter code for a certain device that sits on the bombers. The protocol is: Send a three letter code to the bombers. If the code is correct, then the bombers will be recalled, and all is saved. If the code is wrong, then nothing happens.

Instead of this, consider the same type of problem for finding the combination to a mechanical lock. That is a lock that is often at a gym, for example, to protect your belongings. Recall you spin the lock’s dial three times to the right, stop on the first number, then turn one time to the left, stop on the second number, and finally go to the right to stop at the third number. Then you pull the lock open.

This works provided you know the combination. In general there are 64,000 such combinations. So unless you know the numbers, you are in trouble. Trying all possible combinations is not possible for mortals. But there is hope. It is possible to find the combination without knowing it. This is possible provided: You have the combination lock in your hands.

If you only can send a possible combination to someone else to try, you are out of luck. Unfortunately in Dr. Strangelove the device on the bomber is not in your hands. So as the General says, we are trying all the possible combinations one at a time. But if the device is local you can do better.

Breaking The Locks

There are many sites on the web that explain how to do much better. Here is one way to find the first number for a lock:

  1. Pull up gently on the shackle and hold it in place. Turn the dial clockwise listening carefully until you hear the lock click.

  2. Start with a good deal of pressure and gently let up as you spin it around, until you meet resistance in only one place. It should catch in only one place, making a click.

  3. Add 5 to that number and write it down.

This is the first number in the combination. There are similar methods to get the remaining two numbers. But already you have reduced the choices for the combination from 64,000 by a factor of 40. The rest of the how-to-do rules help you get the remaining two numbers.

Note this attack relies on physical properties of the lock. A lock is made from springs and gears and rods, and is not perfect. As you turn the dial the mechanical parts rub and make noises. These noises reveal information, that is useful to you. Information that can reveal the combination of the lock.

Opening Digital Locks

The point is that there is a way to open a lock without knowing the combination. Here the trick is that you can try and use the lock and play with it in a way that it reveals information about its secret combination. This is what the P=NP question asks:

Are there ways to manipulate a digital lock and get it to reveal information?

Put another way: Do digital locks make noise?

Essentially P=NP is true if digital locks all are imperfect, like mechanical locks. That is, if digital locks all make noise. It is widely believed that is false. The belief is that P{\neq} NP which means that there are essentially perfect digital locks. That is some digital locks make no noise.

P{\neq} NP

Why is it believed that digital locks can be perfect? Well the answer is simple. To date certain types of digital locks have not been broken. That is no one yet knows how to make them click and reveal information. This is of course a dangerous position for several reasons.

  1. The failure to break a lock does not mean that someone cleverer cannot break it.

  2. There are reasons that if some people knew how to break certain digital locks that they would not tell anyone. They might prefer to keep their ability secret to make money or cause harm.

  3. Finally, it seems dangerous to guess that anything can be done without noise.

The latter point is that making systems work perfectly is usually impossible. Mechanical systems must have friction of some kind, and it seems possible that digital systems will also. We will see.

Smart Search

Colonel Ripper, played by Hayden, is the one that launched the bombers against Russia. The recall code is found and the bombers are recalled. An officer named Mandrake, played by Sellers too, notices some doodles on a pad by the crazy Ripper. It is covered with an interlocking pattern of the words Peace On Earth, and Purity Of Essence. Ripper is obsessed with these ideas—do not ask why.

Mandrake: Peace on Earth. Peace on Earth. Peace on Earth: P O E.
Purity of essence. O P E. (whispers) O P E.

This is the key. This information is sent to the Pentagon and soon the bombers are recalled. The search space is cut down from thousands to 6 possible orders. Success. Well if you’ve seen the movie, you know it was not exactly success, but that failure has nothing to do with our attempt to explain the P=NP question.

This second idea is different from whether locks make noise. It is whether every lock has a giveaway by dint of the process by which we obtained that particular lock to begin with. Note that the lock is not the definition of the problem itself, like SAT or graph 3-coloring, but rather a particular instance of the problem. We have discussed how instances of factoring that tend to be generated by algorithms have collective giveaways in an earlier post—which quotes another part of Dr. Strangelove.

Open Problems

I love the movie Dr. Strangelove, and love any excuse to talk about it. So please forgive me this story about P=NP. I hope that trying to understand the P=NP question without complex notation may help us better understand it. What do you all think?

by rjlipton at February 20, 2020 04:12 PM UTC

The next TCS+ talk will take place this coming Wednesday, February 26th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Henry Yuen from University of Toronto will speak about “MIP* = RE” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: MIP* denotes the class of problems that admit interactive proofs with quantum entangled provers. It has been an outstanding question to characterize the complexity of MIP*. Most notably, there was no known computable upper bound on this class.
We show that MIP* is equal to the class RE, the set of recursively enumerable languages. In particular, this shows that MIP* contains uncomputable problems. Through a series of known connections, this also yields a negative answer to Connes’ Embedding Problem from the theory of operator algebras. In this talk, I will explain the connection between Connes’ Embedding Problem, quantum information theory, and complexity theory. I will then give an overview of our approach, which involves reducing the Halting Problem to the problem of approximating the entangled value of nonlocal games.
Joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright.

by plustcs at February 20, 2020 08:30 AM UTC

Authors: Jan Kratochvíl, Tomáš Masařík, Jana Novotná
Download: PDF
Abstract: Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphs; a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not claw-free, compared to unit interval graphs.

Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs. The original bubble model was used by Boyaci, Ekim, and Shalom for proving the polynomiality of the MaxCut problem on unit interval graphs. However, we found a significant mistake in the proof which seems to be hardly repairable. Moreover, we demonstrate the advantages of such a model by providing a subexponential-time algorithm solving the MaxCut problem on mixed unit interval graphs using our extended version of the bubble model. In addition, it gives us a polynomial-time algorithm for specific mixed unit interval graphs; that improves a state-of-the-art result even for unit interval graphs. We further provide a better algorithmic upper-bound on the clique-width of mixed unit interval graphs. Clique-width is one of the most general structural graph parameters, where a large group of natural problems is still solvable in the tracktable time when an efficient representation is given. Unfortunately, the exact computation of the clique-width representation is NP-hard. Therefore, good upper-bounds on clique-width are highly appreciated.

at February 20, 2020 12:00 AM UTC

Authors: Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Slobodan Mitrović, Ronitt Rubinfeld
Download: PDF
Abstract: Subgraph counting is a fundamental problem in analyzing massive graphs, often studied in the context of social and complex networks. There is a rich literature on designing efficient, accurate, and scalable algorithms for this problem. In this work, we tackle this challenge and design several new algorithms for subgraph counting in the Massively Parallel Computation (MPC) model:

Given a graph $G$ over $n$ vertices, $m$ edges and $T$ triangles, our first main result is an algorithm that, with high probability, outputs a $(1+\varepsilon)$-approximation to $T$, with optimal round and space complexity provided any $S \geq \max{(\sqrt m, n^2/m)}$ space per machine, assuming $T=\Omega(\sqrt{m/n})$.

Our second main result is an $\tilde{O}_{\delta}(\log \log n)$-rounds algorithm for exactly counting the number of triangles, parametrized by the arboricity $\alpha$ of the input graph. The space per machine is $O(n^{\delta})$ for any constant $\delta$, and the total space is $O(m\alpha)$, which matches the time complexity of (combinatorial) triangle counting in the sequential model. We also prove that this result can be extended to exactly counting $k$-cliques for any constant $k$, with the same round complexity and total space $O(m\alpha^{k-2})$. Alternatively, allowing $O(\alpha^2)$ space per machine, the total space requirement reduces to $O(n\alpha^2)$.

Finally, we prove that a recent result of Bera, Pashanasangi and Seshadhri (ITCS 2020) for exactly counting all subgraphs of size at most $5$, can be implemented in the MPC model in $\tilde{O}_{\delta}(\sqrt{\log n})$ rounds, $O(n^{\delta})$ space per machine and $O(m\alpha^3)$ total space. Therefore, this result also exhibits the phenomenon that a time bound in the sequential model translates to a space bound in the MPC model.

at February 20, 2020 12:00 AM UTC

Authors: Srinivasan Arunachalam, Alex B. Grilo, Henry Yuen
Download: PDF
Abstract: We propose a learning model called the quantum statistical learning QSQ model, which extends the SQ learning model introduced by Kearns to the quantum setting. Our model can be also seen as a restriction of the quantum PAC learning model: here, the learner does not have direct access to quantum examples, but can only obtain estimates of measurement statistics on them. Theoretically, this model provides a simple yet expressive setting to explore the power of quantum examples in machine learning. From a practical perspective, since simpler operations are required, learning algorithms in the QSQ model are more feasible for implementation on near-term quantum devices. We prove a number of results about the QSQ learning model. We first show that parity functions, (log n)-juntas and polynomial-sized DNF formulas are efficiently learnable in the QSQ model, in contrast to the classical setting where these problems are provably hard. This implies that many of the advantages of quantum PAC learning can be realized even in the more restricted quantum SQ learning model. It is well-known that weak statistical query dimension, denoted by WSQDIM(C), characterizes the complexity of learning a concept class C in the classical SQ model. We show that log(WSQDIM(C)) is a lower bound on the complexity of QSQ learning, and furthermore it is tight for certain concept classes C. Additionally, we show that this quantity provides strong lower bounds for the small-bias quantum communication model under product distributions. Finally, we introduce the notion of private quantum PAC learning, in which a quantum PAC learner is required to be differentially private. We show that learnability in the QSQ model implies learnability in the quantum private PAC model. Additionally, we show that in the private PAC learning setting, the classical and quantum sample complexities are equal, up to constant factors.

at February 20, 2020 12:00 AM UTC

Authors: Siddharth Bhandari, Prahladh Harsha
Download: PDF
Abstract: Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudl\'{a}k's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudl\'{a}k and Cohen-Haeupler-Schulman's constructions.

at February 20, 2020 12:00 AM UTC

Authors: Fedor V. Fomin, Petr A. Golovach
Download: PDF
Abstract: We study the algorithmic properties of the graph class Chordal-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. We discover that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from Chordal-ke. We identify a large class of optimization problems on Chordal-ke that admit algorithms with the typical running time 2^{O(\sqrt{k}\log k)}\cdot n^{O(1)}. Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on Chordal-ke when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of Chordal-ke graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on Chordal-ke graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on Chordal-ke graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of Chordal-ke, namely, Interval-ke and Split-ke graphs.

at February 20, 2020 02:31 AM UTC

Authors: Marco Pegoraro, Merih Seran Uysal, Wil M. P. van der Aalst
Download: PDF
Abstract: The discipline of process mining deals with analyzing execution data of operational processes, extracting models from event data, checking the conformance between event data and normative models, and enhancing all aspects of processes. Recently, new techniques have been developed to analyze event data containing uncertainty; these techniques strongly rely on representing uncertain event data through graph-based models capturing uncertainty. In this paper we present a novel approach to efficiently compute a graph representation of the behavior contained in an uncertain process trace. We present our new algorithm, analyze its time complexity, and report experimental results showing order-of-magnitude performance improvements for behavior graph construction.

at February 20, 2020 02:40 AM UTC

Authors: Sebastian Brandt, Dennis Olivetti
Download: PDF
Abstract: In a recent breakthrough result, Balliu et al. [FOCS'19] proved a deterministic $\Omega(\min(\Delta,\log n /\log \log n))$-round and a randomized $\Omega(\min(\Delta,\log \log n/\log \log \log n))$-round lower bound for the complexity of the bipartite maximal matching problem on $n$-node graphs in the LOCAL model of distributed computing.

Both lower bounds are asymptotically tight as a function of the maximum degree $\Delta$.

We provide truly tight bounds in $\Delta$ for the complexity of bipartite maximal matching and many natural variants, up to and including the additive constant.

As a by-product, our results yield a considerably simplified version of the proof by Balliu et al.

We show that our results can be obtained via bounded automatic round elimination, a version of the recent automatic round elimination technique by Brandt [PODC'19] that is particularly suited for automatization from a practical perspective.

In this context, our work can be seen as another step towards the automatization of lower bounds in the LOCAL model.

at February 20, 2020 12:00 AM UTC

Authors: Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang
Download: PDF
Abstract: The tremendous success of deep neural networks has motivated the need to better understand the fundamental properties of these networks, but many of the theoretical results proposed have only been for shallow networks. In this paper, we study an important primitive for understanding the meaningful input space of a deep network: span recovery. For $k<n$, let $\mathbf{A} \in \mathbb{R}^{k \times n}$ be the innermost weight matrix of an arbitrary feed forward neural network $M:\mathbb{R}^n \to \mathbb{R}$, so $M(x)$ can be written as $M(x) = \sigma(\mathbf{A} x)$, for some network $\sigma:\mathbb{R}^k \to \mathbb{R}$. The goal is then to recover the row span of $\mathbf{A}$ given only oracle access to the value of $M(x)$. We show that if $M$ is a multi-layered network with ReLU activation functions, then partial recovery is possible: namely, we can provably recover $k/2$ linearly independent vectors in the row span of $\mathbf{A}$ using poly$(n)$ non-adaptive queries to $M(x)$. Furthermore, if $M$ has differentiable activation functions, we demonstrate that full span recovery is possible even when the output is first passed through a sign or $0/1$ thresholding function; in this case our algorithm is adaptive. Empirically, we confirm that full span recovery is not always possible, but only for unrealistically thin layers. For reasonably wide networks, we obtain full span recovery on both random networks and networks trained on MNIST data. Furthermore, we demonstrate the utility of span recovery as an attack by inducing neural networks to misclassify data obfuscated by controlled random noise as sensical inputs.

at February 20, 2020 12:00 AM UTC

Authors: Daniel S. Graça, Ning Zhong
Download: PDF
Abstract: In this note, we construct an algorithm that, on input of a description of a structurally stable planar dynamical flow defined on the unit disk, outputs the exact number of the (hyperbolic) equilibrium points as well the locations of all equilibriums with arbitrary precision. By arbitrary accuracy it is meant that the accuracy is included in the input of the algorithm. As a consequence, we obtain a root-finding algorithm that computes the set of all zeros of a continuously differentiable function $f$ defined on the unit ball of $\mathbb{R}^{d}$ with arbitrary accuracy, provided that the Jacobian of $f$ is invertible at each zero of $f$; moreover, the computation is uniform in $f$.

at February 20, 2020 12:00 AM UTC

Authors: Wolfgang Mulzer, Johannes Obenaus
Download: PDF
Abstract: Let $P \subseteq \mathbb{R}^2$ be a set of points and $T$ be a spanning tree of $P$. The \emph{stabbing number} of $T$ is the maximum number of intersections any line in the plane determines with the edges of $T$. The \emph{tree stabbing number} of $P$ is the minimum stabbing number of any spanning tree of $P$. We prove that the tree stabbing number is not a monotone parameter, i.e., there exist point sets $P \subsetneq P'$ such that \treestab{$P$} $>$ \treestab{$P'$}, answering a question by Eppstein \cite[Open Problem~17.5]{eppstein_2018}.

at February 20, 2020 12:00 AM UTC

Authors: Subhra Mazumdar, Arindam Pal, Francesco Parisi, V. S. Subrahmanian
Download: PDF
Abstract: Past work on evacuation planning assumes that evacuees will follow instructions -- however, there is ample evidence that this is not the case. While some people will follow instructions, others will follow their own desires. In this paper, we present a formal definition of a behavior-based evacuation problem (BBEP) in which a human behavior model is taken into account when planning an evacuation. We show that a specific form of constraints can be used to express such behaviors. We show that BBEPs can be solved exactly via an integer program called BB_IP, and inexactly by a much faster algorithm that we call BB_Evac. We conducted a detailed experimental evaluation of both algorithms applied to buildings (though in principle the algorithms can be applied to any graphs) and show that the latter is an order of magnitude faster than BB_IP while producing results that are almost as good on one real-world building graph and as well as on several synthetically generated graphs.

at February 20, 2020 12:00 AM UTC

Authors: Michael Figelius, Moses Ganardi, Markus Lohrey, Georg Zetzsche
Download: PDF
Abstract: We prove new complexity results for computational problems in certain wreath products of groups and (as an application) for free solvable group. For a finitely generated group we study the so-called power word problem (does a given expression $u_1^{k_1} \ldots u_d^{k_d}$, where $u_1, \ldots, u_d$ are words over the group generators and $k_1, \ldots, k_d$ are binary encoded integers, evaluate to the group identity?) and knapsack problem (does a given equation $u_1^{x_1} \ldots u_d^{x_d} = v$, where $u_1, \ldots, u_d,v$ are words over the group generators and $x_1,\ldots,x_d$ are variables, has a solution in the natural numbers). We prove that the power word problem for wreath products of the form $G \wr \mathbb{Z}$ with $G$ nilpotent and iterated wreath products of free abelian groups belongs to $\mathsf{TC}^0$. As an application of the latter, the power word problem for free solvable groups is in $\mathsf{TC}^0$. On the other hand we show that for wreath products $G \wr \mathbb{Z}$, where $G$ is a so called uniformly strongly efficiently non-solvable group (which form a large subclass of non-solvable groups), the power word problem is $\mathsf{coNP}$-hard. For the knapsack problem we show $\mathsf{NP}$-completeness for iterated wreath products of free abelian groups and hence free solvable groups. Moreover, the knapsack problem for every wreath product $G \wr \mathbb{Z}$, where $G$ is uniformly efficiently non-solvable, is $\Sigma^2_p$-hard.

at February 20, 2020 12:00 AM UTC

Authors: Patrick Dinklage
Download: PDF
Abstract: The wavelet tree (Grossi et al. [SODA, 2003]) and wavelet matrix (Claude et al. [Inf. Syst., 2015]) are compact data structures with many applications such as text indexing or computational geometry. By continuing the recent research of Fischer et al. [ALENEX, 2018], we explore the similarities and differences of these heavily related data structures with focus on their construction. We develop a data structure to modify construction algorithms for either the wavelet tree or matrix to construct instead the other. This modification is efficient, in that it does not worsen the asymptotic time and space requirements of any known wavelet tree or wavelet matrix construction algorithm.

at February 20, 2020 12:00 AM UTC

Authors: Satoshi Kobayashi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara
Download: PDF
Abstract: Given a text $T$ of length $n$ and a pattern $P$ of length $m$, the string matching problem is a task to find all occurrences of $P$ in $T$. In this study, we propose an algorithm that solves this problem in $O((n + m)q)$ time considering the distance between two adjacent occurrences of the same $q$-gram contained in $P$. We also propose a theoretical improvement of it which runs in $O(n + m)$ time, though it is not necessarily faster in practice. We compare the execution times of our and existing algorithms on various kinds of real and artificial datasets such as an English text, a genome sequence and a Fibonacci string. The experimental results show that our algorithm is as fast as the state-of-the-art algorithms in many cases, particularly when a pattern frequently appears in a text.

at February 20, 2020 12:00 AM UTC

Authors: Lan Hu, Haomin Shi, Laurent Kneip
Download: PDF
Abstract: The present work proposes a solution to the challenging problem of registering two partial point sets of the same object with very limited overlap. We leverage the fact that most objects found in man-made environments contain a plane of symmetry. By reflecting the points of each set with respect to the plane of symmetry, we can largely increase the overlap between the sets and therefore boost the registration process. However, prior knowledge about the plane of symmetry is generally unavailable or at least very hard to find, especially with limited partial views, and finding this plane could strongly benefit from a prior alignment of the partial point sets. We solve this chicken-and-egg problem by jointly optimizing the relative pose and symmetry plane parameters, and notably do so under global optimality by employing the branch-and-bound (BnB) paradigm. Our results demonstrate a great improvement over the current state-of-the-art in globally optimal point set registration for common objects. We furthermore show an interesting application of our method to dense 3D reconstruction of scenes with repetitive objects.

at February 20, 2020 12:00 AM UTC

Authors: Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Yixin Shen
Download: PDF
Abstract: The most important computational problem on lattices is the Shortest Vector Problem ($SVP$). In this paper we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for $SVP$. We present the following results.

$\bullet$ A new algorithm for $SVP$ that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer $q>1$, our algorithm takes $q^{\Theta(n)}$ time and requires $q^{\Theta(n/q)}$ memory. In fact, we give a similar time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter.

$\bullet$ A quantum algorithm that runs in time $2^{0.9532n+o(n)}$ and requires $2^{0.5n+o(n)}$ classical memory and $poly(n)$ qubits. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ADRS15] that has a time and space complexity $2^{n+o(n)}$.

$\bullet$ A classical algorithm for $SVP$ that runs in time $2^{1.73n+o(n)}$ time and $2^{0.5n+o(n)}$ space and improves over an algorithm from [CCL18] that has the same space complexity.

at February 20, 2020 12:00 AM UTC

Authors: Haitao Wang
Download: PDF
Abstract: Given a set $S$ of $n$ points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of $S$. Previously, Eppstein [SODA'97] gave a randomized algorithm of $O(n\log^2n)$ expected time and Chan [CGTA'99] presented a deterministic algorithm of $O(n\log^2 n\log^2\log n)$ time. In this paper, we propose an $O(n\log^2 n)$ time deterministic algorithm, which improves Chan's deterministic algorithm and matches the randomized bound of Eppstein. If $S$ is in convex position, then we solve the problem in $O(n\log n\log\log n)$ deterministic time. Our results rely on new techniques for dynamically maintaining circular hulls under point insertions and deletions, which are of independent interest.

at February 20, 2020 12:00 AM UTC

Authors: Robert Vicari
Download: PDF
Abstract: The bidirected cut relaxation is the characteristic representative of the bidirected relaxations ($\mathrm{\mathcal{BCR}}$) which are a well-known class of equivalent LP-relaxations for the NP-hard Steiner Tree Problem in Graphs (STP). Although no general approximation algorithm based on $\mathrm{\mathcal{BCR}}$ with an approximation ratio better than $2$ for STP is known, it is mostly preferred in integer programming as an implementation of STP, since there exists a formulation of compact size, which turns out to be very effective in practice.

It is known that the integrality gap of $\mathrm{\mathcal{BCR}}$ is at most $2$, and a long standing open question is whether the integrality gap is less than $2$ or not. The best lower bound so far is $\frac{36}{31} \approx 1.161$ proven by Byrka et al. [BGRS13]. Based on the work of Chakrabarty et al. [CDV11] about embedding STP instances into simplices by considering appropriate dual formulations, we improve on this result by constructing a new class of instances and showing that their integrality gaps tend at least to $\frac{6}{5} = 1.2$.

More precisely, we consider the class of equivalent LP-relaxations $\mathrm{\mathcal{BCR}}^{+}$, that can be obtained by strengthening $\mathrm{\mathcal{BCR}}$ by already known straightforward Steiner vertex degree constraints, and show that the worst case ratio regarding the optimum value between $\mathrm{\mathcal{BCR}}$ and $\mathrm{\mathcal{BCR}}^{+}$ is at least $\frac{6}{5}$. Since $\mathrm{\mathcal{BCR}}^{+}$ is a lower bound for the hypergraphic relaxations ($\mathrm{\mathcal{HYP}}$), another well-known class of equivalent LP-relaxations on which the current best $(\ln(4) + \varepsilon)$-approximation algorithm for STP by Byrka et al. [BGRS13] is based, this worst case ratio also holds for $\mathrm{\mathcal{BCR}}$ and $\mathrm{\mathcal{HYP}}$.

at February 20, 2020 12:00 AM UTC

Authors: Matteo Böhm, Adriano Fazzone, Stefano Leonardi, Chris Schwiegelshohn
Download: PDF
Abstract: A fair clustering instance is given a data set $A$ in which every point is assigned some color. Colors correspond to various protected attributes such as sex, ethnicity, or age. A fair clustering is an instance where membership of points in a cluster is uncorrelated with the coloring of the points.

Of particular interest is the case where all colors are equally represented. If we have exactly two colors, Chierrichetti, Kumar, Lattanzi and Vassilvitskii (NIPS 2017) showed that various $k$-clustering objectives admit a constant factor approximation. Since then, a number of follow up work has attempted to extend this result to a multi-color case, though so far, the only known results either result in no-constant factor approximation, apply only to special clustering objectives such as $k$-center, yield bicrititeria approximations, or require $k$ to be constant.

In this paper, we present a simple reduction from unconstrained $k$-clustering to fair $k$-clustering for a large range of clustering objectives including $k$-median, $k$-means, and $k$-center. The reduction loses only a constant factor in the approximation guarantee, marking the first true constant factor approximation for many of these problems.

at February 20, 2020 12:00 AM UTC

Authors: Adrian Dumitrescu, Anirban Ghosh, Csaba D. Tóth
Download: PDF
Abstract: A unit disk graph $G$ on a given set of points $P$ in the plane is a geometric graph where an edge exists between two points $p,q \in P$ if and only if $|pq| \leq 1$. A subgraph $G'$ of $G$ is a $k$-hop spanner if and only if for every edge $pq\in G$, the topological shortest path between $p,q$ in $G'$ has at most $k$ edges. We obtain the following results for unit disk graphs.

(i) Every $n$-vertex unit disk graph has a $5$-hop spanner with at most $5.5n$ edges. We analyze the family of spanners constructed by Biniaz (WADS 2019) and improve the upper bound on the number of edges from $9n$ to $5.5n$.

(ii) Using a new construction, we show that every $n$-vertex unit disk graph has a $3$-hop spanner with at most $11n$ edges.

(iii) Every $n$-vertex unit disk graph has a $2$-hop spanner with $O(n^{3/2})$ edges. This is the first construction of a $2$-hop spanner with a subquadratic number of edges.

(iv) For every sufficiently large $n$, there exists a set $P$ of $n$ points such that every plane hop spanner on $P$ has hop stretch factor at least $4$. Previously, no lower bound greater than $2$ was known.

(v) For every point set on a circle, there exists a plane $4$-hop spanner. As such, this provides a tight bound for points on a circle.

(vi) The maximum degree of $k$-hop spanners cannot be bounded above by a function of $k$.

at February 20, 2020 12:00 AM UTC

Authors: Andreas Emil Feldmann, Davis Issac, Ashutosh Rai
Download: PDF
Abstract: We develop an FPT algorithm and a kernel for the Weighted Edge Clique Partition (WECP) problem, where a graph with $n$ vertices and integer edge weights is given together with an integer $k$, and the aim is to find $k$ cliques, such that every edge appears in exactly as many cliques as its weight. The problem has been previously only studied in the unweighted version called Edge Clique Partition (ECP), where the edges need to be partitioned into $k$ cliques. It was shown that ECP admits a kernel with $k^2$ vertices [Mujuni and Rosamond, 2008], but this kernel does not extend to WECP. The previously fastest algorithm known for ECP had a runtime of $2^{O(k^2)}n^{O(1)}$ [Issac, 2019]. For WECP we develop a bi-kernel with $4^k$ vertices, and an algorithm with runtime $2^{O(k^{3/2}w^{1/2}\log(k/w))}n^{O(1)}$, where $w$ is the maximum edge weight. The latter in particular improves the runtime for ECP to~$2^{O(k^{3/2}\log k)}n^{O(1)}$. We also show that our algorithm necessarily needs a runtime of $2^{\Theta(k^{3/2}\log k)}n^{O(1)}$ to solve ECP.

at February 19, 2020 12:00 AM UTC

Authors: Max A. Deppert, Klaus Jansen, Kim-Manuel Klein
Download: PDF
Abstract: We introduce a very natural generalization of the well-known problem of simultaneous congruences. Instead of searching for a positive integer $s$ that is specified by $n$ fixed remainders modulo integer divisors $a_1,\dots,a_n$ we consider remainder intervals $R_1,\dots,R_n$ such that $s$ is feasible if and only if $s$ is congruent to $r_i$ modulo $a_i$ for some remainder $r_i$ in interval $R_i$ for all $i$.

This problem is a special case of a 2-stage integer program with only two variables per constraint which is is closely related to directed Diophantine approximation as well as the mixing set problem. We give a hardness result showing that the problem is NP-hard in general.

Motivated by the study of the mixing set problem and a recent result in the field of real-time systems we investigate the case of harmonic divisors, i.e. $a_{i+1}/a_i$ is an integer for all $i<n$. We present an algorithm to decide the feasibility of an instance in time $\mathcal{O}(n^2)$ and we show that even the smallest feasible solution can be computed in strongly polynomial time $\mathcal{O}(n^3)$.

at February 19, 2020 12:00 AM UTC

Authors: Lee-Ad Gottlieb, Robert Krauthgamer, Havana Rika
Download: PDF
Abstract: We consider the rooted orienteering problem in Euclidean space: Given $n$ points $P$ in $\mathbb R^d$, a root point $s\in P$ and a budget $\mathcal B>0$, find a path that starts from $s$, has total length at most $\mathcal B$, and visits as many points of $P$ as possible. This problem is known to be NP-hard, hence we study $(1-\delta)$-approximation algorithms. The previous Polynomial-Time Approximation Scheme (PTAS) for this problem, due to Chen and Har-Peled (2008), runs in time $n^{O(d\sqrt{d}/\delta)}(\log n)^{(d/\delta)^{O(d)}}$, and improving on this time bound was left as an open problem. Our main contribution is a PTAS with a significantly improved time complexity of $n^{O(1/\delta)}(\log n)^{(d/\delta)^{O(d)}}$.

A known technique for approximating the orienteering problem is to reduce it to solving $1/\delta$ correlated instances of rooted $k$-TSP (a $k$-TSP tour is one that visits at least $k$ points). However, the $k$-TSP tours in this reduction must achieve a certain excess guarantee (namely, their length can surpass the optimum length only in proportion to a parameter of the optimum called excess) that is stronger than the usual $(1+\delta)$-approximation. Our main technical contribution is to improve the running time of these $k$-TSP variants, particularly in its dependence on the dimension $d$. Indeed, our running time is polynomial even for a moderately large dimension, roughly up to $d=O(\log\log n)$ instead of $d=O(1)$.

at February 20, 2020 12:00 AM UTC

Authors: Tiago Novello, João Paixão, Carlos Tomei, Thomas Lewiner
Download: PDF
Abstract: Vector fields and line fields, their counterparts without orientations on tangent lines, are familiar objects in the theory of dynamical systems. Among the techniques used in their study, the Morse--Smale decomposition of a (generic) field plays a fundamental role, relating the geometric structure of phase space to a combinatorial object consisting of critical points and separatrices. Such concepts led Forman to a satisfactory theory of discrete vector fields, in close analogy to the continuous case. In this paper, we introduce discrete line fields. Again, our definition is rich enough to provide the counterparts of the basic results in the theory of continuous line fields: a Euler-Poincar\'e formula, a Morse--Smale decomposition and a topologically consistent cancellation of critical elements, which allows for topological simplification of the original discrete line field.

at February 20, 2020 12:00 AM UTC

Authors: Amir M. Mirzendehdel, Morad Behandish, Saigopal Nelaturi
Download: PDF
Abstract: In this paper, we present a topology optimization (TO) framework to enable automated design of mechanical components while ensuring the result can be manufactured using multi-axis machining. Although TO improves the part's performance, the as-designed model is often geometrically too complex to be machined and the as-manufactured model can significantly vary due to machining constraints that are not accounted for during TO. In other words, many of the optimized design features cannot be accessed by a machine tool without colliding with the part (or fixtures). The subsequent post-processing to make the part machinable with the given setup requires trial-and-error without guarantees on preserving the optimized performance. Our proposed approach is based on the well-established accessibility analysis formulation using convolutions in configuration space that is extensively used in spatial planning and robotics. We define an 'inaccessibility measure field' (IMF) over the design domain to identify non-manufacturable features and quantify their contribution to non-manufacturability. The IMF is used to penalize the sensitivity field of performance objectives and constraints to prevent formation of inaccessible regions. Unlike existing discrete formulations, our IMF provides a continuous spatial field that is desirable for TO convergence. Our approach applies to arbitrary geometric complexity of the part, tools, and fixtures, and is highly parallelizable on multi-core architecture. We demonstrate the effectiveness of our framework on benchmark and realistic examples in 2D and 3D. We also show that it is possible to directly construct manufacturing plans for the optimized designs based on the accessibility information.

at February 20, 2020 12:00 AM UTC

Authors: Sujoy Bhore, Guangping Li, Martin Nöllenburg
Download: PDF
Abstract: We study the maximal independent set (MIS) and maximum independent set (MAX-IS) problems on dynamic sets of $O(n)$ axis-parallel rectangles, which can be modeled as dynamic rectangle intersection graphs. We consider the fully dynamic vertex update (insertion/deletion) model for two types of rectangles: (i) uniform height and width and (ii) uniform height and arbitrary width. These types of dynamic vertex update problems arise, e.g., in interactive map labeling. We present the first deterministic algorithm for maintaining a MIS (and thus a 4-approximate MAX-IS) of a dynamic set of uniform rectangles with amortized sub-logarithmic update time. This breaks the natural barrier of $O(\Delta)$ update time (where $\Delta$ is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating MAX-IS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a $4$-approximate MAX-IS with $O(1)$ update time. In a subsequent algorithm, we establish the trade-off between approximation quality $2(1+\frac{1}{k})$ and update time $O(k^2\log n)$ for $k\in \mathbb{N}$. We conclude with an algorithm that maintains a $2$-approximate MAX-IS for dynamic sets of uniform height and arbitrary width rectangles with $O(\omega \log n)$ update time, where $\omega$ is the largest number of maximal cliques stabbed by any axis-parallel line. We have implemented our algorithms and report the results of an experimental comparison exploring the trade-off between solution size and update time for synthetic and real-world map labeling data sets.

at February 20, 2020 12:00 AM UTC

Authors: Eduard Eiben, Fedor V. Fomin, Fahad Panolan, Kirill Simonov
Download: PDF
Abstract: 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 $l$ districts. Here integers $k$ and $l$ 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)\cdot m^{o(\sqrt{k})}$ algorithm for any function $f$ of $k$ and $n$ only, unless 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(\sqrt{k})}$.

at February 19, 2020 12:00 AM UTC

My previous post gave an example of a largish random point set where the greedy geometric spanner for distance ratio 2 had no crossings, while the spanner for the lower distance ratio had many (linearly many) crossings. And you might think from that example that there is some threshold for which distance ratios above the threshold always have planar greedy spanners, or even that the threshold is at or below 2. But it’s not true.

To see why not, we have to turn to an idea from an earlier paper of mine, “Beta-skeletons have unbounded dilation” (CGTA 2002). In it, I used a flattened variant of the Koch snowflake fractal to find bad examples for a different kind of spanner, and the same thing works here too. The intuitive idea is that these fractals form curves that, locally, look nice to a spanner algorithm (just connect consecutive pairs of points along the curve). But they pack a lot of length into a small area, forcing the spanner algorithm to eventually add some shortcuts to the curve. If we can control where it adds the shortcuts, maybe we can make pairs of shortcuts cross.

In fact the Koch snowflake itself almost works, but it has some closest pairs that are non-consecutive along the curve, allowing the greedy spanner algorithm to choose those pairs instead of the consecutive curve points that we want it to choose. If we flatten the snowflake just a little bit, that complication goes away. If we choose the distance ratio of the spanner large enough, we can make it so that the greedy spanner algorithm doesn’t add any shortcuts until it reaches pairs of points that are opposite each other on the curve. And if we make it just barely large enough for that to be true, it will be forced to add those shortcuts once it does reach that distance in the sorted ordering of the distances. For instance, here’s a point set and its non-planar greedy spanner generated in this way with spanning ratio 4:

Greedy spanner of snowflake-like curve with distance ratio 4

This pretty picture, with the three crossing shortcuts between opposite pairs of points, doesn’t quite generalize to arbitrary-order snowflake-like curves, unfortunately. It will always be possible to find a distance ratio such that the greedy algorithm adds one of these three shortcuts, as the first shortcut it needs to add. But then once it has added it, that shortcut can make the other two opposite pairs of points closer to each other in the spanner than they were, so that the greedy algorithm doesn’t need to add them. We might only get one of these three crossing edges, instead of all three. (In fact, for the point set shown here, this is exactly what happens for spanning ratio 4.5.)

Instead, let’s look for a slightly lower distance ratio , for which the first shortcuts added by the greedy spanner algorithm cut off two lobes of the snowflake instead of three. For the same points as above, works:

Greedy spanner of snowflake-like curve with distance ratio 3.5

These two-lobe shortcuts are shorter than the three-lobe shortcuts, so they’re considered earlier by the greedy algorithm. There are two crossing equilateral triangles of two-lobe shortcuts (forming a Star of David pattern) and the greedy algorithm has to include two edges from each equilateral triangle. This is because, for each of these potential shortcuts, the greedy spanner won’t include a better path between its endpoints until it has either that shortcut itself or the two other shortcuts of the same triangle. No matter which two shortcuts we choose from each of the two equilateral triangles, we get either two crossings or, as here, three crossings.

For any order of flattened Koch snowflake, there’s a distance ratio producing a greedy spanner that looks like this picture, with two or three crossings. And by choosing a snowflake of high-enough order, we can make become arbitrarily large. Or, to put it another way, the greedy spanner algorithm can generate crossings for arbitrarily large distance ratios.

(Discuss on Mastodon)

by David Eppstein at February 19, 2020 11:01 PM UTC

Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudl\'{a}k's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudl\'{a}k and Cohen-Haeupler-Schulman's constructions.

at February 19, 2020 03:04 PM UTC

The Department of Computer Science and St Catherine’s College are recruiting an Associate Professor of Computer Science in the Department of Computer Science, to start before 31 July 2020 if possible and by no later than 1 October 2020. The successful candidate will also be appointed as Fellow and Tutor in Computer Science at St Catherine’s College. (see link for details)


by shacharlovett at February 19, 2020 01:29 PM UTC

Authors: Krzysztof Nowicki, Krzysztof Onak
Download: PDF
Abstract: We study dynamic graph algorithms in the Massively Parallel Computation model (MPC), inspired by practical data processing systems. Our goal is to provide algorithms that can efficiently handle large batches of edge insertions and deletions.

We show algorithms that require fewer rounds to update a solution to problems such as Minimum Spanning Forest and Maximal Matching than would be required by their static counterparts to compute it from scratch. They work in the most restrictive memory regime, in which local memory per machine is strongly sublinear in the number of graph vertices. Improving on the size of the batch they can handle would improve on the round complexity of known static algorithms on sparse graphs.

More precisely, we provide $O(1)$ round algorithms that can process a batch of updated of size $O(S)$ for the Minimum Spanning Forest problem and a batch of updates of size $O(S^{1-\varepsilon})$ for the Maximal Matching problem, where $S$ is the limit on the local memory of a single machine.

at February 19, 2020 12:00 AM UTC

Authors: Pratibha Choudhary
Download: PDF
Abstract: Given a graph $G$, and terminal vertices $s$ and $t$, the TRACKING PATHS problem asks to compute a minimum number of vertices to be marked as trackers, such that the sequence of trackers encountered in each s-t path is unique. TRACKING PATHS is NP-hard in both directed and undirected graphs in general. In this paper we give a collection of polynomial time algorithms for some restricted versions of TRACKING PATHS. We prove that TRACKING PATHS is polynomial time solvable for chordal graphs and tournament graphs. We prove that TRACKING PATHS is NP-hard in graphs with bounded maximum degree $\delta\geq 6$, and give a $2(\delta+1)$-approximate algorithm for the same. We also analyze the version of tracking s-t paths where paths are tracked using edges instead of vertices, and we give a polynomial time algorithm for the same. Finally, we show how to reconstruct an s-t path, given a sequence of trackers and a tracking set for the graph in consideration.

at February 19, 2020 12:00 AM UTC

Authors: Anthony Bonato, Konstantinos Georgiou, Calum MacRury, Pawel Pralat
Download: PDF
Abstract: We study $p$-Faulty Search, a variant of the classic cow-path optimization problem, where a unit speed robot searches the half-line (or $1$-ray) for a hidden item. The searcher is probabilistically faulty, and detection of the item with each visitation is an independent Bernoulli trial whose probability of success $p$ is known. The objective is to minimize the worst case expected detection time, relative to the distance of the hidden item to the origin. A variation of the same problem was first proposed by Gal in 1980. Then in 2003, Alpern and Gal [The Theory of Search Games and Rendezvous] proposed a so-called monotone solution for searching the line ($2$-rays); that is, a trajectory in which the newly searched space increases monotonically in each ray and in each iteration. Moreover, they conjectured that an optimal trajectory for the $2$-rays problem must be monotone. We disprove this conjecture when the search domain is the half-line ($1$-ray). We provide a lower bound for all monotone algorithms, which we also match with an upper bound. Our main contribution is the design and analysis of a sequence of refined search strategies, outside the family of monotone algorithms, which we call $t$-sub-monotone algorithms. Such algorithms induce performance that is strictly decreasing with $t$, and for all $p \in (0,1)$. The value of $t$ quantifies, in a certain sense, how much our algorithms deviate from being monotone, demonstrating that monotone algorithms are sub-optimal when searching the half-line.

at February 19, 2020 12:00 AM UTC

Authors: Davin Choo, Christoph Grunau, Julian Portmann, Václav Rozhoň
Download: PDF
Abstract: The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k)-approximation in expectation. Recently, Lattanzi and Sohler (ICML 2019) proposed augmenting k-means++ with O(k log log k) local search steps to yield a constant approximation (in expectation) to the k-means clustering problem. In this paper, we improve their analysis to show that, for any arbitrarily small constant $\eps > 0$, with only $\eps k$ additional local search steps, one can achieve a constant approximation guarantee (with high probability in k), resolving an open problem in their paper.

at February 19, 2020 12:00 AM UTC

Authors: Alina Ene
Download: PDF
Abstract: Motivated by team formation applications, we study discrete optimization problems of the form $\max_{S\in\mathcal{S}}\left(f(S)-w(S)\right)$, where $f:2^{V}\to\mathbb{R_{+}}$ is a non-negative monotone submodular function, $w:2^{V}\to\mathbb{R}_{+}$ is a non-negative linear function, and $\mathcal{S}\subseteq2^{V}$. We give very simple and efficient algorithms for classical constraints, such as cardinality and matroid, that work in a variety of models, including the offline, online, and streaming. Our algorithms use a very simple scaling approach: we pick an absolute constant $c\geq1$ and optimize the function $f(S)-c\cdot w(S)$ using a black-box application of standard algorithms, such as the classical Greedy algorithm and the single-threshold Greedy algorithm. These algorithms are based on recent works that use (time varying) scaling combined with classical algorithms such as the discrete and continuous Greedy algorithms (Feldman, WADS'19; Harshaw \emph{et al.}, ICML'19).

at February 19, 2020 12:00 AM UTC

Authors: Jana Cslovjecsek, Friedrich Eisenbrand, Robert Weismantel
Download: PDF
Abstract: We consider N-fold integer programming problems. After a decade of continuous progress, the currently fastest algorithm for N-fold integer programming by Jansen et al. (2019) has a running time of $(rs\Delta)^{O(r^2s + s^2)} {\phi}^2 \cdot nt \log^{O(1)}(nt)$. Here ${\phi}$ is the largest binary encoding length of a number in the input. This algorithm, like its predecessors are based on the augmentation framework, a tailored integer programming variant of local search. In this paper we propose a different approach that is not based on augmentation. Our algorithm relies on a stronger LP-relaxation of the N-fold integer program instead. This relaxation can be solved in polynomial time with parameter dependence $(s{\Delta})^{O(s^2)}$ by resorting to standard techniques from convex optimization. We show that, for any given optimal vertex solution $x^*$ of this relaxation, there exists an optimal integer solution $z^*$ that is within short $\ell_1$-distance, namely $\|x^* - z^*\|_{1} \leq (rs\Delta)^{O(rs)}$. With dynamic programming one can then find an optimal integer solution of the N-fold IP in time $(rs\Delta)^{O(r^2s + s^2)} \,nt $. This, together with an off-the-shelf-method from convex optimization, results in the currently fastest algorithm for N-fold integer programming.

at February 19, 2020 12:00 AM UTC

Authors: Pál András Papp, Roger Wattenhofer
Download: PDF
Abstract: We study financial networks with debt contracts and credit default swaps between specific pairs of banks. Given such a financial system, we want to decide which of the banks are in default, and how much of their liabilities these defaulting banks can pay. There can easily be multiple different solutions to this problem, leading to a situation of default ambiguity and a range of possible solutions to implement for a financial authority.

In this paper, we study the general properties of the solution space of such financial systems, and analyze a wide range of reasonable objective functions for selecting from the set of solutions. Examples of such objective functions include minimizing the number of defaulting banks, minimizing the amount of unpaid debt, maximizing the number of satisfied banks, maximizing the equity of a specific bank, finding the most balanced distribution of equity, and many others. We show that for all of these objective functions, it is not only NP-hard to find the optimal solution, but it is also NP-hard to approximate this optimum: for each objective function, we show an inapproximability either to an $n^{1/2-\epsilon}$ or to an $n^{1/4-\epsilon}$ factor for any $\epsilon>0$, with $n$ denoting the number of banks in the system. Thus even if an authority has clear criteria to select a solution in case of default ambiguity, it is computationally intractable to find a solution that is reasonably good in terms of this criteria. We also show that our hardness results hold in a wide range of different model variants.

at February 19, 2020 11:20 PM UTC

Authors: Jan Kessler, Jens M. Schmidt
Download: PDF
Abstract: A cycle $C$ of a graph $G$ is \emph{isolating} if every component of $G-V(C)$ is a single vertex. We show that isolating cycles in polyhedral graphs can be extended to larger ones: every isolating cycle $C$ of length $8 \leq |E(C)| < \frac{2}{3}(|V(G)|+3)$ implies an isolating cycle $C'$ of larger length that contains $V(C)$. By ``hopping'' iteratively to such larger cycles, we obtain a powerful and very general inductive motor for proving and computing long cycles (we will give an algorithm with running time $O(n^2)$). This provides a method to prove lower bounds on Tutte cycles, as $C'$ will be a Tutte cycle of $G$ if $C$ is. We also prove that $E(C') \leq E(C)+3$ if $G$ does not contain faces of size five, which gives a new tool for proving results about cycle spectra and evidence that these face sizes obstruct long cycles. As a sample application, we test our motor on a conjecture on essentially 4-connected graphs. A planar graph is \emph{essentially $4$-connected} if it is 3-connected and every of its 3-separators is the neighborhood of a single vertex. Essentially $4$-connected graphs have been thoroughly investigated throughout literature as the subject of Hamiltonicity studies. Jackson and Wormald proved that every essentially 4-connected planar graph $G$ on $n$ vertices contains a cycle of length at least $\frac{2}{5}(n+2)$, and this result has recently been improved multiple times, culminating in the lower bound $\frac{5}{8}(n+2)$. However, the best known upper bound is given by an infinite family of such graphs in which every graph $G$ on $n$ vertices has no cycle longer than $\frac{2}{3}(n+4)$; this upper bound is still unmatched. Using isolating cycles, we improve the lower bound to match the upper (up to a summand $+1$). This settles the long-standing open problem of determining the circumference of essentially 4-connected planar graphs.

at February 19, 2020 12:00 AM UTC