Search

The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of $k \ge 1$ agents. While the initial positions of Facilitator's agents are fixed, Divider gets to select the initial positions of his agents. Then, they take turns to move their agents to adjacent vertices (or stay put) with Facilitator's goal to bring both her agents at same vertex and Divider's goal to prevent it. The computational question of interest is to determine if Facilitator has a winning strategy against Divider with $k$ agents. Fomin, Golovach, and Thilikos [WG, 2021] introduced this game and proved that it is PSPACE-hard and co-W[2]-hard parameterized by the number of agents. This hardness naturally motivates the structural parameterization of the problem. The authors proved that it admits an FPT algorithm when parameterized by the modular width and the number of allowed rounds. However, they left open the complexity of the problem from the perspective of other structural parameters. In particular, they explicitly asked whether the problem admits an FPT or XP-algorithm with respect to the treewidth of the input graph. We answer this question in the negative and show that Rendezvous is co-NP-hard even for graphs of constant treewidth. Further, we show that the problem is co-W[1]-hard when parameterized by the feedback vertex set number and the number of agents, and is unlikely to admit a polynomial kernel when parameterized by the vertex cover number and the number of agents. Complementing these hardness results, we show that the Rendezvous is FPT when parameterized by both the vertex cover number and the solution size. Finally, for graphs of treewidth at most two and girds, we show that the problem can be solved in polynomial time., Comment: A shorter version of this work has been accepted for presentation at the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2022

Consider a dynamic network and a given distributed problem. At any point in time, there might exist several solutions that are equally good with respect to the problem specification, but that are different from an algorithmic perspective, because some could be easier to update than others when the network changes. In other words, one would prefer to have a solution that is more robust to topological changes in the network; and in this direction the best scenario would be that the solution remains correct despite the dynamic of the network. In [Arnaud Casteigts et al., 2020], the authors introduced a very strong robustness criterion: they required that for any removal of edges that maintain the network connected, the solution remains valid. They focus on the maximal independent set problem, and their approach consists in characterizing the graphs in which there exists a robust solution (the existential problem), or even stronger, where any solution is robust (the universal problem). As the robustness criteria is very demanding, few graphs have a robust solution, and even fewer are such that all of their solutions are robust. In this paper, we ask the following question: Can we have robustness for a larger class of networks, if we bound the number k of edge removals allowed? To answer this question, we consider three classic problems: maximal independent set, minimal dominating set and maximal matching. For the universal problem, the answers for the three cases are surprisingly different. For minimal dominating set, the class does not depend on the number of edges removed. For maximal matching, removing only one edge defines a robust class related to perfect matchings, but for all other bounds k, the class is the same as for an arbitrary number of edge removals. Finally, for maximal independent set, there is a strict hierarchy of classes: the class for the bound k is strictly larger than the class for bound k+1. For the robustness notion of [Arnaud Casteigts et al., 2020], no characterization of the class for the existential problem is known, only a polynomial-time recognition algorithm. We show that the situation is even worse for bounded k: even for k = 1, it is NP-hard to decide whether a graph has a robust maximal independent set., LIPIcs, Vol. 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023), pages 7:1-7:15

Given a class of graphs ℋ, the problem ⊕Sub(ℋ) is defined as follows. The input is a graph H ∈ ℋ together with an arbitrary graph G. The problem is to compute, modulo 2, the number of subgraphs of G that are isomorphic to H. The goal of this research is to determine for which classes ℋ the problem ⊕Sub(ℋ) is fixed-parameter tractable (FPT), i.e., solvable in time f(|H|)⋅|G|^O(1). Curticapean, Dell, and Husfeldt (ESA 2021) conjectured that ⊕Sub(ℋ) is FPT if and only if the class of allowed patterns ℋ is matching splittable, which means that for some fixed B, every H ∈ ℋ can be turned into a matching (a graph in which every vertex has degree at most 1) by removing at most B vertices. Assuming the randomised Exponential Time Hypothesis, we prove their conjecture for (I) all hereditary pattern classes ℋ, and (II) all tree pattern classes, i.e., all classes ℋ such that every H ∈ ℋ is a tree. We also establish almost tight fine-grained upper and lower bounds for the case of hereditary patterns (I)., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 68:1-68:17

LIPIcs, Volume 259, CPM 2023, Complete Volume, LIPIcs, Vol. 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023), pages 1-472

In 1926, Levi showed that, for every pseudoline arrangement $\mathcal{A}$ and two points in the plane, $\mathcal{A}$ can be extended by a pseudoline which contains the two prescribed points. Later extendability was studied for arrangements of pseudohyperplanes in higher dimensions. While the extendability of an arrangement of proper hyperplanes in $\mathbb{R}^d$ with a hyperplane containing $d$ prescribed points is trivial, Richter-Gebert found an arrangement of pseudoplanes in $\mathbb{R}^3$ which cannot be extended with a pseudoplane containing two particular prescribed points. In this article, we investigate the extendability of signotopes, which are a combinatorial structure encoding a rich subclass of pseudohyperplane arrangements. Our main result is that signotopes of odd rank are extendable in the sense that for two prescribed crossing points we can add an element containing them. Moreover, we conjecture that in all even ranks $r \geq 4$ there exist signotopes which are not extendable for two prescribed points. Our conjecture is supported by examples in ranks 4, 6, 8, 10, and 12 that were found with a SAT based approach., Comment: Full version of a paper to appear in a shorter form in the 39th International Symposium on Computational Geometry (SoCG 2023)

