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

Mean free path and Mean free time01:22

Mean free path and Mean free time

5.2K
Consider the gas molecules in a cylinder. They move in a random motion as they collide with each other and change speed and direction. The average of all the path lengths between collisions is known as the "mean free path."
5.2K
Approximate Integration01:24

Approximate Integration

58
In many practical and theoretical contexts, the exact value of a definite integral may be inaccessible. This limitation typically arises when the antiderivative of a function is either unknown or cannot be expressed in a closed mathematical form. Alternatively, it can occur when a function is defined not by a formula but by a finite set of empirical data points, such as those collected during experiments. In these cases, approximate integration techniques provide a valuable solution.One of the...
58
Tight Junctions01:29

Tight Junctions

7.2K
Tight junctions are molecular seals between cells that prevent the leaking of fluids, ions, and other small solutes across cavities and compartments in multicellular organisms. They are mainly composed of claudin and occludin transmembrane proteins, and other proteins such as tricellulin and JAM (junctional adhesion molecule). All these proteins are 4-pass transmembrane proteins, except JAM, which is a single-pass transmembrane protein belonging to the immunoglobulin superfamily. The...
7.2K
Linearization and Approximation01:26

Linearization and Approximation

71
Linearization is a mathematical technique used to approximate complex, nonlinear functions with simpler linear models in the vicinity of a chosen reference point. The method is based on the idea that, although a function may be difficult to evaluate exactly, its behavior near a specific input value can often be closely approximated by the tangent line at that point. This approach is particularly useful when small deviations from a known value are involved.Consider the square root function, for...
71
Path Between Thermodynamics States01:21

Path Between Thermodynamics States

4.1K
Consider the two thermodynamic processes involving an ideal gas that are represented by paths AC and ABC in Figure 1:
4.1K
Application of Linearization and Approximation01:29

Application of Linearization and Approximation

103
A drone flying through complex terrain often relies on more than one sensing method to estimate small changes in altitude. Along with direct measurements, air pressure provides a useful indirect indicator of vertical movement. Atmospheric pressure decreases as altitude increases, and this relationship is commonly described using an exponential model. Although accurate, converting pressure measurements into altitude values requires calculations that are too complex to perform repeatedly during...
103

You might also read

Related Articles

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

Sort by
Same author

(Re)packing Equal Disks into Rectangle.

Discrete & computational geometry·2024
Same author

Diverse collections in matroids and graphs.

Mathematical programming·2024
Same author

Special Issue Dedicated to the 16th International Symposium on Parameterized and Exact Computation.

Algorithmica·2022
Same author

Parameterized Complexity of Directed Spanner Problems.

Algorithmica·2022
Same author

Finding Cactus Roots in Polynomial Time.

Theory of computing systems·2019
Same journal

FullSynesth: Syntenic Reconciliation of a Set of Consistent Gene Trees.

Theory of computing systems·2026
Same journal

The Ground-Set-Cost Budgeted Maximum Coverage Problem.

Theory of computing systems·2025
Same journal

Rudin-Shapiro Sums Via Automata Theory and Logic.

Theory of computing systems·2025
Same journal

Prediction and MDL for infinite sequences.

Theory of computing systems·2024
Same journal

On Polynomial Recursive Sequences.

Theory of computing systems·2024
Same journal

Space Lower Bounds for the Signal Detection Problem.

Theory of computing systems·2021
See all related articles

Related Experiment Video

Updated: Feb 10, 2026

Quantification of Fungal Colonization, Sporogenesis, and Production of Mycotoxins Using Kernel Bioassays
10:01

Quantification of Fungal Colonization, Sporogenesis, and Production of Mycotoxins Using Kernel Bioassays

Published on: April 23, 2012

18.7K

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths.

Matthias Bentert1,2, Fedor V Fomin1, Petr A Golovach1

  • 1University of Bergen, Bergen, Norway.

Theory of Computing Systems
|February 9, 2026
PubMed
Summary
This summary is machine-generated.

This study shows that approximating Maximum Vertex-Disjoint Shortest Paths is nearly as hard as the exact problem. We prove that no o(k)-approximation exists under the gap-ETH, and no m^(1/2-ε)-approximation exists unless P=NP.

Keywords:
ETHFixed-parameter tractabilityParameterized (in)approximability

More Related Videos

Transverse Sectioning of Mature Rice Oryza sativa L. Kernels for Scanning Electron Microscopy Imaging Using Pipette Tips as Immobilization Support
05:22

Transverse Sectioning of Mature Rice Oryza sativa L. Kernels for Scanning Electron Microscopy Imaging Using Pipette Tips as Immobilization Support

Published on: January 25, 2022

4.3K
Foraging Path-length Protocol for Drosophila melanogaster Larvae
07:26

Foraging Path-length Protocol for Drosophila melanogaster Larvae

Published on: April 23, 2016

9.9K

Related Experiment Videos

Last Updated: Feb 10, 2026

Quantification of Fungal Colonization, Sporogenesis, and Production of Mycotoxins Using Kernel Bioassays
10:01

Quantification of Fungal Colonization, Sporogenesis, and Production of Mycotoxins Using Kernel Bioassays

Published on: April 23, 2012

18.7K
Transverse Sectioning of Mature Rice Oryza sativa L. Kernels for Scanning Electron Microscopy Imaging Using Pipette Tips as Immobilization Support
05:22

Transverse Sectioning of Mature Rice Oryza sativa L. Kernels for Scanning Electron Microscopy Imaging Using Pipette Tips as Immobilization Support

Published on: January 25, 2022

4.3K
Foraging Path-length Protocol for Drosophila melanogaster Larvae
07:26

Foraging Path-length Protocol for Drosophila melanogaster Larvae

Published on: April 23, 2016

9.9K

Area of Science:

  • Graph Theory and Algorithms
  • Computational Complexity
  • Approximation Algorithms

Background:

  • The Maximum Vertex-Disjoint Shortest Paths problem seeks to connect the maximum number of terminal pairs using pairwise vertex-disjoint shortest paths.
  • Recent breakthroughs have shown polynomial-time solvability for fixed k, implying a ck-approximation.
  • Understanding the limits of approximation is crucial for practical applications.

Purpose of the Study:

  • To establish the hardness of approximating the Maximum Vertex-Disjoint Shortest Paths problem.
  • To determine the best possible approximation ratios achievable in polynomial time.
  • To explore the exact complexity and kernelization bounds of the problem.

Main Methods:

  • Leveraging the gap-Exponential Time Hypothesis (gap-ETH) to prove inapproximability results.
  • Utilizing reductions from known NP-hard problems to demonstrate computational limitations.
  • Developing a simple sqrt(l)-approximation algorithm to show tightness of bounds.
  • Analyzing exact algorithms and kernelization complexity.

Main Results:

  • Assuming the gap-ETH, an o(k)-approximation in f(k)poly(n) time is excluded for any k-dependent function f.
  • An approximation ratio of m^(1/2-ε) is infeasible in polynomial time unless P=NP.
  • A tight sqrt(l)-approximation algorithm is presented, where l is the number of edges in the optimal solution.
  • The problem is solvable in 2^O(l)poly(n) time but does not admit a polynomial kernel in l.
  • It cannot be solved in 2^o(l)poly(n) time under ETH.

Conclusions:

  • The approximation algorithms for Maximum Vertex-Disjoint Shortest Paths are close to optimal, with hardness results matching known bounds.
  • The study provides a comprehensive understanding of the problem's complexity, bridging the gap between theoretical limits and practical solvability.
  • Hardness results hold even for undirected graphs with unit weights, while positive results generalize to directed graphs with arbitrary non-negative weights.