Publication:727981

DOI10.1007/978-3-319-13075-0_23zbMath1355.68115arXiv1403.6331OpenAlexW2460257212MaRDI QIDQ727981

D. Kharzeev, Pål Grønås Drange, Markus Sortland Dregi, Pim van 't Hof

Publication date: 21 December 2016

Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)

Abstract: The Weighted Vertex Integrity (wVI) problem takes as input an $n$-vertex graph $G$, a weight function $w:V(G) omathbb{N}$, and an integer $p$. The task is to decide if there exists a set $Xsubseteq V(G)$ such that the weight of $X$ plus the weight of a heaviest component of $G-X$ is at most $p$. Among other results, we prove that: (1) wVI is NP-complete on co-comparability graphs, even if each vertex has weight $1$; (2) wVI can be solved in $O(p^{p+1}n)$ time; (3) wVI admits a kernel with at most $p^3$ vertices. Result (1) refutes a conjecture by Ray and Deogun and answers an open question by Ray et al. It also complements a result by Kratsch et al., stating that the unweighted version of the problem can be solved in polynomial time on co-comparability graphs of bounded dimension, provided that an intersection model of the input graph is given as part of the input. An instance of the Weighted Component Order Connectivity (wCOC) problem consists of an $n$-vertex graph $G$, a weight function $w:V(G) o mathbb{N}$, and two integers $k$ and $l$, and the task is to decide if there exists a set $Xsubseteq V(G)$ such that the weight of $X$ is at most $k$ and the weight of a heaviest component of $G-X$ is at most $l$. In some sense, the wCOC problem can be seen as a refined version of the wVI problem. We prove, among other results, that: (4) wCOC can be solved in $O(min{k,l}cdot n^3)$ time on interval graphs, while the unweighted version can be solved in $O(n^2)$ time on this graph class; (5) wCOC is W[1]-hard on split graphs when parameterized by $k$ or by $l$; (6) wCOC can be solved in $2^{O(klog l)} n$ time; (7) wCOC admits a kernel with at most $kl(k+l)+k$ vertices. We also show that result (6) is essentially tight by proving that wCOC cannot be solved in $2^{o(k log l)}n^{O(1)}$ time, unless the ETH fails.

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

zbMATH Keywords

complexitygraph algorithmsparameterized complexitypreprocessinggraph vulnerability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Cites Work

• On the computational complexity of vertex integrity and component order connectivity
• Equitable colorings of bounded treewidth graphs
• The clique-separator graph for chordal graphs
• Comparability graphs and intersection graphs
• A survey of integrity
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Counting clique trees and computing perfect elimination schemes in parallel
• A partial k-arboretum of graphs with bounded treewidth
• Measuring the vulnerability for classes of intersection graphs
• The toughness of split graphs
• Which problems have strongly exponential complexity?
• Graph Classes: A Survey
• The k-Separator Problem
• Vulnerability parameters of split graphs
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

Related Items (36)

Linear kernels for separating a graph into components of bounded size ⋮ Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ Network Elicitation in Adversarial Environment ⋮ Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ Component order connectivity in directed graphs ⋮ The vertex attack tolerance of complex networks ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Parameterized complexity of multicut in weighted trees ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Extended MSO model checking via small vertex integrity ⋮ Parameterized Complexity of Safe Set ⋮ Assigning times to minimise reachability in temporal graphs ⋮ Faster parameterized algorithms for two vertex deletion problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ Network majority on tree topological network ⋮ The critical node detection problem in networks: a survey ⋮ Parameterized complexity of critical node cuts ⋮ Slightly Superexponential Parameterized Problems ⋮ Component order connectivity in directed graphs ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Domination and Cut Problems on Chordal Graphs with Bounded Leafage ⋮ On Structural Parameterizations of the Harmless Set Problem ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ On the computational complexity of vertex integrity and component order connectivity ⋮ Structural parameterizations of vertex integrity (best paper) ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Unnamed Item ⋮ Structural parameterizations of vertex integrity ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Parameterized algorithms for generalizations of directed feedback vertex set ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Unnamed Item

This page was built for publication: On the computational complexity of vertex integrity and component order connectivity