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

Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex graphG and an integer k as input, and asked whether at most k edges can be added to G so that theresulting graph does not contain a graph from F as an induced subgraph. It appeared recentlythat special cases of F-Completion, the problem of completing into a chordal graph knownas Minimum Fill-in, corresponding to the case of F = {C4,C5,C6, . . .}, and the problem ofcompleting into a split graph, i.e., the case of F = {C4, 2K2,C5}, are solvable in parameterizedsubexponential time 2O(√ k log k)nO(1). The exploration of this phenomenon is the main motivationfor our research on F-Completion.In this paper we prove that completions into several well studied classes of graphs withoutlong induced cycles also admit parameterized subexponential time algorithms by showing that:The problem Trivially Perfect Completion is solvable in parameterized subexponentialtime 2O(√k log k)nO(1), that is F-Completion for F = {C4, P4}, a cycle and a path on fourvertices.The problems known in the literature as Pseudosplit Completion, the case where F ={2K2,C4}, and Threshold Completion, where F = {2K2, P4,C4}, are also solvable intime 2O(√k log k)nO(1).We complement our algorithms for F-Completion with the following lower bounds:For F = {2K2}, F = {C4}, F = {P4}, and F = {2K2, P4}, F-Completion cannot besolved in time 2o(k)nO(1) unless the Exponential Time Hypothesis (ETH) fails.Our upper and lower bounds provide a complete picture of the subexponential parameterizedcomplexity of F-Completion problems for F ⊆ {2K2,C4, P4}.</p

Exploring Subexponential Parameterized Complexity of Completion Problems