We consider prophet inequalities subject to feasibility constraints that are the intersection of q matroids. The best-known algorithms achieve a Θ(q)-approximation, even when restricted to instances that are the intersection of q partition matroids, and with i.i.d. Bernoulli random variables [José R. Correa et al., 2022; Moran Feldman et al., 2016; Marek Adamczyk and Michal Wlodarczyk, 2018]. The previous best-known lower bound is Θ(√q) due to a simple construction of [Robert Kleinberg and S. Matthew Weinberg, 2012] (which uses i.i.d. Bernoulli random variables, and writes the construction as the intersection of partition matroids). We establish an improved lower bound of q^{1/2+Ω(1/log log q)} by writing the construction of [Robert Kleinberg and S. Matthew Weinberg, 2012] as the intersection of asymptotically fewer partition matroids. We accomplish this via an improved upper bound on the product dimension of a graph with p^p disjoint cliques of size p, using recent techniques developed in [Noga Alon and Ryan Alweiss, 2020]., LIPIcs, Vol. 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), pages 95:1-95:20

Front Matter, Table of Contents, Preface, Conference Organization, LIPIcs, Vol. 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023), pages 0:i-0:xvi

It is a longstanding open problem whether there is an algorithm to decide the Positivity Problem for linear recurrence sequences (LRS) over the integers, namely whether given such a sequence, all its terms are non-negative. Decidability is known for LRS of order 5 or less, i.e., for those sequences in which every new term depends linearly on the previous five (or fewer) terms. For simple LRS (i.e., those sequences whose characteristic polynomials have no repeated roots), decidability of Positivity is known up to order 9. In this paper, we focus on the important subclass of reversible LRS, i.e., those integer LRS ⟨u_n⟩_{n=0}^∞ whose bi-infinite completion ⟨u_n⟩_{n=-∞}^∞ also takes exclusively integer values; a typical example is the classical Fibonacci (bi-)sequence ⟨ … , 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, … ⟩. Our main results are that Positivity is decidable for reversible LRS of order 11 or less, and for simple reversible LRS of order 17 or less., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 130:1-130:17

This report documents the program and the outcomes of Dagstuhl Seminar 22482 "Counting and Sampling: Algorithms and Complexity". We document the talks presented, covering many advances in the area made over the last five years. As well, we document the progress made by working groups on future projects., DagRep, Volume 12, Issue 11, pages 124-145

The Skolem Problem asks to determine whether a given integer linear recurrence sequence (LRS) has a zero term. This decision problem arises within a number of different topics in computer science, including loop termination, weighted automata, formal power series, and probabilistic model checking, among many other examples. Decidability of the problem is notoriously open, despite having been the subject of sustained interest over several decades [Halava et al., 2005]. More specifically, the problem is known to be decidable for recurrences of order at most 4 - a result obtained some 40 years ago [Mignotte et al., 1984; Vereshchagin, 1985] - while decidability is open already for recurrences of order 5. In this talk we take a wide-ranging view of the Skolem Problem. We survey its history and context, starting with the theorem of Skolem-Mahler-Lech characterising the set of zeros of a LRS over fields of characteristic zero. Here we explain the non-effective nature of the existing proofs of the theorem. Among modern developments, we overview versions of the Skolem-Mahler-Lech theorem for non-linear recurrences and for fields of non-zero characteristic. We also describe two recent directions of progress toward showing decidability of the Skolem Problem subject to classical number theoretic conjectures. The first new development concerns a recent algorithm [Y. Bilu et al., 2022] that decides the problem on the class of simple LRS (those with simple characteristic roots) subject to two classical conjectures about the exponential function. The algorithm is self-certifying: its output comes with a certificate of correctness that can be checked unconditionally. The two conjectures alluded to above are required for the proof of termination of the algorithm. A second new development concerns the notion of Universal Skolem Set [F. Luca et al., 2022]: a recursive set S of positive integers such that it is decidable whether a given non-degenerate linear recurrence sequence has a zero in S. Decidability of the Skolem Problem is equivalent to the assertion that ℕ is a Universal Skolem Set. In lieu of this one can ask whether there exists a Universal Skolem Set of density one. We will present a recent a construction of a Universal Skolem Set that has positive density unconditionally and has density one subject to the Bateman-Horn conjecture in number theory. The latter is a far-reaching generalisation of Hardy and Littlewood’s twin primes conjecture., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 5:1-5:2

This report documents the program and the outcomes of Dagstuhl Seminar 22301 "Algorithmic Aspects of Information Theory". Constraints on entropies constitute the "laws of information theory". These constraints go well beyond Shannon’s basic information inequalities, as they include not only information inequalities that cannot be derived from Shannon’s basic inequalities, but also conditional inequalities and disjunctive inequalities that are valid for all entropic functions. There is an extensive body of research on constraints on entropies and their applications to different areas of mathematics and computer science. So far, however, little progress has been made on the algorithmic aspects of information theory. In fact, even fundamental questions about the decidability of information inequalities and their variants have remained open to date. Recently, research in different applications has demonstrated a clear need for algorithmic solutions to questions in information theory. These applications include: finding tight upper bounds on the answer to a query on a relational database, the homomorphism domination problem and its uses in query optimization, the conditional independence implication problem, soft constraints in databases, group-theoretic inequalities, and lower bounds on the information ratio in secret sharing. Thus far, the information-theory community has had little interaction with the communities where these applications have been studied or with the computational complexity community. The main goal of this Dagstuhl Seminar was to bring together researchers from the aforementioned communities and to develop an agenda for studying algorithmic aspects of information theory, motivated from a rich set of diverse applications. By using the algorithmic lens to examine the common problems and by transferring techniques from one community to the other, we expected that bridges would be created and some tangible progress on open questions could be made., DagRep, Volume 12, Issue 7, pages 180-204

Motivated by the theory of spin-glasses in physics, we study the so-called reconstruction problem on the tree, and on the sparse random graph G(n,d/n). Both cases reduce naturally to analysing broadcasting models, where each edge has its own broadcasting matrix, and this matrix is drawn independently from a predefined distribution. We establish the reconstruction threshold for the cases where the broadcasting matrices give rise to symmetric, 2-spin Gibbs distributions. This threshold seems to be a natural extension of the well-known Kesten-Stigum bound that manifests in the classic version of the reconstruction problem. Our results determine, as a special case, the reconstruction threshold for the prominent Edwards–Anderson model of spin-glasses, on the tree. Also, we extend our analysis to the setting of the Galton-Watson random tree, and the (sparse) random graph G(n,d/n), where we establish the corresponding thresholds. Interestingly, for the Edwards–Anderson model on the random graph, we show that the replica symmetry breaking phase transition, established by Guerra and and Toninelli in [Guerra and Toninelli, 2004], coincides with the reconstruction threshold. Compared to classical Gibbs distributions, spin-glasses have several unique features. In that respect, their study calls for new ideas, e.g. we introduce novel estimators for the reconstruction problem. The main technical challenge in the analysis of such systems, is the presence of (too) many levels of randomness, which we manage to circumvent by utilising recently proposed tools coming from the analysis of Markov chains., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 55:1-55:14

A covering path for a planar point set is a path drawn in the plane with straight-line edges such that every point lies at a vertex or on an edge of the path. A covering tree is defined analogously. Let $\pi(n)$ be the minimum number such that every set of $n$ points in the plane can be covered by a noncrossing path with at most $\pi(n)$ edges. Let $\tau(n)$ be the analogous number for noncrossing covering trees. Dumitrescu, Gerbner, Keszegh, and T\'oth (Discrete & Computational Geometry, 2014) established the following inequalities: \[\frac{5n}{9} - O(1) < \pi(n) < \left(1-\frac{1}{601080391}\right)n, \quad\text{and} \quad\frac{9n}{17} - O(1) < \tau(n)\leqslant \left\lfloor\frac{5n}{6}\right\rfloor.\] We report the following improved upper bounds: \[\pi(n)\leqslant \left(1-\frac{1}{22}\right)n, \quad\text{and}\quad \tau(n)\leqslant \left\lceil\frac{4n}{5}\right\rceil.\] In the same context we study rainbow polygons. For a set of colored points in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color in its interior or on its boundary. Let $\rho(k)$ be the minimum number such that every $k$-colored point set in the plane admits a perfect rainbow polygon of size $\rho(k)$. Flores-Pe\~naloza, Kano, Mart\'inez-Sandoval, Orden, Tejel, T\'oth, Urrutia, and Vogtenhuber (Discrete Mathematics, 2021) proved that $20k/19 - O(1), Comment: 17 pages, 6 figures, SoCG 2023

