5
$\begingroup$

Given an undirected graph and an integer $B$, we ask to find the minimum set of nodes whose removal partitions the generated graph into connected components, each having at most $B$ nodes.

We can consider this to be a generalization of the minimum vertex cover, where $B=1$, since deleting the vertex cover set of a graph $G$ gives an independent set, i.e. partition G on connected component of no more than 1 node.

  1. Are there similar problems in literature?

  2. This problem is NP-complete on general graphs. Which known problem on graph theory help to study its (in)approximation?

  3. I want to study it on chordal graphs. For which cases it may be polynomial and for which it is NP-complete?

$\endgroup$
  • 2
    $\begingroup$ This problem is definitely polynomial on proper interval graphs (a.k.a. linear interval graphs) for fixed $B$. Intuitively I guess that its complexity on chordal graphs would be the same as the complexity of the integer-weighted version on trees, but maybe not. $\endgroup$ – Andrew D. King Dec 18 '13 at 2:14
  • 1
    $\begingroup$ Graph separators where $B = \varepsilon n$? $\endgroup$ – Pratik Deoghare Dec 18 '13 at 12:30
  • $\begingroup$ Thaks Andrew...The integer-weighted version on trees ?!! that means that the nodes of the graph, which is a tree, have integer weight. If it is the case, so the problem asks for deleting the set of nodes with the minimum total weight such that the connected component in the generated graph are no more than B nodes. My question is: the problem in this case is of the same complexity as for the general chordal graphs in which case: node weight = 1 or weight > 1 ? $\endgroup$ – lamoincyloj Dec 18 '13 at 18:40
  • $\begingroup$ Thaks Pratik...Yes, it seems to be the same problem, so i have to search if there are results, in literature, for Graph separator problem where B=εn on chordal graphs ?! $\endgroup$ – lamoincyloj Dec 18 '13 at 19:06
  • $\begingroup$ For fixed $B$, this is an MSO definable optimization problem and hence solvable in linear time on graphs of bounded tree-width or bounded clique width. For fixed $k$ and $B$ (decide whether the set to be deleted has size at most $k$) this is an FO definable decision problem and hence solvable in almost linear time on nowhere dense classes of graphs (in particular bounded tree-width, planar, excluded minor, etc). $\endgroup$ – Sebastian Siebertz Dec 27 '13 at 20:00
4
$\begingroup$

The problem that you are describing seems to be a variation of a critical node detection problem. In general, most critical node detection problems aim to identify a set of at most $B$ nodes (or if you are considering the weighted case, a set of nodes with a weighted sum of at most $B$ ) whose deletion results in the maximum disruption of a given property of the graph. In many of the papers that you can find in the literature, the property that is being disrupted often represents a measure of how well connected the residual graph is. For instance, such property may account for the total number of node pairs that remain connected, the number of maximally connected components, or the size of the largest connected component after the critical nodes are removed (you can also search for node interdiction or node blocker problems for other versions). Some references are: Arulslevan et al [1], Shen et al [2], Di Summa et al [3], Addis et al [4], Oosten et al [5] among others. There is also a very short survey [7] on some of these problems. Although, several other papers have been published after that chapter was in press.

These problems are indeed NP-Hard for general graphs. However, there are some polynomially solvable cases (trees and series-parallel graphs, see [3], [4], and [6]).

For the version that you mention, which is somehow a complement of the above problems (instead of maximizing the disruption, you minimize the number of critical nodes to achieve the desired disruption) there is an article that proves inapproximability for the version of the problem in which the disrupted property is the total number of pairwise connections [8]. Your intuition is correct, vertex cover is commonly used to as a steeping stone.

If have some other questions or ideas, you can send me an email. This is one of my research interests. I will be happy to provide you with more ideas and to collaborate.

There is also something to keep in mind. These problems lay in the intersection of several fields, so there may be some similar versions with different names (I have found problems that belong to the same family, like graph separators, pivotal vertices, and articulation points).

[1]: Detecting critical nodes in sparse graphs

[2]: Exact interdiction models and algorithms for disconnecting networks via node deletions

[3]: Complexity of the critical node problem over trees

[4]: Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth

[5]: Disconnecting graphs by removing vertices: A polyhedral approach

[6]: Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs

[7]: Selected Topics in Critical Element Detection

[8]: On New Approaches of Assessing Network Vulnerability: Hardness and Approximation

$\endgroup$
  • 2
    $\begingroup$ That looks like a pretty comprehensive list of references but could you please give full details of the cited papers. At the very least, give the authors. $\endgroup$ – David Richerby Dec 19 '13 at 8:13
  • $\begingroup$ Thanks totaUnimodular. You presented the background for similar problems. $\endgroup$ – lamoincyloj Dec 19 '13 at 19:27
  • $\begingroup$ Sorry, I was going to provide the authors and the links, but it didn't let me add more than 2 hyperlinks. I guess that this time a google search with the titles would do. Sorry. $\endgroup$ – totalUnimodular Dec 19 '13 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.