Theory and Applications of Models of Computation

Frontmatter

On Learning Families of Ideals in Lattices and Boolean Algebras

Abstract

The paper studies learnability from positive data for families of ideals in lattices and Boolean algebras. We established some connections between learnability and algebraic properties of the underlying structures. We prove that for a computable lattice L, the family of all its ideals is \(\textbf{BC}\)-learnable (i.e., learnable w.r.t. semantical convergence) if and only if each ideal of L is principal. In addition, \(\textbf{BC}\)-learnability for the family of all ideals is equivalent to \(\textbf{Ex}\)-learnability (learnability w.r.t. syntactic convergence).

In general, learnability depends on the choice of a computable isomorphic copy of L. Indeed, we show that for every infinite, computable atomic Boolean algebra B, there exist computable algebras A and C isomorphic to B such that the family of all computably enumerable ideals in A is \(\textbf{BC}\)-learnable, while the family of all computably enumerable ideals in C is not \(\textbf{BC}\)-learnable. Finally, we obtain a reverse-mathematical result about conservative \(\textbf{Ex}\)-learning for ideals.

Nikolay Bazhenov, Manat Mustafa

Unambiguous and Co-nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters

Abstract

Nonuniform families of polynomial-size finite automata and pushdown automata respectively have strong connections to nonuniform-NL and nonuniform-LOGCFL. We examine the behaviors of unambiguous and co-nondeterministic computations produced by such families of automata operating multiple counters. As its consequences, we obtain various collapses of the complexity classes of families of promise problems solvable by finite and pushdown automata families when all valid instances are limited to either polynomially long strings or unary strings. A key technical ingredient of our proofs is an inductive counting of reachable vertices of each computation graph of finite and pushdown automata that operate multiple counters simultaneously.

Tomoyuki Yamakami

A Gray Code of Ordered Trees

Abstract

A combinatorial Gray code for a set of combinatorial objects is a sequence of all combinatorial objects in the set so that each object is derived from the preceding object by changing a small part.

In this paper we design a Gray code for ordered trees with n vertices such that each ordered tree is derived from the preceding ordered tree by removing a leaf then appending a leaf elsewhere. Thus, the change is just remove-and-append a leaf, which is of minimum size.

Shin-ichi Nakano

Mechanism Design with Predictions for Facility Location Games with Candidate Locations

Abstract

We study mechanism design with predictions in the single (obnoxious) facility location games with candidate locations on the real line, which complements the existing literature on mechanism design with predictions. We first consider the single facility location games with candidate locations, where each agent prefers the facility (e.g., a school) to be located as close to her as possible. We study two social objectives: minimizing the maximum cost and the social cost, and provide deterministic, anonymous, and group strategy-proof mechanisms with predictions that achieve good trade-offs between consistency and robustness, respectively. Furthermore, we represent the approximation ratio as a function of the prediction error, indicating that mechanisms can achieve better performance even when predictions are not fully accurate. We also consider the single obnoxious facility location games with candidate locations, where each agent prefers the facility (e.g., a garbage transfer station) to be located as far away from her as possible. For the objective of maximizing the minimum utility, we show that any strategy-proof mechanism with predictions is unbounded robust. For the objective of maximizing the social utility, we provide a deterministic, anonymous, and group strategy-proof mechanism with prediction that achieves a good trade-off between consistency and robustness.

Jiazhu Fang, Qizhi Fang, Wenjing Liu, Qingqin Nong

An Improved Approximation Algorithm for Metric Triangle Packing

Abstract

Given an edge-weighted metric complete graph with n vertices, the maximum weight metric triangle packing problem is to find a set of n/3 vertex-disjoint triangles with the total weight of all triangles in the packing maximized. Several simple methods can lead to a 2/3-approximation ratio. However, this barrier is not easy to break. Chen et al. proposed a randomized approximation algorithm with an expected ratio of \((0.66768-\varepsilon )\) for any constant \(\varepsilon >0\). In this paper, we improve the approximation ratio to \((0.66835-\varepsilon )\). Furthermore, we can derandomize our algorithm.

