Compression with wildcards: All induced subgraphs that are (respectively) connected, chordal, bipartite, or forests

Various algorithms have been proposed to enumerate all connected induced subgraphs of a graph \(G=(V,E)\). As a variation we enumerate all "conn-partitions", i.e. partitions \(\Pi\) of \(V\) with the property that each part of \(\Pi\) induces a connected subgraph. In another vein, we enume...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-12
Main Author: Wild, Marcel
Format: Article
Language:English
Subjects:
Algorithms
Graph theory
Polynomials
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Various algorithms have been proposed to enumerate all connected induced subgraphs of a graph \(G=(V,E)\). As a variation we enumerate all "conn-partitions", i.e. partitions \(\Pi\) of \(V\) with the property that each part of \(\Pi\) induces a connected subgraph. In another vein, we enumerate all \(X\subseteq V\) which induce a subgraph that is (respectively) chordal, bipartite, or a forest. Mentioned four algorithms, and two more, run in ouput-polynomial time (and deliver their fare in compressed fashion). Along the way we give fresh and short proofs of well-known facts about bipartite graphs and chordless cycles respectively.
ISSN:2331-8422