We study the single-site Glauber dynamics for the fugacity λ, Hard-Core model on the random graph G(n, d/n). We show that for the typical instances of the random graph G(n,d/n) and for fugacity λ < {d^d} / {(d-1)^(d+1)}, the mixing time of Glauber dynamics is n^{1 + O(1/log log n)}. Our result improves on the recent elegant algorithm in [Bezáková, Galanis, Goldberg and Štefankovič; ICALP'22]. The algorithm there is an MCMC-based sampling algorithm, but it is not the Glauber dynamics. Our algorithm here is simpler, as we use the classic Glauber dynamics. Furthermore, the bounds on mixing time we prove are smaller than those in Bezáková et al. paper, hence our algorithm is also faster. The main challenge in our proof is handling vertices with unbounded degrees. We provide stronger results with regard the spectral independence via branching values and show that the our Gibbs distributions satisfy the approximate tensorisation of the entropy. We conjecture that the bounds we have here are optimal for G(n,d/n). As corollary of our analysis for the Hard-Core model, we also get bounds on the mixing time of the Glauber dynamics for the Monomer-Dimer model on G(n,d/n). The bounds we get for this model are slightly better than those we have for the Hard-Core model, LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 54:1-54:17

We demonstrate some novel links between entropy and description complexity, a notion referring to the minimal formula length for specifying given properties. Let MLU be the logic obtained by extending propositional logic with the universal modality, and let GMLU be the corresponding extension with the ability to count. In the finite, MLU is expressively complete for specifying sets of variable assignments, while GMLU is expressively complete for multisets. We show that for MLU, the model classes with maximal Boltzmann entropy are the ones with maximal description complexity. Concerning GMLU, we show that expected Boltzmann entropy is asymptotically equivalent to expected description complexity multiplied by the number of proposition symbols considered. To contrast these results, we prove that this link breaks when we move to considering first-order logic FO over vocabularies with higher-arity relations. To establish the aforementioned result, we show that almost all finite models require relatively large FO-formulas to define them. Our results relate to links between Kolmogorov complexity and entropy, demonstrating a way to conceive such results in the logic-based scenario where relational structures are classified by formulas of different sizes., LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 38:1-38:18

Parity games have witnessed several new quasi-polynomial algorithms since the breakthrough result of Calude et al. (STOC 2017). The combinatorial object underlying these approaches is a universal tree, as identified by Czerwi\'nski et al. (SODA 2019). By providing a quasi-polynomial lower bound on the size of universal trees, they have highlighted a barrier that must be overcome by all existing approaches to attain polynomial running time. This is due to the existence of worst case instances which force these algorithms to explore a large portion of the tree. As an attempt to overcome this barrier, we propose a strategy iteration framework which can be applied on any universal tree. It is at least as fast as its value iteration counterparts, while allowing one to take bigger leaps in the universal tree. Our main technical contribution is an efficient method for computing the least fixed point of 1-player games. This is achieved via a careful adaptation of shortest path algorithms to the setting of ordered trees. By plugging in the universal tree of Jurdzi\'nski and Lazi\'c (LICS 2017), or the Strahler universal tree of Daviaud et al. (ICALP 2020), we obtain instantiations of the general framework that take time $O(mn^2\log n\log d)$ and $O(mn^2\log^3 n \log d)$ respectively per iteration., Comment: 33 pages, 8 figures

In this paper, we present a novel, polynomial time, algorithm for approximate sampling from symmetric Gibbs distributions on the sparse random graph and hypergraph. The examples of symmetric distributions we consider here include some important distributions on spin-systems and spin-glasses. These are: the q-state antiferromagnetic Potts model for q ≥ 2, including the (hyper)graph Ising model and random colourings. The uniform distribution over the Not-All-Equal solutions of a random k-SAT formula. Finally, we consider sampling from the spin-glass distribution called the k-spin model, i.e., this is the "diluted" version of the well-known Sherrington-Kirkpatrick model. Spin-glasses give rise to very intricate distributions which are also studied in mathematics, in neural computation, computational biology and many other areas. To our knowledge, this is the first rigorously analysed efficient sampling algorithm for spin-glasses which operates in a non trivial range of the parameters of the distribution. We present, what we believe to be, an elegant sampling algorithm. Our algorithm is unique in its approach and does not belong to any of the well-known families of sampling algorithms. We derive it by investigating the power and the limits of the approach that was introduced in [Efthymiou: SODA 2012] and combine it, in a novel way, with powerful notions from the Cavity method. Specifically, for a symmetric Gibbs distribution μ on the random (hyper)graph whose parameters are within an appropriate range, our sampling algorithm has the following properties: with probability 1-o(1) over the instances of the input (hyper)graph, it generates a configuration which is distributed within total variation distance n^{-Ω(1)} from μ. The time complexity is O((nlog n)²), where n is the size of the input (hyper)graph. We make a notable progress regarding impressive predictions of physicists relating phase-transitions of Gibbs distributions with the efficiency of the corresponding sampling algorithms. For most (if not all) the cases we consider here, our algorithm outperforms by far any other sampling algorithms in terms of the permitted range of the parameters of the Gibbs distributions. The use of notions and ideas from the Cavity method provides a new insight to the sampling problem. Our results imply that there is a lot of potential for further exploiting the Cavity method for algorithmic design., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 57:1-57:16

Consider words of length $n$. The set of all periods of a word of length $n$ is a subset of $\{0,1,2,\ldots,n-1\}$. However, any subset of $\{0,1,2,\ldots,n-1\}$ is not necessarily a valid set of periods. In a seminal paper in 1981, Guibas and Odlyzko have proposed to encode the set of periods of a word into an $n$ long binary string, called an autocorrelation, where a one at position $i$ denotes the period $i$. They considered the question of recognizing a valid period set, and also studied the number of valid period sets for length $n$, denoted $\kappa_n$. They conjectured that $\ln(\kappa_n)$ asymptotically converges to a constant times $\ln^2(n)$. If improved lower bounds for $\ln(\kappa_n)/\ln^2(n)$ were proposed in 2001, the question of a tight upper bound has remained opened since Guibas and Odlyzko's paper. Here, we exhibit an upper bound for this fraction, which implies its convergence and closes this long standing conjecture. Moreover, we extend our result to find similar bounds for the number of correlations: a generalization of autocorrelations which encodes the overlaps between two strings., Comment: To appear on the proceedings of ICALP 2023 Version 3: 15 pages, 1 figure, 2 tables, 21 bibliographic references; ICALP 2023 final version; updated related works and bibliographic references; updated Figure 1; typos corrected. version 2: 14 pages, 1 figure, 2 tables, 12 bibliographic references; version 2: added a Related works section with additional references

We study the repeated balls-into-bins process introduced by Becchetti, Clementi, Natale, Pasquale and Posta (2019). This process starts with $m$ balls arbitrarily distributed across $n$ bins. At each round $t=1,2,\ldots$, one ball is selected from each non-empty bin, and then placed it into a bin chosen independently and uniformly at random. We prove the following results: $\quad \bullet$ For any $n \leq m \leq \mathrm{poly}(n)$, we prove a lower bound of $\Omega(m/n \cdot \log n)$ on the maximum load. For the special case $m=n$, this matches the upper bound of $O(\log n)$, as shown in [BCNPP19]. It also provides a positive answer to the conjecture in [BCNPP19] that for $m=n$ the maximum load is $\omega(\log n/ \log \log n)$ at least once in a polynomially large time interval. For $m\in [\omega(n),n\log n]$, our new lower bound disproves the conjecture in [BCNPP19] that the maximum load remains $O(\log n)$. $\quad \bullet$ For any $n\leq m\leq\mathrm{poly}(n)$, we prove an upper bound of $O(m/n\cdot\log n)$ on the maximum load for all steps of a polynomially large time interval. This matches our lower bound up to multiplicative constants. $\quad \bullet$ For any $m\geq n$, our analysis also implies an $O(m^2/n)$ waiting time to reach a configuration with a $O(m/n\cdot\log m)$ maximum load, even for worst-case initial distributions. $\quad \bullet$ For any $m \geq n$, we show that every ball visits every bin in $O(m\log m)$ rounds. For $m = n$, this improves the previous upper bound of $O(n \log^2 n)$ in [BCNPP19]. We also prove that the upper bound is tight up to multiplicative constants for any $n \leq m \leq \mathrm{poly}(n)$., Comment: Full version of STACS 2023 paper; 38 pages, 5 figures

A result due to Burago and Zalgaller states that every orientable polyhedral surface, one that is obtained by gluing Euclidean polygons, has an isometric piecewise linear (PL) embedding into Euclidean space $\mathbb{E}^3$. A flat torus, resulting from the identification of the opposite sides of a Euclidean parallelogram, is a simple example of polyhedral surface. In a first part, we adapt the proof of Burago and Zalgaller, which is partially constructive, to produce PL isometric embeddings of flat tori. In practice, the resulting embeddings have a huge number of vertices, moreover distinct for every flat torus. In a second part, based on another construction of Zalgaller and on recent works by Arnoux et al., we exhibit a universal triangulation with 5974 triangles which can be embedded linearly on each triangle in order to realize the metric of any flat torus., 33 pages, 29 figures

Consider planning a trip in a train network. In contrast to, say, a road network, the edges are temporal, i.e., they are only available at certain times. Another important difficulty is that trains, unfortunately, sometimes get delayed. This is especially bad if it causes one to miss subsequent trains. The best way to prepare against this is to have a connection that is robust to some number of (small) delays. An important factor in determining the robustness of a connection is how far in advance delays are announced. We give polynomial-time algorithms for the two extreme cases: delays known before departure and delays occurring without prior warning (the latter leading to a two-player game scenario). Interestingly, in the latter case, we show that the problem becomes PSPACE-complete if the itinerary is demanded to be a path., LIPIcs, Vol. 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), pages 17:1-17:17

