Computer Science – Theory and Applications

Frontmatter

Complexity of Generation

Abstract

In this talk I summarize the results obtained in 1999–2008 by Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassiony, Kazuhisa Makino, and myself, on complexity of generation algorithms. These algorithms can be partitioned into three groups: supergraph, flash-light (backtrack), and dual-bounded generation. We will call a problem tractable if it can be solved by a polynomial (\(n^{const}\)) or quasi-polynomial (\(n^{polylog(n)}\)) time algorithm. More generally, for any positive non-decreasing function \(g = g(n)\), generating can be performed in total or incremental time g, or with g-delay. Most of the polynomial delay algorithms are provided by the flash-light (backtrack) method. As for the incremental algorithms, generating the next object is equivalent with just verifying its existence, which is a standard decision problem. Thus, incremental generation, in contrast to the delay one, may be NP-hard or NP-complete. For example, we show that generating all vertices of a polyhedron, given by its facets, is NP-complete (while the complexity status is still open in case of the polytopes, that is, bounded polyhedra). This problem is reduced to generating all negative cycles of a weighted digraph, which is NP-complete (for graphs, too). Generating all minimal transversals to a hypergraph, so-called dualization, plays an important role. For this problem an incremental quasi-polynomial algorithm (but no polynomial one) is known. We outline several wide classes of generation problems that can be reduced to dualization and, thus, solved in incremental quasi-polynomial time. We survey algorithms and complexity bounds for the above and many other generation problems.

Vladimir Gurvich

Lower Bounds for Unrestricted Boolean Circuits: Open Problems

Abstract

To prove that \(\text {P} \ne \text {NP}\), it suffices to prove a superpolynomial lower bound on Boolean circuit complexity of a function from NP. Currently, we are not even close to achieving this goal: we do not know how to prove a 4n lower bound. What is more depressing is that there are almost no techniques for proving circuit lower bounds.

In this note, we briefly review various approaches that could potentially lead to stronger linear or superlinear lower bounds for unrestricted Boolean circuits (i.e., circuits with no restriction on depth, fan-out, or basis).

Alexander S. Kulikov

Online Labeling: Algorithms, Lower Bounds and Open Questions

Abstract

The online labeling problem (also known as the file maintenance problem), is a natural algorithmic problem that has arisen as a buidling block for data structures. A stream of distinct integer items is to be assigned labels online from a label set \(\{1,\ldots ,m\}\) so that the order of the labels respects the natural order of the items. Maintaining order on the labels may require relabeling items. The algorithm pays 1 each time an item is labeled or relabeled and the goal of the algorithm is to minimize the total cost.

We survey upper and lower bounds and open problems in both the deterministic and randomized setting.

Michael Saks

Maintaining Chordal Graphs Dynamically: Improved Upper and Lower Bounds

Abstract

We study upper and lower bounds for the problem of maintaining a chordal graph G under edge insertions and deletions. Let G be a chordal graph on n vertices and m edges and let (u, v) be the edge to be deleted or inserted.

• Let k be the size of the maximum clique in G. Our first result is an improved analysis of an earlier approach due to Ibarra [12] to support edge deletions. We can construct a data structure in \(O(nk^2)\) time such that we can report in O(1) time if \(G{\setminus }{(u,v)}\) is chordal and if it is, we can update the structure in \(O(n + k^2)\) time. We then show using a charging argument that the update time can be improved to \(O(n^2/\Delta + k^2)\) amortized time over a sequence of \(\Delta \) deletions.
• We develop a data structure to maintain a perfect elimination ordering (PEO) of chordal graphs where we can detect whether \(G{\setminus }{(u,v)}\) is chordal in \(O(\min \{degree(u), degree(v)\})\) time, and if it is chordal, we can update the structure in \(O(degree(u)+degree(v))\) time. In graphs of bounded degree, our query and update bounds are a constant.
• Finally, we show that we can obtain a PEO of the graph from a clique-tree in O(n) time after an edge insertion or deletion (against a naive \(O(m\,+\,n)\) time). This answers a question posed by Ibarra [12].

Regarding lower bounds, we show that any dynamic structure to maintain a chordal graph requires \(\varOmega (\log n)\) amortized time per edge addition or deletion or per query to detect chordality, in the cell probe model with word size \(\log n\).

Niranka Banerjee, Venkatesh Raman, Srinivasa Rao Satti

