Length-bounded cuts: proper interval graphs and structural parameters

DOI10.1016/J.JCSS.2021.12.002MaRDI QIDQ2119399zbMATH OpenOpenAlexFDO

Authors Matthias Bentert, Klaus Heeger, Dušan Knop

Publication date 29 March 2022

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1910.03409

zbMATH Keywords

edge-disjoint pathsfeedback vertex numberpathwidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

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 $lambda$. The task is to find a set of edges $F$ of size at most $$ such that every $s$-$t$-path of length at most $lambda$ in $G$ contains some edge in $F$. Bazgan et al. 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 showing a dynamic-programming based polynomial-time algorithm. We strengthen the W[1]-hardness result of Dvov{r}'ak and Knop. Our reduction is shorter, seems simpler to describe, 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.

Review text

The paper studies a variant of the \textsc{Edge Cut} problem called the \textsc{Length-Bounded Cut} problem, which is the cut problem related to the variant of the \textsc{Edge Disjoint Paths} problem. The task of the \textsc{Length-Bounded Cut} problem is to find a set \(F\) of at most \(\beta\) edges such that each \(s\)-\(t\)-path of length at most \(\lambda\) in \(G\) contains some edge in \(F\), i.e., there is no \(s\)-\(t\)-path of length at most \(\lambda\) in \(G-F\). The \textsc{Length-Bounded Cut} problem is polynomially solvable for \(\lambda=|V|\) as it reduces to \textsc{Edge Cut} and also for \(\lambda\le 3\), while it is NP-hard for the remaining values \(\lambda\ge 4\). This paper studies \textsc{Length-Bounded Cut} for special graph classes and confirms a conjecture of \textit{C. Bazgan} et al. [Networks 73, No. 1, 23--37 (2019; Zbl 1407.90090)] that it can be solved in polynomial time on proper interval graphs. The authors give a dynamic-programming-based algorithm for the problem with running time \(O(n^2\cdot m)\). Regarding parameterized complexity, the authors show that the \textsc{Length-Bounded Cut} problem is W[1]-hard for the feedback vertex number and for the combined parameter pathwidth and maximum degree of the input graph \(G\). The above results imply that, assuming the Exponential Time Hypothesis, there is no \(f(k)\cdot n^{o(k)}\)-time algorithm for \textsc{Length-Bounded Cut}, where \(k\) is the pathwidth of the input graph.

Recommendations

• scientific article; zbMATH DE number 7765394
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Length-Bounded Cuts and Flows
• Approximability of 3- and 4-Hop Bounded Disjoint Paths Problems
• scientific article; zbMATH DE number 7758343
• Length-bounded cuts and flows
• Parameterized complexity of length-bounded cuts and multicuts
• Complexity of maximum cut on interval graphs
• On the maximum cardinality cut problem in proper interval graphs and related graph classes

Cites work

• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fractals for kernelization lower bounds
• Graph Classes: A Survey
• Hop-constrained node survivable network design: An application to MPLS over WDM
• scientific article; zbMATH DE number 3353312 (Why is no real title available?)
• scientific article; zbMATH DE number 7765394 (Why is no real title available?)
• Improved bounds for the unsplittable flow problem
• Integer programming formulations for the two 4-hop-constrained paths problem
• Length-bounded cuts and flows
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Maximal Flow Through a Network
• On algorithms employing treewidth for L-bounded cut problems
• On the complexity of k-SAT
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Parameterized algorithms
• Parameterized Complexity of Geodetic Set
• Parameterized complexity of length-bounded cuts and multicuts
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Which problems have strongly exponential complexity?

Cited in

(8)

• On the maximum cardinality cut problem in proper interval graphs and related graph classes
• \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• Parametrized complexity of length-bounded cuts and multi-cuts
• Grundy Distinguishes Treewidth from Pathwidth
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• A survey of parameterized algorithms and the complexity of edge modification
• Structural parameterizations of the biclique-free vertex deletion problem

This page was built for publication: Length-bounded cuts: proper interval graphs and structural parameters

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