Assistance and interdiction problems on interval graphs

DOI10.1016/J.DAM.2023.06.046MaRDI QIDQ6094722zbMATH OpenOpenAlexFDO

Authors Hung P. Hoang, Stefan Lendl, Lasse Wulf

Publication date 14 September 2023

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

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

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)

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.

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

Cites work

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

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)