Back to Search
Start Over
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
- Publication Year :
- 2019
-
Abstract
- In the presented paper, we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of edges of size at most β such that every s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [Networks, 2019] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph G is a proper interval graph. We confirm this conjecture by providing a dynamic-programming based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [Algorithmica, 2018] for Length-Bounded Cut parameterized by pathwidth. Our reduction is shorter, and the target of the reduction has stronger structural properties. Consequently, we give W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.<br />LIPIcs, Vol. 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020), pages 36:1-36:14
- Subjects :
- feedback vertex number
FOS: Computer and information sciences
Computer Networks and Communications
Mathematics of computing → Graph algorithms
Applied Mathematics
pathwidth
Mathematics of computing → Combinatorial optimization
G.2.2
Theoretical Computer Science
Computational Theory and Mathematics
Computer Science - Data Structures and Algorithms
Theory of computation → Dynamic programming
Theory of computation → Parameterized complexity and exact algorithms
Data Structures and Algorithms (cs.DS)
Edge-disjoint paths
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....d9801a333b43ba374424a769ec94b977