We consider problems of finding a maximum size/weight t-matching without forbidden subgraphs in an undirected graph G with the maximum degree bounded by \(t+1\) , where t is an integer greater than 2. A t-matching is a subset of edges such that each vertex is incident to at most t edges of the subset. Depending on the variant, forbidden subgraphs denote certain subsets of t-regular complete partite subgraphs of G. A graph is complete partite if there exists a partition of its vertex set such that every pair of vertices from different sets is connected by an edge and vertices from the same set form an independent set. A clique \(K_{t+1}\) and a bipartite clique \(K_{t,t}\) are examples of complete partite graphs. These problems are natural generalizations of the triangle-free and square-free 2-matching problems in subcubic graphs. In the weighted setting we assume that the weights of edges of G are vertex-induced on every forbidden subgraph. We present simple and fast combinatorial algorithms for these problems. The presented algorithms are the first ones for the weighted versions, and for the unweighted ones, are faster than those known previously. Additionally, the running times of our algorithms are independent of t. Our approach relies on the use of gadgets with so-called half-edges. A half-edge of edge e is, informally speaking, a half of e containing exactly one of its endpoints.

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

Clique-Free t-Matchings in Degree-Bounded Graphs

  • Katarzyna Paluch,
  • Mateusz Wasylkiewicz

摘要

We consider problems of finding a maximum size/weight t-matching without forbidden subgraphs in an undirected graph G with the maximum degree bounded by \(t+1\) , where t is an integer greater than 2. A t-matching is a subset of edges such that each vertex is incident to at most t edges of the subset. Depending on the variant, forbidden subgraphs denote certain subsets of t-regular complete partite subgraphs of G. A graph is complete partite if there exists a partition of its vertex set such that every pair of vertices from different sets is connected by an edge and vertices from the same set form an independent set. A clique \(K_{t+1}\) and a bipartite clique \(K_{t,t}\) are examples of complete partite graphs. These problems are natural generalizations of the triangle-free and square-free 2-matching problems in subcubic graphs. In the weighted setting we assume that the weights of edges of G are vertex-induced on every forbidden subgraph. We present simple and fast combinatorial algorithms for these problems. The presented algorithms are the first ones for the weighted versions, and for the unweighted ones, are faster than those known previously. Additionally, the running times of our algorithms are independent of t. Our approach relies on the use of gadgets with so-called half-edges. A half-edge of edge e is, informally speaking, a half of e containing exactly one of its endpoints.