Distributed Symmetry-Breaking Algorithms for Congested Cliques

Abstract

The Congested Clique is a distributed-computing model for single-hop networks with restricted bandwidth that has been very intensively studied recently. It models a network by an n-vertex graph in which any pair of vertices can communicate one with another by transmitting \(O(\log n)\) bits in each round. Various problems have been studied in this setting, but for some of them the best-known results are those for general networks. For other problems, the results for Congested Cliques are better than on general networks, but still incur significant dependency on the number of vertices n. Hence the performance of these algorithms may become poor on large cliques, even though their diameter is just 1. In this paper we devise significantly improved algorithms for various symmetry-breaking problems, such as forests-decompositions, vertex-colorings, and maximal independent set.

We analyze the running time of our algorithms as a function of the arboricity a of a clique subgraph that is given as input. The arboricity is always smaller than the number of vertices n in the subgraph, and for many families of graphs it is significantly smaller. In particular, trees, planar graphs, graphs with constant genus, and many other graphs have bounded arboricity, but unbounded size. We obtain O(a)-forest-decomposition algorithm with \(O(\log a)\) time that improves the previously-known \(O(\log n)\) time, \(O(a^{2 + \epsilon })\)-coloring in \(O(\log ^* n)\) time that improves upon an \(O(\log n)\)-time algorithm, O(a)-coloring in \(O(a^{\epsilon })\)-time that improves upon several previous algorithms, and a maximal independent set algorithm with \(O(\sqrt{a})\) time that improves at least quadratically upon the state-of-the-art for small and moderate values of a.

Those results are achieved using several techniques. First, we produce a forest decomposition with a helpful structure called H-partition within \(O(\log a)\) rounds. In general graphs this structure requires \(\varTheta (\log n)\) time, but in Congested Cliques we are able to compute it faster. We employ this structure in conjunction with partitioning techniques that allow us to solve various symmetry-breaking problems efficiently.

Leonid Barenboim, Victor Khazanov

The Clever Shopper Problem

Abstract

We investigate a variant of the so-called Internet Shopping problem introduced by Blazewicz et al. (2010), where a customer wants to buy a list of products at the lowest possible total cost from shops which offer discounts when purchases exceed a certain threshold. Although the problem is NP-hard, we provide exact algorithms for several cases, e.g. when each shop sells only two items, and an FPT algorithm for the number of items, or for the number of shops when all prices are equal. We complement each result with hardness proofs in order to draw a tight boundary between tractable and intractable cases. Finally, we give an approximation algorithm and hardness results for the problem of maximising the sum of discounts.

Laurent Bulteau, Danny Hermelin, Anthony Labarre, Stéphane Vialette

A Tight Lower Bound for Steiner Orientation

Abstract

In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs \(\mathscr {T}\). The question is whether we can orient the undirected edges in a way such that there is a directed \(s\leadsto t\) path for each terminal pair \((s,t)\in \mathscr {T}\). Arkin and Hassin [DAM’02] showed that the Steiner Orientation problem is NP-complete. They also gave a polynomial time algorithm for the special case when \(k=2\).

From the viewpoint of exact algorithms, Cygan, Kortsarz and Nutov [ESA’12, SIDMA’13] designed an XP algorithm running in \(n^{O(k)}\) time for all \(k\ge 1\). Pilipczuk and Wahlström [SODA ’16] showed that the Steiner Orientation problem is W[1]-hard parameterized by k. As a byproduct of their reduction, they were able to show that under the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi and Zane [JCSS’01] the Steiner Orientation problem does not admit an \(f(k)\cdot n^{o(k/\log k)}\) algorithm for any computable function f. That is, the \(n^{O(k)}\) algorithm of Cygan et al. is almost optimal.

In this paper, we give a short and easy proof that the \(n^{O(k)}\) algorithm of Cygan et al. is asymptotically optimal, even if the input graph has genus 1. Formally, we show that the Steiner Orientation problem is W[1]-hard parameterized by the number k of terminal pairs, and, under ETH, cannot be solved in \(f(k)\cdot n^{o(k)}\) time for any function f even if the underlying undirected graph has genus 1. We give a reduction from the Grid Tiling problem which has turned out to be very useful in proving W[1]-hardness of several problems on planar graphs. As a result of our work, the main remaining open question is whether Steiner Orientation admits the “square-root phenomenon” on planar graphs (graphs with genus 0): can one obtain an algorithm running in time \(f(k)\cdot n^{O(\sqrt{k})}\) for Planar Steiner Orientation, or does the lower bound of \(f(k)\cdot n^{o(k)}\) also translate to planar graphs?

