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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study provably effective and efficient data reduction for a class ofNP-hard graph modification problems based on vertex degree properties. We showfixed-parameter tractability for NP-hard graph completion (that is, edgeaddition) cases while we show that there is no hope to achieve analogousresults for the corresponding vertex or edge deletion versions. Our algorithmsare based on transforming graph completion problems into efficiently solvablenumber problems and exploiting f-factor computations for translating theresults back into the graph setting. Our core observation is that we encountera win-win situation: either the number of edge additions is small or theproblem is polynomial-time solvable. This approach helps in answering an openquestion by Mathieson and Szeider [JCSS 2012] concerning the polynomialkernelizability of Degree Constraint Edge Addition and leads to a generalmethod of approaching polynomial-time preprocessing for a wider class of degreesequence completion problems.

Win-Win Kernelization for Degree Sequence Completion Problems