LIPIcs, Volume 242, WABI 2022, Complete Volume, LIPIcs, Vol. 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022), pages 1-474

A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph G, what is the smallest number |λ| of time-labels that we need to add to the edges of G such that the resulting temporal graph (G,λ) is temporally connected? As it turns out, this basic problem, called Minimum Labeling (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem Min. Aged Labeling (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e., maximum label) of the obtained temporal graph (G,λ). Second we consider the problem Min. Steiner Labeling (MSL), where the aim is now to have a temporal path between any pair of "important" vertices which lie in a subset R ⊆ V, which we call the terminals. This relaxed problem resembles the problem Steiner Tree in static (i.e., non-temporal) graphs. However, due to the requirement of strictly increasing labels in a temporal path, Steiner Tree is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely Min. Aged Steiner Labeling (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number |R| of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL remains NP-hard, it is in FPT with respect to the number |R| of terminals. That is, adding the age restriction, makes the above problems strictly harder (unless P=NP or W[1]=FPT)., LIPIcs, Vol. 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), pages 62:1-62:15

Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for {\it bicombining tree-child networks} which are tree-child networks with every reticulation node having exactly two parents. In this paper, we extend these studies to {\it $d$-combining tree-child networks} where every reticulation node has now $d\geq 2$ parents. Moreover, we also give results and conjectures on the distributional behavior of the number of reticulation nodes of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves., Extended abstract which is accepted for presentation at AofA2022; an accompanying Maple worksheet can be found in the ancillary file folder

The integer complexity of a natural number n, denoted by ‖n‖, is the smallest number of 1’s needed to express n using an arbitrary combination of addition and multiplication (and parentheses). For example, ‖6‖ = 5 since the expression 6 = (1+1)⋅ (1+1+1) contains five 1’s and there are no such expressions containing at most four 1’s. The investigation of this cute complexity measure was originated by Mahler and Popken in the 1950s. It is easy to see that ‖n‖/(log₃ n) ∈ [3, 3 log₂ 3] (∼ [3,4.755]) for every n, but the distribution of ‖n‖ is largely unknown. In this work, we focus on the restricted expressions obtained by applying Horner’s schema to a mixed binary-ternary representation of a given number in which we can arrange base-two and base-three digits in an arbitrary order. Let f(n) denote the minimum number of 1’s needed to express n in this way. Apparently, f(n) ≥ ‖n‖ for every n. We extensively investigate on f(n) via the combination of computer experiments and theoretical analysis and obtain the following set of results: (i) Computer experiments supporting the hypothesis that f(n)/log₃ n < 3.483 on average and f(n)/log₃ n < 4.212 for all n, (ii) For almost all natural numbers n, 3.120 < f(n)/log₃ n < 3.587, and (iii) There are infinitely many n’s such that f(n)/log₃ n > 3.934. Several new bounds on the original integer complexity are also presented in the paper., LIPIcs, Vol. 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), pages 29:1-29:16

Temporal graphs have been recently introduced to model changes to a given network that occur throughout a fixed period of time. We introduce and investigate the Temporal Δ Independent Set problem, a temporal variant of the well known Independent Set problem. This problem is e.g. motivated in the context of finding conflict-free schedules for maximum subsets of tasks, that have certain (changing) constraints on each day they need to be performed. We are specifically interested in the case where each task needs to be performed in a certain time-interval on each day and two tasks are in conflict on a day if their time-intervals overlap on that day. This leads us to considering Temporal Δ Independent Set on the restricted class of temporal unit interval graphs, i.e., temporal graphs where each layer is unit interval. We present several hardness results for this problem, as well as two algorithms: The first is a constant-factor approximation algorithm for instances where τ, the total number of time steps (layers) of the temporal graph, and Δ, a parameter that allows us to model some tolerance in the conflicts, are constants. For the second result we use the notion of order preservation for temporal unit interval graphs that, informally, requires the intervals of every layer to obey a common ordering. We provide an FPT algorithm parameterized by the size of minimum vertex deletion set to order preservation., LIPIcs, Vol. 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), pages 19:1-19:16

Front Matter, Table of Contents, Preface, Conference Organization, OASIcs, Vol. 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022), pages 0:i-0:x

