English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Pro

Presents the zaia usage as premium feature

ZAIA

Presents AI Discovery search usage as a premium feature

AI Discovery

Presents AI Discovery explain and summary usage as a premium feature

Content Analysis

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Presents the pdf analysis as premium feature

PDF Analysis

1500 Top-up

3000 Top-up

Zendy Basic

2500 Top-up

Zendy Unlimited

Presents the access of premium content as premium feature

Premium Content

In the Vector Connectivity problem we are given an undirected graph $$G=(V,E)$$G=(V,E), a demand function $$\\lambda :V\\rightarrow \\{0,\\ldots ,d\\}$$ź:Vź{0,ź,d}, and an integer k. The question is whether there exists a set S of at most k vertices such that every vertex $$v\\in V{\\setminus } S$$vźV\\S has at least $$\\lambda (v)$$ź(v) vertex-disjoint paths to S; this abstractly captures questions about placing servers or warehouses relative to demands. The problem is $$\\mathsf {NP}$$NP-hard already for instances with $$d=4$$d=4 (Cicalese et al., Theoretical Computer Science '15), admits a log-factor approximation (Boros et al., Networks '14), and is fixed-parameter tractable in terms of k (Lokshtanov, unpublished '14). We prove several results regarding kernelization and approximation for Vector Connectivity and the variant Vector d-Connectivity where the upper bound d on demands is a fixed constant. For Vector d-Connectivity we give a factor d-approximation algorithm and construct a vertex-linear kernelization, that is, an efficient reduction to an equivalent instance with $$f(d)k=O(k)$$f(d)k=O(k) vertices. For Vector Connectivity we have a factor $$\\mathsf {opt} $$opt-approximation and we can show that it has no kernelization to size polynomial in k or even $$k+d$$k+d unless $$\\mathsf {NP} \\subseteq \\mathsf {coNP}/\\mathsf {poly}$$NP⊆coNP/poly, which shows that $$f(d){\\text {poly}}(k)$$f(d)poly(k) is optimal for Vector d-Connectivity. Finally, we give a simple randomized fixed-parameter algorithm for Vector Connectivity with respect to k based on matroid intersection.

On Kernelization and Approximation for the Vector Connectivity Problem