8
$\begingroup$

Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component.

I assume for large $n = |V|$ and large $k$ the problem is difficult (NP-hard), but I am interested in small values of $k$ ($k \in \{1, 2, 3, 4\}$).

For $k = 1$, I think it is possible to find best vertex $\{v^*_1\}$ to remove by performing single depth-first-search of the graph (i.e., checking articulation points).

For $k = 2$, it would be possible to find best vertices $\{v^*_1, v^*_2\}$ by performing $n$ depth-first searches (each of them for graph $G_i = G / \{v_i\}$). A similar approach could be applied in the case $k > 2$.

I wonder if there is any better solution than that.

(Related: counting the minimum number of vertices without necessarily enumerating them)

$\endgroup$
  • $\begingroup$ Well, it generalizes vertex cover which asks for vertices $S = \{v_1, \dots, v_k\}$ such that $G-S$ has a largest component of singleton size. $\endgroup$ – Pål GD Jun 21 '13 at 9:18
  • $\begingroup$ Ps., a parameterized algorithm is an FPT algorithm if it runs in time $f(k) \cdot n^c$ for some $c$, and an algorithm is an XP algorithm if it runs in $n^{f(k)}$ time. $\endgroup$ – Pål GD Jun 21 '13 at 9:19
  • $\begingroup$ Can you come with some more information? I'm quite interested in the background of this problem. $\endgroup$ – Pål GD Jun 26 '13 at 10:03
  • $\begingroup$ I faced this problem while looking for max common connected subgraph of two graphs. Check the comments in your answer :) $\endgroup$ – MindaugasK Jul 9 '13 at 8:40
9
$\begingroup$

The problem you are describing is known as Component Order Connectivity in the field of vulnerability measures of graphs. The decision version of the problem is as follows:

Component Order Connectivity:

Input: Graph $G = (V,E)$, integers $k$ and $\ell$

Question: Does there exist a set of vertices $X \subseteq V$ of size at most $k$ such that the size of the largest component of $G - X$ is at most $\ell$?

The problem is obviously NP-complete since it generalizes vertex cover; the case when $\ell=1$ is vertex cover. Hence the problem cannot be fixed parameter tractable when parameterized by $\ell$ (unless $FPT = W[1]$). The problem is also known to be $W[1]$-hard when parameterized by $k$. Hence, we have to resort to algorithms with an exponential running time in $k+\ell$.

Very interesting question. For input $G,k,\ell$, a brute force approach would be:

branching(G,k,l):
    Find a connected set of vertices D of G of size l+1
    if no such D exists:
            return True // no component of size > l
    for v in D:
        if branching(G-v,k-1,l):
            return True
    return False

The algorithm runs in time $(\ell + 1)^k \cdot n^2$.

Observe that any yes instance $G,k,\ell$ of the problem has treewidth, and indeed pathwidth at most $k+\ell$. This can be observed by seeing that taking a deletion set $X$ of size at most $k$ yields a graph $G-X$ where every connected component has size at most $\ell$. Hence, a valid path decomposition is simply to construct one bag for each of the components in $G-X$ and then add all of $X$ to every bag. It follows that any yes instance has $|E(G)| \leq n(k+\ell)$.

A related problem has been studied in the past under the name Graph Integrity, or Vertex Integrity to distinguish the vertex deletion version and the edge deletion version:

Vertex Integrity:

Input: Graph $G = (V,E)$, integer $p$

Question: Does there exist a set of vertices $X \subseteq V$ such that $|X| + \max_{D \in cc(G-X)}|D| \leq p$?

That is, the sum of the deletion set and the size of the maximal component should be minimized. This problem is also NP-hard. See, e.g.,

  • Clark, L.H., Entringer, R.C., Fellows, M.R.: Computational complexity of integrity. J. Combin. Math. Combin. Comput 2, 179–191 (1987)
  • Fellows, M., Stueckle, S.: The immersion order, forbidden subgraphs and the complexity of network integrity. J. Combin. Math. Combin. Comput 6, 23–32 (1989)
$\endgroup$
  • $\begingroup$ Well, actually I am working with chemical graphs, which are planar with very high probability. $\endgroup$ – MindaugasK Jun 21 '13 at 13:09
  • $\begingroup$ Then you can check out the planar separator theorem (Lipton and Tarjan) which says that you can find balanced $O(\sqrt{n})$ separators. $\endgroup$ – Pål GD Jun 21 '13 at 14:21
  • $\begingroup$ I solved this problem as I suggested in the question, by doing $|V|+1$-depth-first-searches (one for finding articulation points, $|V|$ for finding pairs of articulation points). Max component of chemical graphs (molecules), which are sparse, can often be made sufficiently small by deleting only 1-2 atoms (vertices) (with rare exceptions). I wasn't seeking optimal solution, I just wanted 1, 2 or 3 atoms, whose removal would 'cut' the molecule into small peaces, and DFS was sufficient. $\endgroup$ – MindaugasK Jul 9 '13 at 8:19
  • $\begingroup$ Actually the problem I stated in the question was not exactly the one I wanted to solve. Each vertex had also weights associated with it. Thus, I wanted to pick vertices, which not only result in small largest component, but which sum of weight is also small. $\endgroup$ – MindaugasK Jul 9 '13 at 8:27
  • $\begingroup$ This in itself was a subproblem of another problem: find max common connected substructure of 2 given molecules (find max common connected induced subgraph of 2 graphs). After mapping single atom from one molecule with all possible mappings from another one, you can remove that atom from consideration, and it is nice if it 'cuts' the molecule. Maybe I should state this as another question. $\endgroup$ – MindaugasK Jul 9 '13 at 8:28

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.