Scholarlink

The quest to match entities within graphs is a cornerstone of graph theory, and such algorithmic approaches have been investigated for centuries. Traditionally, given a graph G, the problem is to find a maximum size matching in G. Subsequently, the goal has been to find a matching M such that the graph induced on the endpoints of the edges of M, \(G[V_M]\) , has some additional property \(\mathcal{P}\) , such as induced matching, acyclicity, connectivity, disconnectedness, etc. In this paper, we focus on the property of disconnectedness. In particular, we consider the following problem defined by Gomes et al. [TCS ’23]: given a graph G, and two positive integers k and c; we want to know if there exists a matching M of size at least k such that \(G[V_M]\) has at least c connected components? We call this the Disconnected Matching problem. We show the following results.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Parameterized Complexity of Disconnected Matchings

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Sushmita Gupta,
  • Pallavi Jain,
  • Lawqueen Kanesh,
  • Sounak Modak,
  • Saket Saurabh

摘要

The quest to match entities within graphs is a cornerstone of graph theory, and such algorithmic approaches have been investigated for centuries. Traditionally, given a graph G, the problem is to find a maximum size matching in G. Subsequently, the goal has been to find a matching M such that the graph induced on the endpoints of the edges of M, \(G[V_M]\) , has some additional property \(\mathcal{P}\) , such as induced matching, acyclicity, connectivity, disconnectedness, etc. In this paper, we focus on the property of disconnectedness. In particular, we consider the following problem defined by Gomes et al. [TCS ’23]: given a graph G, and two positive integers k and c; we want to know if there exists a matching M of size at least k such that \(G[V_M]\) has at least c connected components? We call this the Disconnected Matching problem. We show the following results.