Jingyang Zhao, Mingyu Xiao

An Optimal and Practical Algorithm for the Planar 2-Center Problem

Abstract

The 2-center problem for a set S of n points in the plane asks for two congruent circular disks of the minimum radius \(r^{*}\), whose union covers all points of S. We present an optimal algorithm for computing \(r^{*}\), with \(O(n \log n)\) running time and O(n) space. Our result improves upon the previously known \(O(n \log ^2 n)\) time algorithm, and solves a long-standing (near-thirty years) open problem. Also, we present \(O(n \log n)\) time and O(n) space algorithms for its two variants: The first is to cover a set of points in convex position, and the second is to cover a convex polygon P, whose goal is to find two centers inside P such that the maximum distance from any point of polygon P to its closest center is minimized. Except for efficiency, the other novelty of our algorithms is simplicity: they are built on the standard algorithms for computing the Delaunay triangulation and furthest-site Voronoi diagram of a point set.

Xuehou Tan

Endogenous Threshold Selection with Two-Interval Restricted Tests

Abstract

We continue to study the endogenous threshold selection game. Two firms have interchangeable products with qualities that are drawn i.i.d. from a common prior. A principal wants to minimize the probability of selecting the product of lower quality by offering a set of threshold tests. The threshold test is that given a threshold, the product can be estimated whether its quality exceeds the threshold. Two firms pick the threshold endogenously to maximize the probability of being chosen by the principal.

We consider the scenario where the principal restricts threshold tests to be two-interval. We further characterize properties of Bayes-Nash equilibrium between two firms. Numerically, the minimum probability of incorrect selection is 0.22096 where threshold tests are supported on \([0,0.19]\cup [0.33,0.79]\). Moreover, our exploration aids in offering valuable insights into signaling games with one receiver and two senders.

Zeyu Ren, Yan Liu

An Improved Kernel and Parameterized Algorithm for Almost Induced Matching

Abstract

An induced subgraph is called an induced matching if each vertex is a degree-1 vertex in the subgraph. The Almost Induced Matching problem asks whether we can delete at most k vertices from the input graph such that the remaining graph is an induced matching. This paper studies parameterized algorithms for this problem by taking the size k of the deletion set as the parameter. First, we prove a 6k-vertex kernel for this problem, improving the previous result of 7k. Second, we give an \(O^*(1.6765^k)\)-time and polynomial-space algorithm, improving the previous running-time bound of \(O^*(1.7485^k)\).

Yuxi Liu, Mingyu Xiao

A Tight Threshold Bound for Search Trees with 2-Way Comparisons

Abstract