Rajesh Chitnis, Andreas Emil Feldmann

Can We Create Large k-Cores by Adding Few Edges?

Abstract

The notion of a k-core, defined by Seidman [’83], has turned out to be useful in analyzing network structures. The k-core of a given simple and undirected graph is the maximal induced subgraph such that each vertex in it has degree at least k. Hence, finding a k-core helps to identify a (core) community where each entity is related to at least k other entities. One can find the k-core of a given graph in polynomial time, by iteratively deleting each vertex of degree less than k. Unfortunately, this iterative dropping out of vertices can sometimes lead to unraveling of the entire network; e.g., Schelling [’78] considered the extreme example of a path with \(k = 2\), where indeed the whole network unravels.

In order to avoid this unraveling, we would like to edit the network in order to maximize the size of its k-core. Formally, we introduce the Edge k-Core problem (EKC): given a graph G, a budget b, and a goal p, can at most b edges be added to G to obtain a k-core containing at least p vertices? First we show the following dichotomy: EKC is polytime solvable for \(k \le 2\) and NP-hard for \(k \ge 3\). Then, we show that EKC is W[1]-hard even when parameterized by \(b + k + p\). In searching for an FPT algorithm, we consider the parameter “treewidth”, and design an FPT algorithm for EKC which runs in time \((k+\mathbf{tw })^{O(\mathbf{tw }+b)}\cdot \text {poly}(n)\), where \(\mathbf{tw }\) is the treewidth of the input graph. Even though an extension of Courcelle’s theorem [Arnborg et al., J. Algorithms ’91] can be used to show FPT for EKC parameterized by \(\mathbf{tw }+k+b\), we obtain a much faster running time as compared to Courcelle’s theorem (which needs a tower of exponents) by designing a dynamic programming algorithm which needs to take into account the fact that newly added edges might have endpoints in different bags which cross the separator.

Rajesh Chitnis, Nimrod Talmon

Periodicity in Data Streams with Wildcards

Abstract

We investigate the problem of detecting periodic trends within a string S of length n, arriving in the streaming model, containing at most k wildcard characters, where \(k=o(n)\). A wildcard character is a special character that can be assigned any other character. We say S has wildcard-period p if there exists an assignment to each of the wildcard characters so that in the resulting stream the length \(n-p\) prefix equals the length \(n-p\) suffix. We present a two-pass streaming algorithm that computes wildcard-periods of S using \(\mathcal {O}\left( k^3\,{{\mathsf {polylog}}} \,n\right) \) bits of space, while we also show that this problem cannot be solved in sublinear space in one pass. We then give a one-pass randomized streaming algorithm that computes all wildcard-periods p of S with \(p<\frac{n}{2}\) and no wildcard characters appearing in the last p symbols of S, using \(\mathcal {O}\left( k^3\log ^9 n\right) \) space.

Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou

Maximum Colorful Cycles in Vertex-Colored Graphs

Abstract

In this paper, we study the problem of finding a maximum colorful cycle a vertex-colored graph. Specifically, given a graph with colored vertices, the goal is to find a cycle containing the maximum number of colors. We aim to give a dichotomy overview on the complexity of the problem. We first show that the problem is NP-hard even for simple graphs such as split graphs, biconnected graphs, interval graphs. Then we provide polynomial-time algorithms for classes of vertex-colored threshold graphs and vertex-colored bipartite chain graphs, which are our main contributions.

Giuseppe F. Italiano, Yannis Manoussakis, Nguyen Kim Thang, Hong Phong Pham

Grammar-Based Compression of Unranked Trees

Abstract

We introduce forest straight-line programs (FSLPs) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the succinctness of FSLPs with two other compression schemes for unranked trees: top dags and tree straight-line programs of first-child/next sibling encodings. Efficient translations between these formalisms are provided. Finally, we show that equality of unranked trees in the setting where certain symbols are associative or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees.

Adrià Gascón, Markus Lohrey, Sebastian Maneth, Carl Philipp Reh, Kurt Sieber

Complement for Two-Way Alternating Automata

Abstract

