Assistance and interdiction problems on interval graphs

DOI10.1016/J.DAM.2023.06.046zbMATH Open1521.05191arXiv2107.14550OpenAlexW3187972231MaRDI QIDQ6094722FDOQ6094722

Authors: Hung P. Hoang, Stefan Lendl, Lasse Wulf 

Publication date: 14 September 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We introduce a novel framework of graph modifications specific to interval graphs. We study interdiction problems with respect to these graph modifications. Given a list of original intervals, each interval has a replacement interval such that either the replacement contains the original, or the original contains the replacement. The interdictor is allowed to replace up to $k$ original intervals with their replacements. Using this framework we also study the contrary of interdiction problems which we call assistance problems. We study these problems for the independence number, the clique number, shortest paths, and the scattering number. We obtain polynomial time algorithms for most of the studied problems. Via easy reductions, it follows that on interval graphs, the most vital nodes problem with respect to shortest path, independence number and Hamiltonicity can be solved in polynomial time.

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

Recommendations

• Interdiction problems on planar graphs
• Linear recognition of almost interval graphs
• Shiftable intervals
• Interdiction problems on planar graphs
• On the independent set interdiction problem

zbMATH Keywords

interval graphsnetwork interdictiondeletion blockersmost vital nodes problemmost vital vertexvertex blockers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Communication networks in operations research (90B18)

Cites Work

• The node-deletion problem for hereditary properties is NP-complete
• Algorithmic graph theory and perfect graphs
• HAMILTONian circuits in chordal bipartite graphs
• Most vital links and nodes in weighted networks
• The most vital nodes with respect to independent set and vertex cover
• Minimum vertex blocker clique problem
• On short paths interdiction problems: Total and node-wise limited interdiction
• Tough graphs and Hamiltonian circuits.
• On a class of posets and the corresponding comparability graphs
• The critical node detection problem in networks: a survey
• Length-bounded cuts and flows
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• Approximability and parameterized complexity of multicover by \(c\)-intervals
• 1-tough cocomparability graphs are hamiltonian
• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
• Exact algorithms for the minimum cost vertex blocker clique problem
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Minimum interval cover and its application to genome sequencing

Cited In (2)

• On blockers and transversals of maximum independent sets in co-comparability graphs
• Interdiction problems on planar graphs

This page was built for publication: Assistance and interdiction problems on interval graphs

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