We provide new (parameterized) computational hardness results for Interval Scheduling on Unrelated Machines. It is a classical scheduling problem motivated from just-in-time or lean manufacturing, where the goal is to complete jobs exactly at their deadline. We are given n jobs and m machines. Each job has a deadline, a weight, and a processing time that may be different on each machine. The goal is find a schedule that maximizes the total weight of jobs completed exactly at their deadline. Note that this uniquely defines a processing time interval for each job on each machine. Interval Scheduling on Unrelated Machines is closely related to coloring interval graphs and has been thoroughly studied for several decades. However, as pointed out by Mnich and van Bevern [Computers & Operations Research, 2018], the parameterized complexity for the number m of machines as a parameter remained open. We resolve this by showing that Interval Scheduling on Unrelated Machines is W[1]-hard when parameterized by the number m of machines. To this end, we prove W[1]-hardness with respect to m of the special case where we have parallel machines with eligible machine sets for jobs. This answers Open Problem 8 of Mnich and van Bevern’s list of 15 open problems in the parameterized complexity of scheduling [Computers & Operations Research, 2018]. Furthermore, we resolve the computational complexity status of the unweighted version of Interval Scheduling on Unrelated Machines by proving that it is NP-complete. This answers an open question by Sung and Vlach [Journal of Scheduling, 2005]., LIPIcs, Vol. 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), pages 18:1-18:16

We present several new proofs of lower bounds for the space-stretch tradeoff in labeled network routing. First, we give a new proof of an important result of Cyril Gavoille and Marc Gengler that any routing scheme with stretch < 3 must use Ω(n) bits of space at some node on some network with n vertices, even if port numbers can be changed. Compared to the original proof, our proof is significantly shorter and, we believe, conceptually and technically simpler. A small extension of the proof can show that, in fact, any constant fraction of the n nodes must use Ω(n) bits of space on some graph. Our main contribution is a new result that if port numbers are chosen adversarially, then stretch < 2k+1 implies some node must use Ω(n^(1/k) log n) bits of space on some graph, assuming a girth conjecture by Erdős. We conclude by showing that all known methods of proving a space lower bound in the labeled setting, in fact, require the girth conjecture., LIPIcs, Vol. 246, 36th International Symposium on Distributed Computing (DISC 2022), pages 37:1-37:16

Given an integer linear recurrence sequence $\langle X_n \rangle_n$, the Skolem Problem asks to determine whether there is a natural number $n$ such that $X_n = 0$. Recent work by Lipton, Luca, Nieuwveld, Ouaknine, Purser, and Worrell proved that the Skolem Problem is decidable for a class of reversible sequences of order at most seven. Here we give an alternative proof of their result. Our novel approach employs a powerful result for Galois conjugates that lie on two concentric circles due to Dubickas and Smyth., 15 pages, accepted for publication at MFCS 2022

The betweenness centrality of a vertex v is an important centrality measure that quantifies how many optimal paths between pairs of other vertices visit v. Computing betweenness centrality in a temporal graph, in which the edge set may change over discrete timesteps, requires us to count temporal paths that are optimal with respect to some criterion. For several natural notions of optimality, including foremost or fastest temporal paths, this counting problem reduces to #TEMPORAL PATH, the problem of counting all temporal paths between a fixed pair of vertices; like the problems of counting foremost and fastest temporal paths, #TEMPORAL PATH is #P-hard in general. Motivated by the many applications of this intractable problem, we initiate a systematic study of the parameterised and approximation complexity of #TEMPORAL PATH. We show that the problem presumably does not admit an FPT-algorithm for the feedback vertex number of the static underlying graph, and that it is hard to approximate in general. On the positive side, we prove several exact and approximate FPT-algorithms for special cases., LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 30:1-30:19

OASIcs, Volume 106, ATMOS 2022, Complete Volume, OASIcs, Vol. 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022), pages 1-240

For a fixed graph H, the H-Recoloring problem asks whether, given two homomorphisms from a graph G to H, one homomorphism can be transformed into the other by changing the image of a single vertex in each step and maintaining a homomorphism to H throughout. The most general algorithmic result for H-Recoloring so far has been proposed by Wrochna in 2014, who introduced a topological approach to obtain a polynomial-time algorithm for any undirected loopless square-free graph H. We show that the topological approach can be used to recover essentially all previous algorithmic results for H-Recoloring and that it is applicable also in the more general setting of digraph homomorphisms. In particular, we show that H-Recoloring admits a polynomial-time algorithm i) if H is a loopless digraph that does not contain a 4-cycle of algebraic girth 0 and ii) if H is a reflexive digraph that contains no triangle of algebraic girth 1 and no 4-cycle of algebraic girth 0., LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 43:1-43:21

A singularly (near) optimal distributed algorithm is one that is (near) optimal in two criteria, namely, its time and message complexities. For synchronous CONGEST networks, such algorithms are known for fundamental distributed computing problems such as leader election [Kutten et al., JACM 2015] and Minimum Spanning Tree (MST) construction [Pandurangan et al., STOC 2017, Elkin, PODC 2017]. However, it is open whether a singularly (near) optimal bound can be obtained for the MST construction problem in general asynchronous CONGEST networks. In this paper, we present a randomized distributed MST algorithm that, with high probability, computes an MST in asynchronous CONGEST networks and takes Õ(D^{1+ε} + √n) time and Õ(m) messages, where n is the number of nodes, m the number of edges, D is the diameter of the network, and ε > 0 is an arbitrarily small constant (both time and message bounds hold with high probability). Since Ω̃(D+√n) and Ω(m) are respective time and message lower bounds for distributed MST construction in the standard KT₀ model, our algorithm is message optimal (up to a polylog(n) factor) and almost time optimal (except for a D^ε factor). Our result answers an open question raised in Mashregi and King [DISC 2019] by giving the first known asynchronous MST algorithm that has sublinear time (for all D = O(n^{1-ε})) and uses Õ(m) messages. Using a result of Mashregi and King [DISC 2019], this also yields the first asynchronous MST algorithm that is sublinear in both time and messages in the KT₁ CONGEST model. A key tool in our algorithm is the construction of a low diameter rooted spanning tree in asynchronous CONGEST that has depth Õ(D^{1+ε}) (for an arbitrarily small constant ε > 0) in Õ(D^{1+ε}) time and Õ(m) messages. To the best of our knowledge, this is the first such construction that is almost singularly optimal in the asynchronous setting. This tree construction may be of independent interest as it can also be used for efficiently performing basic tasks such as verified broadcast and convergecast in asynchronous networks., LIPIcs, Vol. 246, 36th International Symposium on Distributed Computing (DISC 2022), pages 19:1-19:24