We consider the problem of converting a two-way alternating finite automaton (2AFA) with n states to a 2AFA accepting the complement of the original language. Complementing is trivial for halting 2AFAs, by inverting the roles of existential and universal decisions and the roles of accepting and rejecting states. However, since 2AFAs do not have resources to detect infinite loops by counting executed steps, the best construction known so far required \(\varOmega (4^n)\) states. Here we shall show that the cost of complementing is polynomial in n. This complementary simulation does not eliminate infinite loops.

Viliam Geffert

Closure Under Reversal of Languages over Infinite Alphabets

Abstract

It is shown that languages definable by weak pebble automata are not closed under reversal. For the proof, we establish a kind of periodicity of an automaton’s computation over a specific set of words. The periodicity is partly due to the finiteness of the automaton description and partly due to the word’s structure. Using such a periodicity we can find a word such that during the automaton’s run on it there are two different, yet indistinguishable, configurations. This enables us to remove a part of that word without affecting acceptance. Choosing an appropriate language leads us to the desired result.

Daniel Genkin, Michael Kaminski, Liat Peterfreund

Structural Parameterizations of Dominating Set Variants

Abstract

We consider structural parameterizations of the fundamental dominating set problem and its variants in the parameter ecology program. We give improved fixed-parameter tractable (FPT) algorithms and lower bounds under well-known conjectures for dominating set in graphs that are k vertices away from a cluster graph or a split graph. These are graphs in which there is a set of k vertices (called the modulator) whose deletion results in a cluster graph or a split graph. We also call k as the deletion distance (to the appropriate class of graphs). Specifically, we show the following results. When parameterized by the deletion distance k to cluster graphs,

• we can find a minimum dominating set in \({\mathcal O}^*(3^k)\) time (\({\mathcal O}^*\) notation ignores polynomial factors of input). Within the same time, we can also find a minimum independent dominating set (IDS) or a minimum efficient dominating set (EDS) or a minimum total dominating set. These algorithms are obtained through a dynamic programming approach for an interesting generalization of set cover which may be of independent interest.
• We complement our upper bound results by showing that at least for dominating set and total dominating set, \({\mathcal O}^*((2-\epsilon )^k)\) time algorithm is not possible for any \(\epsilon > 0\) under, what is known as, Set Cover Conjecture. We also show that most of these variants of dominating set do not have polynomial sized kernel.

The standard dominating set and most of its variants are \(\mathsf {NP}\)-hard or \(\mathsf {W}\)[2]-hard in split graphs. For the two variants IDS and EDS that are polynomial time solvable in split graphs, we show that when parameterized by the deletion distance k to split graphs,

• IDS can be solved in \({\mathcal O}^*(2^k)\) time and we provide an \(\Omega (2^k)\) lower bound under the strong exponential time hypothesis (SETH);
• the \(2^k\) barrier can be broken for EDS by designing an \({\mathcal O}^*( 3^{k/2})\) algorithm. This is one of the very few problems with a runtime better than \({\mathcal O}^*(2^k)\) in the realm of structural parameterization. We also show that no \(2^{o(k)}\) algorithm is possible unless the exponential time hypothesis (ETH) is false.

Dishant Goyal, Ashwin Jacob, Kaushtubh Kumar, Diptapriyo Majumdar, Venkatesh Raman

Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing

Abstract

We study Parallel Task Scheduling \(Pm|size_j|C_{\max }\) with a constant number of machines. This problem is known to be strongly NP-complete for each \(m \ge 5\), while it is solvable in pseudo-polynomial time for each \(m \le 3\). We give a positive answer to the long-standing open question whether this problem is strongly NP-complete for \(m=4\). As a second result, we improve the lower bound of \(\frac{12}{11}\) for approximating pseudo-polynomial Strip Packing to \(\frac{5}{4}\). Since the best known approximation algorithm for this problem has a ratio of \(\frac{4}{3} + \varepsilon \), this result narrows the gap between approximation ratio and inapproximability result by a significant step. Both results are proven by a reduction from the strongly NP-complete problem 3-Partition.

Sören Henning, Klaus Jansen, Malin Rau, Lars Schmarje

Operations on Boolean and Alternating Finite Automata

Abstract

