Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Setting Time of Cement01:12

Setting Time of Cement

709
The setting time of cement refers to the process of cement paste transitioning from a plastic state to a solid state. This process is crucial in construction as it dictates the timeframe for concrete placement, compaction, and finishing. The onset of this solidification is termed the initial set, indicating when the paste becomes unworkable. The final set is when the paste has solidified completely, and further handling or manipulation can no longer affect its shape. The cement strength is...
709
Protein Complex Assembly02:41

Protein Complex Assembly

16.8K
Proteins can form homomeric complexes with another unit of the same protein or heteromeric complexes with different types.  Most protein complexes self-assemble spontaneously via ordered pathways, while some proteins need assembly factors that guide their proper assembly. Despite the crowded intracellular environment, proteins usually interact with their correct partners and form functional complexes.
Many viruses self-assemble into a fully functional unit using the infected host cell to...
16.8K
Protein Complexes with Interchangeable Parts01:57

Protein Complexes with Interchangeable Parts

2.9K
Groups of proteins may form a complex where each protein in this complex has a different role in the overall execution of the complex’s function. Often some of the proteins in the complex can be replaced by a closely related variant to give a complex that contains many of the same components yet is functionally distinct.
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order...
2.9K
Complex Numbers01:29

Complex Numbers

320
The real number system cannot represent the square root of a negative number, which restricts solutions for certain equations, such as quadratics with negative discriminants. To address this, the complex number system was developed, introducing the imaginary unit i, where i = √(-1). This extension allows for the representation of all roots, including those involving negative radicands.A complex number is written in the form x + yi, where x and y are real numbers. Here, x represents the...
320
Specialized Care Centers and Settings-II01:30

Specialized Care Centers and Settings-II

1.3K
Rural Health Centers
Rural health centers are specialized care facilities in remote locations with very few medical personnel. The primary care providers who run the centers are mostly Registered Nurse Practitioners. Here, emergency treatment is provided to critically ill or injured patients before they are transferred to the closest hospital. Fortunately, due to advancement in technology, many rural healthcare facilities and professionals have easy access to diagnostic and treatment...
1.3K
PPE Use in Healthcare Settings I: Donning01:22

PPE Use in Healthcare Settings I: Donning

1.7K
Donning PPE must be completed before contact with the patient. This process protects from infectious agents. The sequence and action included in each donning are critical, and the steps must be systematic to avoid exposure to pathogens. The institutional policy also needs to be followed while donning PPE. The pre-donning preparations are gathering equipment, inspecting the PPE equipment for tears, holes, or damage, removing jewelry, removing any garments below the elbows, and tying the hair...
1.7K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Ranking Specific Sets of Objects.

Datenbank-Spektrum : Zeitschrift fur Datenbanktechnologie : Organ der Fachgruppe Datenbanken der Gesellschaft fur Informatik e.V·2017
Same author

Methods for solving reasoning problems in abstract argumentation - A survey.

Artificial intelligence·2015
Same journal

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity.

Algorithmica·2026
Same journal

A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games.

Algorithmica·2026
Same journal

Fully Characterizing Lossy Catalytic Computation.

Algorithmica·2026
Same journal

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

Algorithmica·2026
Same journal

The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms.

Algorithmica·2026
Same journal

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem.

Algorithmica·2025
See all related articles

Related Experiment Video

Updated: Feb 8, 2026

Setting Limits on Supersymmetry Using Simplified Models
07:46

Setting Limits on Supersymmetry Using Simplified Models

Published on: November 15, 2013

9.0K

Complexity of Secure Sets.

Bernhard Bliem1, Stefan Woltran1

  • 1Institute of Information Systems 184/2, TU Wien, Favoritenstrasse 9-11, 1040 Vienna, Austria.

Algorithmica
|June 26, 2018
PubMed
Summary
This summary is machine-generated.

We show that finding a non-empty secure set of size k in a graph is NP-complete. The problem is also W[2]-hard when parameterized by treewidth, despite being fixed-parameter tractable for solution size.

Keywords:
Complexity analysisParameterized algorithmsParameterized complexitySecure setTreewidth

More Related Videos

Decellularization of the Murine Cardiopulmonary Complex
08:34

Decellularization of the Murine Cardiopulmonary Complex

Published on: May 30, 2021

3.4K
New Variations for Strategy Set-shifting in the Rat
09:45

New Variations for Strategy Set-shifting in the Rat

Published on: January 23, 2017

8.6K

Related Experiment Videos

Last Updated: Feb 8, 2026

Setting Limits on Supersymmetry Using Simplified Models
07:46

Setting Limits on Supersymmetry Using Simplified Models

Published on: November 15, 2013

9.0K
Decellularization of the Murine Cardiopulmonary Complex
08:34

Decellularization of the Murine Cardiopulmonary Complex

Published on: May 30, 2021

3.4K
New Variations for Strategy Set-shifting in the Rat
09:45

New Variations for Strategy Set-shifting in the Rat

Published on: January 23, 2017

8.6K

Area of Science:

  • Graph Theory
  • Computational Complexity

Background:

  • A secure set S in a graph ensures that for any vertex X, the majority of its neighbors are in S.
  • Determining if a set S is secure is known to be NP-complete.

Purpose of the Study:

  • To determine the complexity of finding a non-empty secure set of size at most k.
  • To analyze the parameterized complexity of secure set problems with respect to treewidth.
  • To provide an upper bound for the problem and an FPT algorithm for bounded treewidth graphs.

Main Methods:

  • NP-completeness proof for the decision problem of finding a secure set of size at most k.
  • W[2]-hardness proof for the problem parameterized by treewidth.
  • Membership in the complexity class defined by treewidth parameterization.
  • Development of a fixed-parameter tractable (FPT) algorithm for checking secure sets on bounded treewidth graphs.

Main Results:

  • The problem of deciding the existence of a non-empty secure set of size at most k is NP-complete.
  • The problem is W[2]-hard when parameterized by treewidth.
  • The problem is in the complexity class defined by treewidth parameterization.
  • An FPT algorithm is presented for checking if a given set is secure on graphs with bounded treewidth.

Conclusions:

  • The complexity of finding small secure sets in graphs is now precisely characterized as NP-complete.
  • The W[2]-hardness result for treewidth parameterization is a significant finding, contrasting with expectations for similar subset problems.
  • The study provides both theoretical complexity bounds and practical algorithmic solutions for secure set problems on bounded treewidth graphs.