Front Matter, Table of Contents, Preface, Conference Organization, LIPIcs, Vol. 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022), pages 0:i-0:xii

We initiate the study of distributed graph algorithms under the presence of Byzantine nodes. We consider the fundamental problem of testing the connectivity of a graph in the congested clique model in a Byzantine setting. We are given a n-vertex (arbitrary) graph G embedded in a n-node congested clique where an arbitrary subset of B nodes of the clique of size up to (1/3-ε)n (for any arbitrary small constant ε > 0) can be Byzantine. We consider the full information model where Byzantine nodes can behave arbitrarily, collude with each other, and have unlimited computational power and full knowledge of the states and actions of the honest nodes, including random choices made up to the current round. Our main result is an efficient randomized distributed algorithm that is able to correctly distinguish between two contrasting cases: (1) the graph G⧵ B (i.e., the graph induced by the removal of the vertices assigned to the Byzantine nodes in the clique) is connected or (2) the graph G is far from connected, i.e., it has at least 2|B|+1 connected components. Our algorithm runs in O(polylog n) rounds in the congested clique model and guarantees that all honest nodes will decide on the correct case with high probability. Since Byzantine nodes can lie about the vertices assigned to them, we show that this is essentially the best possible that can be done by any algorithm. Our result can be viewed also in the spirit of property testing, where our algorithm is able to distinguish between two contrasting cases while giving no guarantees if the graph falls in the grey area (i.e., neither of the cases occur). Our work is a step towards robust and secure distributed graph computation that can output meaningful results even in the presence of a large number of faulty or malicious nodes., LIPIcs, Vol. 246, 36th International Symposium on Distributed Computing (DISC 2022), pages 7:1-7:21

We study the space reachable by rolling a 3D convex polyhedron on a 2D periodic tessellation in the xy-plane, where at every step a face of the polyhedron must coincide exactly with a tile of the tessellation it rests upon, and the polyhedron rotates around one of the incident edges of that face until the neighboring face hits the xy plane. If the whole plane can be reached by a sequence of such rolls, we call the polyhedron a plane roller for the given tessellation. We further classify polyhedra that reach a constant fraction of the plane, an infinite area but vanishing fraction of the plane, or a bounded area as hollow-plane rollers, band rollers, and bounded rollers respectively. We present a polynomial-time algorithm to determine the set of tiles in a given periodic tessellation reachable by a given polyhedron from a given starting position, which in particular determines the roller type of the polyhedron and tessellation. Using this algorithm, we compute the reachability for every regular-faced convex polyhedron on every regular-tiled (≤ 4)-uniform tessellation., LIPIcs, Vol. 226, 11th International Conference on Fun with Algorithms (FUN 2022), pages 6:1-6:16

Front Matter, Table of Contents, Preface, Conference Organization, LIPIcs, Vol. 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), pages 0:i-0:xviii

A constraint language Γ has non-redundancy f(n) if every instance of CSP(Γ) with n variables contains at most f(n) non-redundant constraints. If Γ has maximum arity r then it has non-redundancy O(n^r), but there are notable examples for which this upper bound is far from the best possible. In general, the non-redundancy of constraint languages is poorly understood and little is known beyond the trivial bounds Ω(n) and O(n^r). In this paper, we introduce an elementary algebraic framework dedicated to the analysis of the non-redundancy of constraint languages. This framework relates redundancy-preserving reductions between constraint languages to closure operators known as pattern partial polymorphisms, which can be interpreted as generic mechanisms to generate redundant constraints in CSP instances. We illustrate the power of this framework by deriving a simple characterisation of all languages of arity r having non-redundancy Θ(n^r)., LIPIcs, Vol. 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022), pages 11:1-11:15

Research on Temporal Graphs has expanded in the last few years. Most of the results till now, address problems related to the notion of Temporal Paths (and Temporal Connectivity). In this talk, we focus, instead, on problems whose main topic is not on Temporal Paths. In particular, we will discuss Temporal Vertex Covers, the notion of Temporal Transitivity, and also issues and models of stochastic temporal graphs. We believe that several algorithmic graph problems, not directly related to paths, can be raised in the temporal domain. This may motivate new research towards lifting more topics of algorithmic graph theory to the temporal case., LIPIcs, Vol. 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), pages 2:1-2:1

Lovász (1967) showed that two graphs G and H are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph F, the number of homomorphisms from F to G equals the number of homomorphisms from F to H. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalence and algebraic equation systems. In this paper, we provide a unified algebraic framework for such results by examining the linear-algebraic and representation-theoretic structure of tensors counting homomorphisms from labelled graphs. The existence of certain linear transformations between such homomorphism tensor subspaces can be interpreted both as homomorphism indistinguishability over a graph class and as feasibility of an equational system. Following this framework, we obtain characterisations of homomorphism indistinguishability over several natural graph classes, namely trees of bounded degree, graphs of bounded pathwidth (answering a question of Dell et al. (2018)), and graphs of bounded treedepth., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 70:1-70:20

