Computing the forcing spectrum of outerplanar graphs in polynomial time

The forcing number of a graph with a perfect matching \(M\) is the minimum number of edges in \(M\) whose endpoints need to be deleted, such that the remaining graph only has a single perfect matching. This number is of great interest in theoretical chemistry, since it conveys information about the...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-01
Main Authors: Gorsky, Maximilian, Kreßin, Fabian
Format: Article
Language:English
Subjects:
Algorithms
Graph theory
Graphs
Matching
Polynomials
Questions
Vertex sets
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The forcing number of a graph with a perfect matching \(M\) is the minimum number of edges in \(M\) whose endpoints need to be deleted, such that the remaining graph only has a single perfect matching. This number is of great interest in theoretical chemistry, since it conveys information about the structural properties of several interesting molecules. On the other hand, in bipartite graphs the forcing number corresponds to the famous feedback vertex set problem in digraphs. Determining the complexity of finding the smallest forcing number of a given planar graph is still a widely open and important question in this area, originally proposed by Afshani, Hatami, and Mahmoodian in 2004. We take a first step towards the resolution of this question by providing an algorithm that determines the set of all possible forcing numbers of an outerplanar graph in polynomial time. This is the first polynomial-time algorithm concerning this problem for a class of graphs of comparable or greater generality.
ISSN:2331-8422