We investigate the descriptional complexity of basic regular operations on languages represented by Boolean and alternating finite automata. In particular, we consider the operations of difference, symmetric difference, star, reversal, left quotient, and right quotient, and get tight upper bounds \(m+n, m+n, 2^n, 2^n, m,\) and \(2^m\), respectively, for Boolean automata, and \(m+n+1, m+n, 2^n, 2^n, m+1\), and \(2^m+1\), respectively, for alternating finite automata. To describe witnesses for symmetric difference, we use a ternary alphabet. All the remaining witnesses are defined over binary or unary alphabets that are shown to be optimal.

Michal Hospodár, Galina Jirásková, Ivana Krajňáková

Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized

Abstract

Let \(\mathrm{\Pi }\) be a family of graphs. In the classical \(\mathrm{\Pi }\)-Vertex Deletion problem, given a graph G and a positive integer k, the objective is to check whether there exists a subset S of at most k vertices such that \(G-S\) is in \(\mathrm{\Pi }\). In this paper, we introduce the conflict free version of this classical problem, namely Conflict Free \(\mathrm{\Pi }\)-Vertex Deletion (CF-\(\mathrm{\Pi }\)-VD), and study these problems from the viewpoint of classical and parameterized complexity. In the CF-\(\mathrm{\Pi }\)-VD problem, given two graphs G and H on the same vertex set and a positive integer k, the objective is to determine whether there exists a set \(S\subseteq V(G)\), of size at most k, such that \(G-S\) is in \(\mathrm{\Pi }\) and H[S] is edgeless. Initiating a systematic study of these problems is one of the main conceptual contribution of this work. We obtain several results on the conflict free version of several classical problems. Our first result shows that if \(\mathrm{\Pi }\) is characterized by a finite family of forbidden induced subgraphs then CF-\(\mathrm{\Pi }\)-VD is Fixed Parameter Tractable (FPT). Furthermore, we obtain improved algorithms for conflict free version of several well studied problems. Next, we show that if \(\mathrm{\Pi }\) is characterized by a “well-behaved” infinite family of forbidden induced subgraphs, then CF-\(\mathrm{\Pi }\)-VD is W[1]-hard. Motivated by this hardness result, we consider the parameterized complexity of CF-\(\mathrm{\Pi }\)-VD when H is restricted to well studied families of graphs. In particular, we show that the conflict free versions of several well-known problems such as Feedback Vertex Set, Odd Cycle Transversal, Chordal Vertex Deletion and Interval Vertex Deletion are FPT when H belongs to the families of d-degenerate graphs and nowhere dense graphs.

Pallavi Jain, Lawqueen Kanesh, Pranabendu Misra

Quadratically Tight Relations for Randomized Query Complexity

Abstract

In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions \(\mathsf {R}(f)\). The certificate complexity \(\mathsf {C}(f)\) is such a complexity measure for the zero-error randomized query complexity \(\mathsf {R}_0(f)\): \(\mathsf {C}(f) \le \mathsf {R}_0(f) \le \mathsf {C}(f)^2\). In the first part of the paper we introduce a new complexity measure, expectational certificate complexity \(\mathsf {EC}(f)\), which is also a quadratically tight bound on \(\mathsf {R}_0(f)\): \(\mathsf {EC}(f) \le \mathsf {R}_0(f) = O(\mathsf {EC}(f)^2)\). For \(\mathsf {R}(f)\), we prove that \(\mathsf {EC}^{2/3} \le \mathsf {R}(f)\). We then prove that \(\mathsf {EC}(f) \le \mathsf {C}(f) \le \mathsf {EC}(f)^2\) and show that there is a quadratic separation between the two, thus \(\mathsf {EC}(f)\) gives a tighter upper bound for \(\mathsf {R}_0(f)\). The measure is also related to the fractional certificate complexity \(\mathsf {FC}(f)\) as follows: \(\mathsf {FC}(f) \le \mathsf {EC}(f) = O(\mathsf {FC}(f)^{3/2})\). This also connects to an open question by Aaronson whether \(\mathsf {FC}(f)\) is a quadratically tight bound for \(\mathsf {R}_0(f)\), as \(\mathsf {EC}(f)\) is in fact a relaxation of \(\mathsf {FC}(f)\).