We study search trees with 2-way comparisons (2wcst ’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3wcst ’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: \(\lambda ^-\) is the largest ratio that forces the less-than test, and \(\lambda ^+\) is the smallest ratio that forces the equal-to test. They determined that \(\lambda ^-= \tfrac{1}{4}\), but for the higher threshold they only showed that \(\lambda ^+\in [\tfrac{3}{7},\tfrac{4}{9}]\). We give the tight bound for the higher threshold, by proving that in fact \(\lambda ^+= \tfrac{3}{7}\).

Sunny Atalig, Marek Chrobak

Kleene Theorems for Lasso Languages and -Languages

Abstract

Automata operating on pairs of words were introduced as an alternative way of capturing acceptance of regular \(\omega \)-languages. Families of DFAs and lasso automata operating on such pairs were defined subsequently, giving rise to minimisation algorithms, a Myhill-Nerode theorem and language learning algorithms. Yet Kleene theorems for these well-studied classes are still missing. We introduce rational lasso languages and expressions, show a Kleene theorem for lasso languages and explore the connection between rational lasso and \(\omega \)-expressions, which yields a Kleene theorem for \(\omega \)-languages and saturated lasso automata. For one direction of the Kleene theorems, we also provide a Brzozowski construction for lasso automata from rational lasso expressions.

Mike Cruchten

Tight Double Exponential Lower Bounds

Abstract

The majority of established algorithms have polynomial, exponential, or factorial runtime complexities. Examples of problems that admit tight double or even triple exponential bounds on computational complexity are relatively rare. The Choosability problem is one such example. For this problem, Marx and Mitsou [ICALP 2016] presented a quite sophisticated proof that shows there is no \(\mathcal {O}(2^{2^{o(tw)}})n^{O(1)}\) time algorithm parameterized by treewidth tw, assuming ETH. In our paper, we show how we almost immediately come to the same conclusion knowing the reduction from \(\forall \exists \)-TQBF to the Choosability problem. Besides, in some sense, we provide a factory that produces problems with tight double exponential lower bounds not only in terms of treewidth but also pathwidth, cutwidth, and bandwidth. It was suspected that the \(\Pi ^\textrm{P}_2\)-complete or \(\Sigma ^\textrm{P}_2\)-complete problems require a double exponential time algorithm in terms of treewidth. However, in our paper, we provide a counterexample to this statement.

Ivan Bliznets, Markus Hecher

Source-Oblivious Broadcast

Abstract

This paper revisits the study of (minimum) broadcast graphs, i.e., graphs enabling fast information dissemination from every source node to all the other nodes (and having minimum number of edges for this property). This study is performed in the framework of compact distributed data structures, that is, when the broadcast protocols are bounded to be encoded at each node as an ordered list of neighbors specifying, upon reception of a message, in which order this message must be passed to these neighbors. We show that this constraint does not limit the power of broadcast protocols, as far as the design of (minimum) broadcast graphs is concerned. Specifically, we show that, for every n, there are n-node graphs for which it is possible to design protocols encoded by lists yet enabling broadcast in \(\lceil \log _2n\rceil \) rounds from every source, which is optimal even for general (i.e., non space-constrained) broadcast protocols. Moreover, we show that, for every n, there exist such graphs with the additional property that they are asymptotically as sparse as the sparsest graphs for which \(\lceil \log _2n\rceil \)-round broadcast protocols exist, up to a constant multiplicative factor. Concretely, these graphs have \(O(n\cdot L(n))\) edges, where L(n) is the number of leading 1 s in the binary representation of \(n-1\), and general minimum broadcast graphs are known to have \(\varOmega (n\cdot L(n))\) edges.

Pierre Fraigniaud, Hovhannes A. Harutyunyan

On the 3-Tree Core of Plane Graphs

Abstract

Plane 3-trees have been well studied in graph drawing literature. For many graph drawing styles, the aesthetic qualities that have been achieved for plane 3-trees are much better than the ones known for general plane graphs. This motivates us to investigate whether one can find a large plane 3-tree type structure in a general plane graph, and if so, whether it can be leveraged to obtain a better drawing for the graph. We thus introduce the concept of a 3-tree core H of a 3-connected plane graph G. Here, H is an edge-labeled plane 3-tree that represents G, and the distance d between H and G is the number of vertices of G that are missing in H. As an application of this concept, we consider the planar ortho-path visibility drawing, where each vertex is drawn as an orthogonal polygonal chain on an integer grid and each edge is drawn as an orthogonal line segment between the paths corresponding to its end vertices. We show that if H has a flat visibility drawing (i.e., each ortho-path is a horizontal line segment) with height k, then G has an ortho-path visibility drawing with height \(O(k2^d)\). In particular, if G is a planar triangulation with \(d=O(1)\), then G can be drawn with height \(4n/9+O(1)\) by choosing an appropriate planar embedding. This bound is significantly smaller than the \(2n/3+O(1)\) lower bound for the ortho-path visibility drawing when one must respect the input embedding.

Debajyoti Mondal, Md. Saidur Rahman

A Coq-Based Infrastructure for Quantum Programming, Verification and Simulation

Abstract

Quantum programming presents a significant departure from traditional programming due to its non-intuitive algorithm design and reliance on intricate linear algebraic derivations. Therefore, formal verification using theorem provers is essential and highly suitable for quantum programming. The mathematical foundation of quantum computing lies in matrix and vector computation. Hence, establishing a proper formal theory of matrices and vectors within theorem provers becomes of utmost significance. This paper expands and refines a Coq-based type system tailored for quantum computing, focusing specifically on powers-of-2 matrices and vectors. This enables precise descriptions of quantum states and operations while facilitating the formal verification of quantum programs. By utilizing this type system, we offer an environment for writing and verifying quantum programs. The verified programs can be extracted as equivalent OCaml files and executable simulators. Our work provides an effective infrastructure for quantum programming, verification and simulation, thereby laying a foundation for future developments.

Wenxuan Tao, Gang Chen

A Local Search Algorithm for Radius-Constrained k-Median

Abstract

Given a set X of n points in a metric space and a radius R, we consider the combining version of k-center and k-median which is with the same objective as k-median, but with the constraint that any x in X is assigned to a center within the range R. In this paper, we propose a bicriteria approximation algorithm achieving a bicriteria approximation ratio of \((3+\varepsilon , 7)\), by incorporating local search with the technology of finding key balls with consequent center exchanges therein. Compared to the state-of-the-art approximation ratio of (8, 4) that is based on an LP formulation for k-median, we improve the ratio of the total distance from 8 to \(3+\varepsilon \) at the price of compromising the ratio of radius from 4 to 7.

Gaojie Chi, Longkun Guo

Energy and Output Patterns in Boolean Circuits

Abstract

Consider a Boolean circuit over a basis \(\{ \wedge , \vee , \lnot \}\), where \(\wedge \) and \(\vee \) are the conjunction of unbounded fan-in and disjunction of unbounded fan-in, respectively, and \(\lnot \) is the negation. The energy complexity of a circuit is defined as the number of gates outputting ones in the circuit, where the maximum is taken over all the input assignments.

We prove that the number of output patterns (the set of possible outputs of all the internal gates in the circuit) in a circuit of energy e is at most \(2^{e \log e + 4e}\) vastly improving the trivial bound of \({s \atopwithdelims ()e}\) where s is the size of the circuit. Building on this tool, we prove the following:

• Any Boolean circuit C of energy e can be converted to a depth-3 circuit of size \(s2^{e\log e + 4e}\). This implies a strong limitation on computational power of energy-bounded circuits even if the circuit is allowed to use unbounded fan-in.
• The problem of counting output patterns of a given circuit is known to be \(\#\textrm{P}\)-complete in general, but is fixed-parameter tractable when parameterized by energy e (over the basis \(\mathcal {B}_2 = \{\wedge _2,\vee _2,\lnot \}\)). We also show further applications of this algorithm.
• If a function \(f:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}\) is computed by a circuit of energy e, then, the unbounded-error communication complexity U(f) is at most \(O(e \log e)\). In particular, this implies that any circuit computing \(\textrm{IP}_n\) has energy \(\textrm{exp}^{W(\varOmega (n))}\), where W denotes the product logarithm. This improves the lower bound of \(\varOmega (\sqrt{n})\) that follows from the relation between energy complexity and decision tree height of a function.

Jayalal Sarma, Kei Uchizawa

Approximation Algorithms for Robust Clustering Problems Using Local Search Techniques

Abstract

In this paper, we explore two robust models for the k-median and k-means problems: the outlier-version (k-MedO/k-MeaO) and the penalty-version (k-MedP/k-MeaP), enabling the marking and elimination of certain points as outliers. In k-MedO/k-MeaO, the count of outliers is restricted by a specified integer, while in k-MedP/k-MeaP, there’s no explicit limit on outlier quantity, yet each outlier incurs a penalty cost.

We introduce a novel approach to evaluate the approximation ratio of local search algorithms for these problems. This involves an adapted clustering method that captures pertinent information about outliers within both local and global optimal solutions. For k-MeaP, we enhance the best-known approximation ratio derived from local search, elevating it from \(25+\varepsilon \) to \(9+\varepsilon \). The best-known approximation ratio for k-MedP is also obtained.

Regarding k-MedO/k-MeaO, only two bi-criteria approximation algorithms based on local search exist. One violates the outlier constraint (limiting outlier count), while the other breaches the cardinality constraint (restricting the number of clusters). We focus on the former algorithm, enhancing its approximation ratios from \(17+\varepsilon \) to \(3+\varepsilon \) for k-MedO and from \(274+\varepsilon \) to \(9+\varepsilon \) for k-MeaO.

Chenchen Wu, Rolf H. Möhring, Yishui Wang, Dachuan Xu, Dongmei Zhang

On the Power of Counting the Total Number of Computation Paths of NPTMs

Abstract

In this paper, we define and study variants of several complexity classes of decision problems that are defined via some criteria on the number of accepting paths of an NPTM. In these variants, we modify the acceptance criteria so that they concern the total number of computation paths, instead of the number of accepting ones. This direction reflects the relationship between the counting classes \(\#\textsf{P}\) and \(\textsf{TotP}\), which are the classes of functions that count the number of accepting paths and the total number of paths of NPTMs, respectively. The former is the well-studied class of counting versions of \(\textsf{NP}\) problems, introduced by Valiant (1979). The latter contains all self-reducible counting problems in \(\#\textsf{P}\) whose decision version is in \(\textsf{P}\), among them prominent \(\#\textsf{P}\)-complete problems such as Non-negative Permanent, #PerfMatch and #DNF-Sat.

We show that almost all classes introduced in this work coincide with their ‘# accepting paths’-definable counterparts, thus providing an alternative model of computation for the classes \(\mathsf {\oplus P}\), \(\mathsf {Mod_k P}\), \(\textsf{SPP}\), \(\textsf{WPP}\), \(\mathsf {C_=P}\), and \(\textsf{PP}\). Moreover, for each of these classes, we present a novel family of complete problems which are defined via problems that are \(\textsf{TotP}\)-complete under parsimonious reductions. This way, we show that all the aforementioned classes have complete problems that are defined via counting problems whose existence version is in \(\textsf{P}\), in contrast to the standard way of obtaining completeness results via counting versions of \(\textsf{NP}\)-complete problems. To the best of our knowledge, prior to this work, such results were known only for \(\mathsf {\oplus P}\) and \(\mathsf {C_=P}\).

We also build upon a result by Curticapean, to exhibit yet another way to obtain complete problems for \(\textsf{WPP}\) and \(\textsf{PP}\), namely via the difference of values of the \(\textsf{TotP}\) function #PerfMatch on pairs of graphs. Finally, for the so defined \(\textsf{WPP}\)-complete problem, we provide an exponential lower bound under the randomized Exponential Time Hypothesis, showcasing the hardness of the class.

Eleni Bakali, Aggeliki Chalki, Sotiris Kanellopoulos, Aris Pagourtzis, Stathis Zachos

The Parameterized Complexity of Maximum Betweenness Centrality

Abstract

Arguably, one of the most central tasks in the area of social network analysis is to identify important members and communities of a given network. The importance of an agent is traditionally measured using some well-defined notion of centrality. In this work, we focus on betweenness centrality, which is based on the number of shortest paths that an agent intersects. This measure can be naturally generalized from a single agent to a group of agents.

Specifically, we study the computation complexity of the \(k\)-Maximum Betweenness Centrality problem, which consists in finding a group of size k whose betweenness centrality exceeds a given threshold. Since this problem is NP-complete in general, we use the framework of parameterized complexity to reveal at least some tractable fragments. From this perspective, we show that the problem is W[1]-hard and in XP when parameterized by the group size k. As the threshold value is not a useful parameter in this context, we focus on the structural restrictions of the underlying social network. In this direction, we show that the problem admits FPT algorithms with respect to the vertex cover number, the distance to clique, or the twin-cover number and the group size combined.

Šimon Schierreich, José Gaspar Smutný

Offensive Alliances in Signed Graphs

Abstract

Signed graphs have been introduced to enrich graph structures expressing relationships between persons or general social entities, introducing edge signs to reflect the nature of the relationship, e.g., friendship or enmity. Independently, offensive alliances have been defined and studied for undirected, unsigned graphs. We join both lines of research and define offensive alliances in signed graphs, hence considering the nature of relationships. Apart from some combinatorial results, mainly on k-balanced and k-anti-balanced signed graphs (a newly introduced family of signed graphs), we focus on the algorithmic complexity of finding smallest offensive alliances, looking at a number of parameterizations. While the parameter solution size leads to an FPT result for unsigned graphs, we obtain \(\textsf {W}[2]\)-completeness for the signed setting. We introduce new parameters for signed graphs, e.g., distance to weakly balanced signed graphs, that could be of independent interest. We show that these parameters yield FPT results. Here, we make use of the recently introduced parameter neighborhood diversity for signed graphs.

Zhidan Feng, Henning Fernau, Kevin Mann, Xingqin Qi

Quantum Path Parallelism: A Circuit-Based Approach to Text Searching

Abstract

Text searching problems are fundamental problems in computer science whose applications are found in a variety of fields. The string matching problem is the common framework for the class of text searching problems where the objective is to find all, possibly approximate, occurrences of a given pattern of length m within a larger text of length n. In this paper, we present the quantum path parallelism approach, a general strategy based on quantum computation that can be easily adapted to a variety of nonstandard text searching problems. Our method translates a text searching problem to an automata-based string recognition problem, associating each possible approximation of the pattern with a different path accepted by the automaton. Under favourable conditions, our proposed method solves the approximate search problem in \(\mathcal {O}(\sqrt{nm}\log ^2(n))\) time, offering a quadratic speed-up over classical solutions. In other cases such speed-up is achieved only for short patterns, i.e. assuming \(m=\mathcal {O}(\log (n))\). As a demonstration of the flexibility of our method, we show how it can be adapted for solving some approximate string matching problems, obtaining a significant quantum advantage.

Simone Faro, Arianna Pavone, Caterina Viola

Space-Efficient Graph Kernelizations

Abstract

Let n be the size of a parameterized problem and k the parameter. We present kernels for Feedback Vertex Set and Path Contraction whose sizes are all polynomial in k and that are computable in polynomial time and with \(O({{\,\textrm{poly}\,}}(k) \log n)\) bits (of working memory). By using kernel cascades, we obtain the best known kernels in polynomial time with \(O({{\,\textrm{poly}\,}}(k) \log n)\) bits.

Frank Kammer, Andrej Sajenko

Counting on Rainbow k-Connections

Abstract

For an undirected graph imbued with an edge coloring, a rainbow path (resp. proper path) between a pair of vertices corresponds to a simple path in which no two edges (resp. no two adjacent edges) are of the same color. In this context, we refer to such an edge coloring as a rainbow k-connected w-coloring (resp. k-proper connected w-coloring) if at most w colors are used to ensure the existence of at least k internally vertex disjoint rainbow paths (resp. k internally vertex disjoint proper paths) between all pairs of vertices. At present, while there have been extensive efforts to characterize the complexity of finding rainbow 1-connected colorings, we remark that very little appears to known for cases where \(k \in \mathbb {N}_{>1}\).

In this work, in part answering a question of (Ducoffe et al.; Discrete Appl. Math. 281; 2020), we first show that the problems of counting rainbow k-connected w-colorings and counting k-proper connected w-colorings are both linear time treewidth Fixed Parameter Tractable (FPT) for every \(\left( k,w\right) \in \mathbb {N}_{>0}^2\). Subsequently, and in the other direction, we extend prior NP-completeness results for deciding the existence of a rainbow 1-connected w-coloring for every \(w \in \mathbb {N}_{>1}\), in particular, showing that the problem remains NP-complete for every \(\left( k,w\right) \in \mathbb {N}_{>0} \times \mathbb {N}_{>1}\). This yields as a corollary that no Fully Polynomial-time Randomized Approximation Scheme (FPRAS) can exist for approximately counting such colorings in any of these cases (unless \(NP = RP\)). Next, concerning counting hardness, we give the first \(\#P\)-completeness result we are aware of for rainbow connected colorings, proving that counting rainbow k-connected 2-colorings is \(\#P\)-complete for every \(k \in \mathbb {N}_{>0}\).

Robert D. Barish, Tetsuo Shibuya

Some Combinatorial Algorithms on the Edge Cover Number of k-Regular Connected Hypergraphs

Abstract

For \(k\ge 3\), let H be a k-regular connected hypergraph on n vertices and m edges. The edge cover number \(\rho (H)\) is the minimum number of edges that intersect every vertex. We prove the following inequality: \(\rho (H)\le \frac{(k-1)n+1}{k}\). Furthermore, the extremal hypergraphs with equality holds are exactly k-star hypertrees. Based on the proofs, some combinatorial algorithms on the edge cover number are designed.

Zhongzheng Tang, Yaxuan Li, Zhuo Diao

Time Efficient Implementation for Online K-Server Problem on Trees

Abstract

We consider online algorithms for the k-server problem on trees of size n. Chrobak and Larmore proposed a k-competitive algorithm for this problem that has the optimal competitive ratio. However, the existing implementations have \(O\left( k^2 + k\cdot \log n\right) \) or \(O\left( k(\log n)^2\right) \) time complexity for processing a query, where n is the number of nodes. We propose a new time-efficient implementation of this algorithm that has O(n) time complexity for preprocessing and \(O\left( k\log k\right) \) time for processing a query. The new algorithm is faster than both existing algorithms and the time complexity for query processing does not depend on the tree size.

Kamil Khadiev, Maxim Yagafarov

Improved Approximation Algorithm for the Distributed Lower-Bounded k-Center Problem

Abstract

Clustering large data is a fundamental task with widespread applications. The distributed computation methods have received greatly attention in recent years due to the increasing size of data. In this paper, we consider a variant of the widely used k-center problem, i.e., the lower-bounded k-center problem, and study the lower-bounded k-center problem in the Massively Parallel Computation (MPC) model. The lower-bounded k-center problem takes as input a set C of points in a metric space, the desired number k of centers, and a lower bound L. The goal is to partition the set C into at most k clusters such that the number of points in each cluster is at least L, and the k-center clustering objective is minimized. The current best result for the above problem in the MPC model is 16-approximation algorithm with 4 rounds. In this paper, we obtain a 2-round \((7+\epsilon )\)-approximation algorithm for this problem in the MPC model.

Ting Liang, Qilong Feng, Xiaoliang Wu, Jinhui Xu, Jianxin Wang

Parameterized Complexity of Weighted Target Set Selection

Abstract

Consider a graph G where each vertex has a threshold. A vertex v in G is activated if the number of active vertices adjacent to v is at least as many as its threshold. A vertex subset \(A_{0}\) of G is a target set if eventually all vertices in G are activated by initially activating vertices of \(A_{0}\). The Target Set Selection problem (TSS) involves finding the smallest target set of G with vertex thresholds. This problem has already been extensively studied and is known to be NP-hard even for very restricted conditions. In this paper, we analyze TSS and its weighted variant, called the Weighted Target Set Selection problem (WTSS) from the perspective of parameterized complexity. Let k be the solution size and \(\ell \) be the maximum threshold. We first show that TSS is W[1]-hard for split graphs when parameterized by \(k + \ell \), and W[2]-hard for cographs when parameterized by k. We also prove that WTSS is W[2]-hard for trivially perfect graphs when parameterized by k. On the other hand, we show that WTSS can be solved in \(O(n \log n)\) time for complete graphs. Additionally, we design FPT algorithms for WTSS when parameterized by \(\textsf{nd}+\ell \), \(\textsf{tw}+\ell \), \(\textsf{ce}\), and \(\textsf{vc}\), where \(\textsf{nd}\) is the neighborhood diversity, \(\textsf{tw}\) is the treewidth, \(\textsf{ce}\) is the cluster editing number, and \(\textsf{vc}\) is the vertex cover number of the input graph.

Takahiro Suzuki, Kei Kimura, Akira Suzuki, Yuma Tamura, Xiao Zhou

Mechanism Design for Building Optimal Bridges Between Regions

Abstract

We study the bridge-building problem from the mechanism design perspective. In this problem, a social planner is tasked with building a bridge to connect two regions separated by an obstacle (e.g., a river or valley). Each agent in a region has a private location and is interested in traveling to a facility (e.g., a transportation hub) in the other region. The cost of an agent with respect to a bridge is the distance from their location to the facility of interest via the bridge. Our goal is to design strategy-proof mechanisms that elicit truthful locations from the agents and approximately optimize an objective by determining a location for building a bridge. We consider the social cost and maximum cost objectives, which are the total cost and maximum cost of agents, respectively. For the social cost objective, we characterize an optimal solution and show that it is strategy-proof. For the maximum cost objective, any optimal solution is no longer strategy-proof. We present deterministic \(\frac{5}{3}\)-approximation and randomized \(\frac{3}{2}\)-approximation strategy-proof mechanisms. We complement the results by providing tight lower bounds.

Zining Qin, Hau Chan, Chenhao Wang, Ying Zhang

Joint Bidding in Ad Auctions

Abstract

In traditional advertising auctions, commodity suppliers as advertisers compete for adverting positions to display commodities. As e-commerce platforms become more prevalent, offline retailers are also opening online virtual shops, and retailers are starting to charge a fee for extra exposure of their shops. This has led to situations where a single commodity may be sponsored by both the retailer and the supplier, offering opportunities for more profit. In order to explore this novel advertising pattern, we propose a new model called the joint advertising system (JAS), where retailers and suppliers jointly bid for advertising positions. In the context of this realistic scenario, conventional mechanisms such as GFP, GSP and Myerson auction cannot be applied directly. Besides, the VCG mechanism results in negative revenue in JAS. To solve this issue, we modify the payment rule of VCG to create a revised VCG mechanism that guarantees incentive compatibility, individual rationality and weak budget-balance. Additionally, we leverage the structure of the affine maximizer auction (AMA) and technique of automated mechanism design to train joint AMA. Finally, we conduct several experiments to demonstrate the performance of the joint AMA. It turns out that our mechanism maintains good economic properties and outperforms other mechanisms in various settings.

Yuchao Ma, Weian Li, Wanzhi Zhang, Yahui Lei, Zhicheng Zhang, Qi Qi, Qiang Liu, Xingxing Wang

Lower Bounds for the Sum of Small-Size Algebraic Branching Programs

Abstract

We observe that proving strong enough lower bounds for the sum of set-multilinear Algebraic Branching Programs (smABPs) in the low-degree regime implies Valiant’s conjecture (i.e. it implies general ABP lower bounds). Using this connection, we obtain lower bounds for the sum of small-sized general ABPs. In particular, we show that the sum of \({{\,\textrm{poly}\,}}(n)\) ABPs, each of size (\({:}{=}\) number of vertices) \((nd)^{o(1)}\), cannot compute the family of Iterated Matrix Multiplication polynomials \(\textrm{IMM}_{n,d}\) for any arbitrary function \(d=d(n)\).

We also give a dual version of our result for the sum of low-variate ROABPs (read-once oblivious ABPs) and read-k oblivious ABPs. Both smABP and ROABP are very well-studied ‘simple’ models; our work puts them at the forefront of understanding Valiant’s conjecture.

C. S. Bhargav, Prateek Dwivedi, Nitin Saxena

Backmatter