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

Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving01:29

Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving

44
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
44
Compacting Factor test01:22

Compacting Factor test

119
The compacting factor test is a method used to assess the workability of concrete. It is  especially suitable for concrete mixes containing aggregates up to one and a half inches in size. This test involves specialized equipment consisting of two truncated cone-shaped hoppers and a cylinder, all with polished interior surfaces to minimize friction.
The procedure begins by placing concrete into the upper hopper without any compaction. Once filled, the bottom door of this hopper is opened,...
119
Theorems of Pappus and Guldinus: Problem Solving01:12

Theorems of Pappus and Guldinus: Problem Solving

708
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
708
DNA Packaging00:58

DNA Packaging

102.2K
Overview
102.2K
Castigliano's Theorem: Problem Solving01:14

Castigliano's Theorem: Problem Solving

600
The deflection of a simply supported beam that carries a central point load can be analyzed using structural mechanics principles, particularly by applying Castigliano's theorem. This theorem relates the displacement at the load application point to the partial derivatives of the strain energy in the structure. The simply supported beam with a point load at its center has symmetric reaction forces at the supports, each bearing half of the load. The bending moment at any point along the beam...
600
Chromatin Packaging02:21

Chromatin Packaging

15.2K
Each human somatic cell contains 6 billion base-pairs of DNA. Each base-pair is 0.34 nm long, which means that each diploid cell contains a staggering 2 meters of DNA. How is such a long DNA strand packed inside a nucleus measuring only 10 - 20 microns in diameter? 
The chromatin
In combination with specialized DNA binding protein called Histones, the DNA double helix forms a compact DNA: protein complex called chromatin. The chromatin itself is further compacted into higher-order...
15.2K

You might also read

Related Articles

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

Sort by
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

Related Experiment Video

Updated: Jun 10, 2025

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules
10:58

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules

Published on: July 25, 2013

17.0K

On the Parameterized Complexity of Compact Set Packing.

Ameet Gadekar1

  • 1Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel.

Algorithmica
|October 16, 2024
PubMed
Summary
This summary is machine-generated.

This study investigates the parameterized complexity of the Set Packing problem, focusing on "compact" instances. Researchers found a dichotomy: the problem is fixed-parameter tractable when the parameter is small, but W[1]-hard otherwise.

Keywords:
Parameterized complexitySet packing

More Related Videos

Assembly and Characterization of Polyelectrolyte Complex Micelles
08:44

Assembly and Characterization of Polyelectrolyte Complex Micelles

Published on: March 2, 2020

10.7K
Simple In-House Ultra-High Performance Capillary Column Manufacturing with the FlashPack Approach
13:36

Simple In-House Ultra-High Performance Capillary Column Manufacturing with the FlashPack Approach

Published on: December 4, 2021

3.9K

Related Experiment Videos

Last Updated: Jun 10, 2025

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules
10:58

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules

Published on: July 25, 2013

17.0K
Assembly and Characterization of Polyelectrolyte Complex Micelles
08:44

Assembly and Characterization of Polyelectrolyte Complex Micelles

Published on: March 2, 2020

10.7K
Simple In-House Ultra-High Performance Capillary Column Manufacturing with the FlashPack Approach
13:36

Simple In-House Ultra-High Performance Capillary Column Manufacturing with the FlashPack Approach

Published on: December 4, 2021

3.9K

Area of Science:

  • Theoretical Computer Science
  • Computational Complexity Theory
  • Algorithm Design and Analysis

Background:

  • The Set Packing problem is a fundamental NP-hard optimization problem concerning finding a maximum collection of disjoint sets.
  • Parameterized complexity analyzes computational problems with respect to a parameter, aiming to identify tractable subproblems.
  • Previous research indicates Parameterized Set Packing (PSP) is not fixed-parameter tractable (FPT) unless P=NP, requiring exponential time.

Purpose of the Study:

  • To explore tractable instances of Set Packing from a parameterized complexity viewpoint.
  • To investigate the complexity of Compact PSP, where input instances have a specific structural property (compactness).

Main Methods:

  • Introduced the concept of a 'compact' instance for PSP, defined by the size of the ground set relative to the number of sets.
  • Developed a novel gadget, the 'Compatible Intersecting Set System pair', to prove hardness results.
  • Applied techniques from parameterized complexity to establish a dichotomy for Compact PSP.

Main Results:

  • Established a dichotomy for Compact PSP: it is FPT when the parameter k is small, but W[1]-hard when k is large.
  • Demonstrated that Compact PSP does not admit a $2^{o(k)} n^{O(1)}$ time algorithm, assuming the Exponential Time Hypothesis (ETH).
  • Showed that existing constructions for related problems like Set Cover do not extend to Compact PSP.

Conclusions:

  • The compactness of Set Packing instances significantly impacts its parameterized complexity, leading to a clear FPT/W[1]-hard boundary.
  • The newly constructed gadget is crucial for proving the hardness of Compact PSP and offers insights into related problems.
  • The framework can be extended to analyze other problems, such as Compact k-VectorSum, potentially yielding improved lower bounds.