In the second part of the work, we investigate whether the corruption bound \(\mathsf {corr}_\epsilon (f)\) quadratically approximates \(\mathsf {R}(f)\). By Yao’s theorem, it is enough to prove that the square of the corruption bound upper bounds the distributed query complexity \(\mathsf {D}^\mu _\epsilon (f)\) for all input distributions \(\mu \). Here, we show that this statement holds for input distributions in which the various bits of the input are distributed independently. This is a natural and interesting subclass of distributions, and is also in the spirit of the input distributions studied in communication complexity in which the inputs to the two communicating parties are statistically independent. Our result also improves upon a result of Harsha et al. [2015], who proved a similar weaker statement. We also note that a similar statement in the communication complexity is open.

Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgēnijs Vihrovs

On Vertex Coloring Without Monochromatic Triangles

Abstract

We study a certain relaxation of the classic vertex coloring problem, namely, a coloring of vertices of undirected, simple graphs, such that there are no monochromatic triangles. We give the first classification of the problem in terms of classic and parametrized algorithms. Several computational complexity results are also presented, which improve on the previous results found in the literature. We propose the new structural parameter for undirected, simple graphs – the triangle-free chromatic number \(\chi _3\). We bound \(\chi _3\) by other known structural parameters. We also present two classes of graphs with interesting coloring properties, that play pivotal role in proving useful observations about our problem.

Michał Karpiński, Krzysztof Piecuch

Recognizing Read-Once Functions from Depth-Three Formulas

Abstract

Consider the following decision problem: for a given monotone Boolean function f decide, whether f is read-once. For this problem, it is essential how the input function f is represented. On a negative side we have the following results. Elbassioni et al. [1] proved that this problem is coNP-complete when f is given by a depth-4 read-2 monotone Boolean formula. Gurvich [2] proved that this problem is coNP-complete even when the input is the following expression: \(C\vee D_n\), where \(D_n = x_1 y_1 \vee \ldots \vee x_n y_n\) and C is a monotone CNF over the variables \(x_1, y_1, \ldots , x_n, y_n\) (note that this expression is a monotone Boolean formula of depth 3; in [2] nothing is said about the readability of C, but the proof is valid even if C is read-2 and thus the entire formula is read-3).

On a positive side, from [3] we know that there is a polynomial time algorithm to recognize read-once functions when the input is a monotone depth-2 formula (that is, a DNF or a CNF). There are even very fast algorithms for this problem [4].

Our contribution consists of the following two results. We show that we can test in polynomial-time whether a given expression \(C\vee D\) computes a read-once function, provided that C is a read-once monotone CNF and D is a read-once monotone DNF and all the variables of C occur also in D (recall that due to Gurvich, the problem is coNP-complete when C is read-2). The second result states that this is a coNP-complete problem to decide whether the expression \(A\wedge D_n\) computes a read-once function, where \(D_n\) is as above and A is the \(\bigwedge -\bigvee -\bigwedge \) depth-3 read-once monotone Boolean formula (so that the entire expression \(A\wedge D_n\) is depth-3 read-2). This result improves the result of [1] in the depth and the result of [2] in the readability of the input formula.

Alexander Kozachinskiy

Max-Cut Above Spanning Tree is Fixed-Parameter Tractable

Abstract

Every connected graph on n vertices has a cut of size at least \(n-1\). We call this bound the ‘spanning tree bound’. In the Max-Cut Above Spanning Tree (Max-Cut-AST) problem, we are given a connected n-vertex graph G and a non-negative integer k, and the task is to decide whether G has a cut of size at least \(n-1+k\). We show that Max-Cut-AST admits an algorithm that runs in time \(\mathcal {O}(8^kn^{\mathcal {O}(1)})\), and hence it is fixed parameter tractable with respect to k. Furthermore, we show that Max-Cut-AST has a polynomial kernel of size \(\mathcal {O}(k^5)\).

Jayakrishnan Madathil, Saket Saurabh, Meirav Zehavi

Slopes of 3-Dimensional Subshifts of Finite Type

Abstract

In this paper we study the directions of periodicity of three-dimensional subshifts of finite type (SFTs) and in particular their slopes. A configuration of a subshift has a slope of periodicity if it is periodic in exactly one direction, the slope being the angles of the periodicity vector. In this paper, we prove that any \(\varSigma ^0_2\) set may be realized as a a set of slopes of an SFT.

Etienne Moutot, Pascal Vanier

Facility Location on Planar Graphs with Unreliable Links

Abstract

