In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the graph satisfies P or not. Often, testers are restricted to a constant number of queries. While the graph properties for which there exists such a tester are somewhat well characterized in the dense graph model, it is not the case for sparse graphs. In this area, Czumaj and Sohler (FOCS’19) proved that H-freeness (i.e. the property of excluding the graph H as a subgraph) can be tested with constant queries on planar graphs as well as on graph classes excluding a minor. Using results from the sparsity toolkit, we propose a simpler alternative to the proof of Czumaj and Sohler, for a statement generalized to the broader notion of bounded expansion. That is, we prove that for any class 𝒞 with bounded expansion and any graph H, testing H-freeness can be done with constant query complexity on any graph G in 𝒞, where the constant depends on H and 𝒞, but is independent of G. While classes excluding a minor are prime examples of classes with bounded expansion, so are, for example, cubic graphs, graph classes with bounded maximum degree, or graphs of bounded book thickness. Additionally, random graphs with bounded average degree almost surely have bounded expansion.

Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are W[1]-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form ϕ≡∃ x₁⋯ ∃ x_k ∑_{α ∈ I} #y ψ_α(x₁,…,x_k,y) ≥ t, where ψ_α is a quantifier-free formula for each α ∈ I, t is an arbitrary number, and #y is a counting quantifier, can be evaluated in time f(d,k)n, where n is the number of vertices and d is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set.

Abstract We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of n items with a size and a value each, and an algorithm has to decide whether or not and how often to pack each item into a knapsack of bounded capacity. The items are given online and the total size of the packed items must not exceed the knapsack’s capacity, while the objective is to maximize the total value of the packed items. While each item can only be packed once in the classical knapsack problem (also called the 0-1 knapsack problem), the unbounded version allows for items to be packed multiple times. We show that the simple unbounded knapsack problem, where the size of each item is equal to its value, allows for a competitive ratio of 2. We also analyze randomized algorithms and show that, in contrast to the 0-1 knapsack problem, one uniformly random bit cannot improve an algorithm’s performance. More randomness lowers the competitive ratio to less than 1 . 736 , but it can never be below 1 . 693 . In the advice complexity setting, we measure how many bits of information (so-called advice bits) the algorithm has to know to achieve some desired solution quality. For the simple unbounded knapsack problem, one advice bit lowers the competitive ratio to $$\varvec{3/2}$$ 3 / 2 . While this cannot be improved with fewer than $$\varvec{\log }_{\varvec{2}} \varvec{n} $$ log 2 n advice bits for instances of length n , a competitive ratio of $$\varvec{1}\varvec{+}\varvec{\varepsilon }$$ 1 + ε can be achieved with $$\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$$ O ( ε - 1 · log ( n ε - 1 ) ) advice bits for any $$\varvec{\varepsilon }\varvec{>}\varvec{0}$$ ε > 0 . We further show that no amount of advice bounded by a function $$\varvec{f(n)}$$ f ( n ) allows an algorithm to be optimal. We also study the online general unbounded knapsack problem and show that it does not allow for any bounded competitive ratio for both deterministic and randomized algorithms, as well as for algorithms using fewer than $$\varvec{\log }_{\varvec{2}} \varvec{n}$$ log 2 n advice bits. We also provide a surprisingly simple algorithm that uses $$\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$$

It is known that first-order logic with some counting extensions can be efficiently evaluated on graph classes with bounded expansion, where depth-$r$ minors have constant density. More precisely, the formulas are $\exists x_1 ... x_k \#y φ(x_1,...,x_k, y)>N$, where $φ$ is an FO-formula. If $φ$ is quantifier-free, we can extend this result to nowhere dense graph classes with an almost linear FPT run time. Lifting this result further to slightly more general graph classes, namely almost nowhere dense classes, where the size of depth-$r$ clique minors is subpolynomial, is impossible unless FPT=W[1]. On the other hand, in almost nowhere dense classes we can approximate such counting formulas with a small additive error. Note those counting formulas are contained in FOC({<}) but not FOC1(P). In particular, it follows that partial covering problems, such as partial dominating set, have fixed parameter algorithms on nowhere dense graph classes with almost linear running time.