Connecting Terminals and 2-Disjoint Connected Subgraphs

DOI10.1007/978-3-642-45043-3_36zbMATH Open1417.05112arXiv1301.2506OpenAlexW2159973663MaRDI QIDQ2864321FDOQ2864321

Yngve Villanger, Jan Arne Telle

Publication date: 6 December 2013

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Abstract: Given a graph $G=(V,E)$ and a set of terminal vertices $T$ we say that a superset $S$ of $T$ is $T$-connecting if $S$ induces a connected graph, and $S$ is minimal if no strict subset of $S$ is $T$-connecting. In this paper we prove that there are at most $|VsetminusT|choose|T|-2cdot{3}^{frac|VsetminusT|3}$ minimal $T$-connecting sets when $|T|leqn/3$ and that these can be enumerated within a polynomial factor of this bound. This generalizes the algorithm for enumerating all induced paths between a pair of vertices, corresponding to the case $|T|=2$. We apply our enumeration algorithm to solve the {sc 2-Disjoint Connected Subgraphs} problem in time $O^{*}(1.7804^n)$, improving on the recent $O^{*}(1.933^n)$ algorithm of Cygan et al. 2012 LATIN paper.

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

Recommendations

• Algebraic connectivity and disjoint vertex subsets of graphs
• On two-connected subgraph polytopes
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• Proper connection number 2, connectivity, and forbidden subgraphs
• Graphs with disjoint \(2\)-dominating sets
• Disjoint sub(di)graphs in digraphs
• Connected domination subdivision numbers of graphs
• Subgraphs decomposable into two trees and \(k\)-edge-connected subgraphs
• Non-separating subgraphs in highly connected graphs
• Connectivity, graph minors, and subgraph multiplicity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Connectivity (05C40)

Cited In (11)

• Title not available (Why is that?)
• Enumeration of minimal tropical connected sets
• Path Contraction Faster Than 2^n
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating Minimal Tropical Connected Sets
• Contracting bipartite graphs to paths and cycles
• Path Contraction Faster than $2^n$
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• Contracting bipartite graphs to paths and cycles
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs

This page was built for publication: Connecting Terminals and 2-Disjoint Connected Subgraphs

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