Hassin et al. [9] consider the Max-Exp-Cover-R problem to study the facility location problem on a graph in the presence of unreliable links when the link failure is according to the Linear Reliability Order (LRO) model. They showed that for unbounded R the problem is polynomial time solvable and for \(R=1\) and planar graphs the problem is NP-Complete. In this paper, we study the Max-Exp-Cover-1 problem under the LRO edge failure model. We obtain a fixed parameter tractable algorithm for Max-Exp-Cover-1 problem for bounded treewidth graphs, parameterized by the treewidth. We extend the Baker’s technique (Baker, J. ACM 1994) to obtain PTAS for Max-Exp-Cover-1 problem under the LRO model on planar graphs. We observe that the coverage function of the Max-Exp-Cover-R problem is submodular and the problem admits a \((1-1/e)\)-approximation for any failure model in which the expected coverage of a set by another set can be computed in polynomial time.

N. S. Narayanaswamy, Meghana Nasre, R. Vijayaragunathan

On the Decision Trees with Symmetries

Abstract

We introduce a propositional proof system based on decision trees utilizing symmetries of formulas. We refer to this proof system as decision trees with symmetries (\(\mathrm {SDT}\)). \(\mathrm {SDT}\) can be polynomially simulated by the proof system \(\mathrm {SR}\text {-}\mathrm {I}\) introduced by Krishnamurthy [7]; \(\mathrm {SR}\text {-}\mathrm {I}\) extends Resolution with the symmetry rule. We show that there are polynomial-size proofs of the functional pigeonhole principle (\(\mathrm {FPHP}_n^{n+1}\)) and of an encoding of the clique coloring principle (\(\mathrm {CLIQUE}\text {-}\mathrm {COLORING}_{n,k}\)). On the other hand we show that any \(\mathrm {SDT}\) for the pigeonhole principle (\(\mathrm {PHP}_n^{n+1}\)) has size \(2^{\varOmega \left( n^{1/3-o(1)}\right) }\) despite that \(\mathrm {PHP}_n^{n+1}\) has a lot of symmetries. In 1999 Urquhart [11] showed that \(\mathrm {PHP}_n^{n+1}\) has a polynomial-size \(\mathrm {SR}\text {-}\mathrm {I}\) refutation. Thus \(\mathrm {SDT}\) is strictly weaker than \(\mathrm {SR}\text {-}\mathrm {I}\). The smallest decision tree for \(\mathrm {PHP}_n^{n+1}\) has size \(2^{\varOmega (n \log n)}\); we show that there exists an \(\mathrm {SDT}\) for \(\mathrm {PHP}_n^{n+1}\) of size \(2^{O(\sqrt{n})}\).

Artur Riazanov

On Emptiness and Membership Problems for Set Automata

Abstract

We consider a computational model which is known as set automata.

The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3].

In this paper we characterize algorithmic complexity of the emptiness and membership problems for set automata. More definitely, we prove that both problems are \({\mathbf {PSPACE}}\)-complete for both kinds of set automata.

A. Rubtsov, M. Vyalyi

On Strong NP-Completeness of Rational Problems

Abstract

The computational complexity of the partition, 0-1 subset sum, unbounded subset sum, 0-1 knapsack and unbounded knapsack problems and their multiple variants were studied in numerous papers in the past where all the weights and profits were assumed to be integers. We re-examine here the computational complexity of all these problems in the setting where the weights and profits are allowed to be any rational numbers. We show that all of these problems in this setting become strongly NP-complete and, as a result, no pseudo-polynomial algorithm can exist for solving them unless P = NP. Despite this result we show that they all still admit a fully polynomial-time approximation scheme.

Dominik Wojtczak

A New Algorithm for Finding Closest Pair of Vectors (Extended Abstract)

Abstract

Given n vectors \(x_0, x_1, \ldots , x_{n-1}\) in \(\{0,1\}^{m}\), how to find two vectors whose pairwise Hamming distance is minimum? This problem is known as the Closest Pair Problem. If these vectors are generated uniformly at random except two of them are correlated with Pearson-correlation coefficient \(\rho \), then the problem is called the Light Bulb Problem. In this work, we propose a novel coding-based scheme for the Close Pair Problem. We design both randomized and deterministic algorithms, which achieve the best known running time when the minimum distance is very small compared to the length of input vectors. When applied to the Light Bulb Problem, our algorithms yields state-of-the-art deterministic running time when the Pearson-correlation coefficient \(\rho \) is very large.

Ning Xie, Shuai Xu, Yekun Xu

Backmatter