There is a large and important collection of Ramsey-type combinatorial problems, closely related to central problems in complexity theory, that can be formulated in terms of the asymptotic growth of the size of the maximum independent sets in powers of a fixed small (directed or undirected) hypergraph, also called the Shannon capacity. An important instance of this is the corner problem studied in the context of multiparty communication complexity in the Number On the Forehead (NOF) model. Versions of this problem and the NOF connection have seen much interest (and progress) in recent works of Linial, Pitassi and Shraibman (ITCS 2019) and Linial and Shraibman (CCC 2021). We introduce and study a general algebraic method for lower bounding the Shannon capacity of directed hypergraphs via combinatorial degenerations, a combinatorial kind of "approximation" of subgraphs that originates from the study of matrix multiplication in algebraic complexity theory (and which play an important role there) but which we use in a novel way. Using the combinatorial degeneration method, we make progress on the corner problem by explicitly constructing a corner-free subset in $F_2^n \times F_2^n$ of size $\Omega(3.39^n/poly(n))$, which improves the previous lower bound $\Omega(2.82^n)$ of Linial, Pitassi and Shraibman (ITCS 2019) and which gets us closer to the best upper bound $4^{n - o(n)}$. Our new construction of corner-free sets implies an improved NOF protocol for the Eval problem. In the Eval problem over a group $G$, three players need to determine whether their inputs $x_1, x_2, x_3 \in G$ sum to zero. We find that the NOF communication complexity of the Eval problem over $F_2^n$ is at most $0.24n + O(\log n)$, which improves the previous upper bound $0.5n + O(\log n)$., Comment: A short version of this paper will appear in the proceedings of ITCS 2022. This paper improves results that appeared in arxiv:2104.01130v1

LIPIcs, Volume 223, CPM 2022, Complete Volume, LIPIcs, Vol. 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), pages 1-470

We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 × 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. The goal is to clear the board, i.e, make a sequence of captures after which only one piece is left. We generalize this game to unbounded boards with n pieces, each of which have a given number of captures that they are permitted to make. We show that Generalized Solo Chess is NP-complete, even when it is played by only rooks that have at most two captures remaining. It also turns out to be NP-complete even when every piece is a queen with exactly two captures remaining in the initial configuration. In contrast, we show that solvable instances of Generalized Solo Chess can be completely characterized when the game is: a) played by rooks on a one-dimensional board, and b) played by pawns with two captures left on a 2D board. Inspired by Generalized Solo Chess, we also introduce the Graph Capture Game, which involves clearing a graph of tokens via captures along edges. This game subsumes Generalized Solo Chess played by knights. We show that the Graph Capture Game is NP-complete for undirected graphs and DAGs., LIPIcs, Vol. 226, 11th International Conference on Fun with Algorithms (FUN 2022), pages 5:1-5:20

Vectorial representations of graphs and relational structures, so-called graph embeddings, make it possible to apply standard tools from data mining, machine learning, and statistics to the graph domain. In particular, graph embeddings aim to capture important information about, both, the graph structure and available side information as a vector, to enable downstream tasks such as classification, regression, or clustering. Starting from the 1960s in chemoinformatics, research in various communities has resulted in a plethora of approaches, often with recurring ideas. However, most of the field advancements are driven by intuition and empiricism, often tailored to a specific application domain. Until recently, the area has received little stimulus from theoretical computer science, graph theory, and learning theory. The Dagstuhl Seminar 22132 "Graph Embeddings: Theory meets Practice", was aimed to gather leading applied and theoretical researchers in graph embeddings and adjacent areas, such as graph isomorphism, bio- and chemoinformatics, and graph theory, to stimulate an increased exchange of ideas between these communities., DagRep, Volume 12, Issue 3, pages 141-155

Global transformations provide a categorical framework for capturing synchronous rewriting systems, generalizing cellular automata to dynamical systems over dynamic spaces. Originally developed for addressing deterministic dynamical systems, the presented work raises the question of non-determinism. While a usual approach is to develop a general non-deterministic setting where deterministic systems can be retrieved as a specific case, we show here that by choosing the right parametrization, global transformations can already be used to handle non-determinism. Context-free Lindenmayer systems, already shown to be captured by global transformation in the deterministic case, are used to illustrate the approach. From this concrete example, the formal obstructions are exhibited, leading to a solution involving a 2-categorical monad and its associated Kleisli construction., LIPIcs, Vol. 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), pages 49:1-49:13

In an influential paper, Erdős and Selfridge introduced the Maker-Breaker game played on a hypergraph, or equivalently, on a monotone CNF. The players take turns assigning values to variables of their choosing, and Breaker’s goal is to satisfy the CNF, while Maker’s goal is to falsify it. The Erdős-Selfridge Theorem says that the least number of clauses in any monotone CNF with k literals per clause where Maker has a winning strategy is Θ(2^k). We study the analogous question when the CNF is not necessarily monotone. We prove bounds of Θ(√2 ^k) when Maker plays last, and Ω(1.5^k) and O(r^k) when Breaker plays last, where r = (1+√5)/2≈ 1.618 is the golden ratio., LIPIcs, Vol. 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), pages 31:1-31:11

We study the complexity of approximating the partition function of the $q$-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on $q=2$, which corresponds to the case of the Ising model; for $q>2$, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing \#P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all $q\geq 2$ and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lov��sz and Welsh in the context of quantum computations., 58 pages. Changes on version 2: minor changes

Given a hypergraph with uncertain node weights following known probability distributions, we study the problem of querying as few nodes as possible until the identity of a node with minimum weight can be determined for each hyperedge. Querying a node has a cost and reveals the precise weight of the node, drawn from the given probability distribution. Using competitive analysis, we compare the expected query cost of an algorithm with the expected cost of an optimal query set for the given instance. For the general case, we give a polynomial-time $f(\alpha)$-competitive algorithm, where $f(\alpha)\in [1.618+\epsilon,2]$ depends on the approximation ratio $\alpha$ for an underlying vertex cover problem. We also show that no algorithm using a similar approach can be better than $1.5$-competitive. Furthermore, we give polynomial-time $4/3$-competitive algorithms for bipartite graphs with arbitrary query costs and for hypergraphs with a single hyperedge and uniform query costs, with matching lower bounds., Comment: An extended abstract appears in the proceedings of the 29th Annual European Symposium on Algorithms (ESA 2021)