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/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

For the General Factor problem we are given an undirected graph $G$ and foreach vertex $v\in V(G)$ a finite set $B_v$ of non-negative integers. The taskis to decide if there is a subset $S\subseteq E(G)$ such that $deg_S(v)\in B_v$for all vertices $v$ of $G$. The maxgap of a finite integer set $B$ is thelargest $d\ge 0$ such that there is an $a\ge 0$ with $[a,a+d+1]\capB=\{a,a+d+1\}$. Cornu\'ejols (1988) showed that if the maxgap of all sets $B_v$is at most 1, then the decision version of General Factor is poly-timesolvable. Dudycz and Paluch (2018) extended this result for the minimizationand maximization versions. Using convolution techniques from van Rooij (2020),we improve upon the previous algorithm by Arulselvan et al. (2018) and presentan algorithm counting the number of solutions of a certain size in time$O^*((M+1)^k)$, given a tree decomposition of width $k$, where $M=\max_v \maxB_v$.  We prove that this algorithm is essentially optimal for all cases that arenot polynomial time solvable for the decision, minimization or maximizationversions. We prove that such improvements are not possible even for $B$-Factor,which is General Factor on graphs where all sets $B_v$ agree with the fixed set$B$. We show that for every fixed $B$ where the problem is NP-hard, our newalgorithm cannot be significantly improved: assuming the Strong ExponentialTime Hypothesis (SETH), no algorithm can solve $B$-Factor in time $O^*((\maxB+1-\epsilon)^k)$ for any $\epsilon>0$. We extend this bound to the countingversion of $B$-Factor for arbitrary, non-trivial sets $B$, assuming #SETH.  We also investigate the parameterization of the problem by cutwidth. Unlikefor treewidth, a larger set $B$ does not make the problem harder: Given alinear layout of width $k$ we give a $O^*(2^k)$ algorithm for any $B$ andprovide a matching lower bound that this is optimal for the NP-hard cases.

Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth