A parameterized complexity view on collapsing k-cores

DOI10.1007/S00224-021-10045-WOpenAlexW2963602119MaRDI QIDQ825978FDOQ825978

Authors: Hendrik Molter, Ondřej Suchý, Jun-Jie Luo 

Publication date: 18 December 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-021-10045-w

Recommendations

• A parameterized complexity view on collapsing \(k\)-cores
• Can we create large \(k\)-cores by adding few edges?
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets

zbMATH Keywords

social network analysisgraph algorithmsfixed-parameter tractabilityfeedback vertex set\(r\)-degenerate vertex deletionkernelization lower bounds

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Linear time solvable optimization problems on graphs of bounded clique-width
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• On the approximability of influence in social networks
• Treewidth governs the complexity of target set selection
• Lower bounds based on the exponential time hypothesis
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized algorithms
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Title not available (Why is that?)
• Kernelization Lower Bounds by Cross-Composition
• Improved upper bounds for vertex cover
• Treewidth. Computations and approximations
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Faster deterministic \textsc{Feedback Vertex Set}
• The bandwidth problem for graphs and matrices—a survey
• The parameterized complexity of editing graphs for bounded degeneracy
• A \(c^k n\) 5-approximation algorithm for treewidth
• On feedback vertex set: new measure and new structures
• Constant thresholds can make target set selection tractable
• Fast algorithms for determining (generalized) core groups in social networks
• Parameterized inapproximability of target set selection and generalizations
• Linear time parameterized algorithms for \textsc{Subset Feedback Vertex Set}
• Linear-time kernelization for feedback vertex set
• Can we create large \(k\)-cores by adding few edges?
• Improved analysis of highest-degree branching for feedback vertex set
• The complexity of finding harmless individuals in social networks
• A parameterized complexity view on collapsing \(k\)-cores
• Title not available (Why is that?)
• Target set selection parameterized by clique-width and maximum threshold
• A naive algorithm for feedback vertex set
• Immunity against local influence
• Preventing unraveling in social networks: the anchored \(k\)-core problem

Cited In (9)

• Targeted \(k\)-node collapse problem: towards understanding the robustness of local \(k\)-core structure
• A parameterized complexity view on collapsing \(k\)-cores
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Preventing unraveling in social networks: the anchored \(k\)-core problem
• Mathematical programming formulations for the collapsed k-core problem
• Preventing unraveling in social networks: the anchored \(k\)-core problem
• Building large \(k\)-cores from sparse graphs
• Building large \(k\)-cores from sparse graphs

This page was built for publication: A parameterized complexity view on collapsing \(k\)-cores

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q825978)