Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth

Basic Information

• Paper ID: 2510.12552
• Title: Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
• Authors: Nicolas El Maalouly, Kostas Lakis (ETH Zurich)
• Classification: cs.DS (Data Structures and Algorithms), cs.CC (Computational Complexity)
• Publication Date: October 14, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12552

Abstract

This paper investigates two related graph-theoretic problems: Exact Matching (EM) and Top-k Perfect Matching (TkPM). The EM problem asks whether there exists a perfect matching using exactly k red edges in a red-blue edge-colored graph; the TkPM problem seeks a perfect matching that maximizes the weight sum of its k heaviest edges. While EM admits a randomized polynomial-time algorithm, deterministic algorithms exist only in special cases, making it a natural candidate for testing the P=RP hypothesis. This paper primarily studies the parameterized complexity of these problems on blown-up graphs, proposing FPT algorithms and approximation algorithms based on neighborhood diversity and bandwidth parameters.

Research Background and Motivation

Problem Significance

1. Theoretical Value: The EM problem is one of few natural problems suitable for testing the P=RP hypothesis, possessing significant computational complexity theory value
2. Algorithmic Challenge: Although randomized polynomial-time algorithms based on the Schwartz-Zippel lemma exist, no deterministic polynomial-time algorithm has been found to date
3. Practical Applications: The TkPM problem has important applications in clustering and load balancing optimization problems

Limitations of Existing Approaches

1. Algorithms on General Graphs: For general graphs, TkPM only achieves a 0.5-approximation ratio; bipartite graphs can achieve approximately 0.8
2. Parameterized Complexity: Existing FPT algorithms depend on independence number α or bipartite independence number β, which may be large on certain graph classes
3. Potential of Structured Graphs: For graphs with special structure (such as blown-up graphs), existing algorithms fail to fully exploit their structural properties

Research Motivation

The core motivation of this paper is to design more efficient algorithms by exploiting the structural properties of blown-up graphs. Blown-up graphs are obtained by replacing each vertex of the original graph with a clique or independent set, a structure common in practical applications with favorable algorithmic properties.

Core Contributions

1. FPT Algorithm: Proposes an FPT algorithm parameterized by k and neighborhood diversity γ with time complexity O((2k+γ-1 choose γ-1)f(n))
2. Approximation Algorithm: Designs a (1-ε)-approximation algorithm with time complexity O((log²k/log²(1/(1-ε)))^γ² f(n)), significantly reducing parameter dependence
3. Subexponential Algorithm: Develops a recursive algorithm for prototype graphs with bounded bandwidth with time complexity 2^O(φ²√n log² n)
4. EM Algorithm Adaptation: Adapts the recursive method to the EM problem, achieving time complexity 2^O(φ²n^(12/13) log² n)

Methodology Details

Task Definitions

Exact Matching (EM):

• Input: Red-blue edge-colored graph G and integer k
• Output: Determine whether there exists a perfect matching containing exactly k red edges

Top-k Perfect Matching (TkPM):

• Input: Edge-weighted graph G, weight function w, and integer k
• Output: Find a perfect matching M that maximizes the weight sum of its k heaviest edges

Core Concepts

Blown-up Graph

• Prototype Graph P: The initial small graph
• Blowing-up Process: Replace each vertex of P with a clique or independent set (called a blob)
• Edge Processing: Edges in the original graph become edge sets of complete bipartite graphs (called bands)

Neighborhood Diversity

The neighborhood diversity of graph G is γ if and only if vertices can be partitioned into γ sets V₁, V₂, ..., Vγ such that for any u, u' ∈ Vᵢ and any v ∉ Vᵢ, we have (u,v) ∈ E(G) ⟺ (u',v) ∈ E(G).

Algorithm 1: FPT Algorithm with Bounded Neighborhood Diversity

Core Idea

Since vertices of the same type are equivalent in neighborhood relationships, any two matchings using a fixed number of vertices of each type are equivalent in extensibility.

Type-Constrained Maximum Weight Matching (TC-MWM)

1. Problem Transformation: Transform TkPM into a maximum weight matching problem under type constraints
2. Auxiliary Graph Construction: For each type Vᵢ, add |Vᵢ|-cᵢ "killer" vertices with weight 0
3. Algorithm Flow: Run maximum weight perfect matching algorithm on the auxiliary graph

Parameter Enumeration

Enumerate all distribution schemes satisfying c₁+c₂+...+cγ=2k, with total count (2k+γ-1 choose γ-1).

Algorithm 2: Approximation Algorithm

Exponential Growth Strategy

• Rather than considering exact vertex counts for each blob, focus on edge counts for each band
• For each bᵢ, consider only values in the set A = {0, 1, ⌈α⌉, ⌈α²⌉, ..., k}
• Where α = 1/(1-ε)

Complexity Improvement

Through this strategy, the exponential impact of parameter k is reduced to polynomial level, with total enumeration count becoming O((log²k/log²(1/(1-ε)))^γ²).

Algorithm 3: Recursive Algorithm (Bounded Bandwidth)

Bandwidth Definition

The bandwidth φ(G) of graph G is the minimum integer such that there exists a vertex ordering v₁, v₂, ..., vₙ satisfying {vᵢ, vⱼ} ∈ E(G) ⟹ |i-j| ≤ φ(G).

Tight/Loose Band Classification

• Tight Band: A band containing ≥√n edges in the optimal solution
• Loose Band: A band containing <√n edges in the optimal solution
• Key Observation: The number of tight bands is ≤√n

Loose Separator

A loose separator is defined as a small separator that does not touch any tight band. Bounded bandwidth graphs guarantee the existence of multiple disjoint small separators, thus always enabling the discovery of a loose separator.

Recursive Strategy

1. Base Case: When there are too many tight bands or too few blobs, use Algorithm 1
2. Recursive Case:
   • Find a loose separator S
   • Enumerate all possible edge selections related to S (at most √n edges per band)
   • Recursively solve the separated subproblems
   • Combine subproblem solutions to obtain the global solution

Experimental Setup

Theoretical Analysis Framework

This paper primarily conducts theoretical analysis, verifying algorithm correctness and complexity bounds through mathematical proofs.

Complexity Analysis Methods

1. Induction: Used to prove correctness of recursive algorithms
2. Amortized Analysis: Analyzes recursion depth and computational cost per level
3. Parameterized Complexity Theory: Analyzes parameter dependencies of FPT algorithms

Experimental Results

Algorithm 1 Performance

• Time Complexity: O((2k+γ-1 choose γ-1)f(n)), where f(n) is polynomial
• Parameterized Characteristics: Achieves polynomial time when γ is constant
• Correctness: Guaranteed to find optimal solution through extensibility lemma

Algorithm 2 Approximation Performance

• Approximation Ratio: (1-ε)
• Time Complexity: O((log²k/log²(1/(1-ε)))^γ² f(n))
• PTAS Condition: Achieves PTAS when γ = O(√(log n/log log n))

Algorithm 3 Subexponential Performance

• Time Complexity: 2^O(φ²√n log² n)
• Subexponential Condition: Maintains subexponential complexity when φ = o(n^(1/4)/log n)
• Recursion Depth: O(log n) levels

EM Problem Adaptation Results

• Time Complexity: 2^O(φ²n^(12/13) log² n)
• Technical Adjustment: Modifies tight band threshold to n^α, where α = 12/13

Related Work

Exact Matching Problem Research

1. Papadimitriou-Yannakakis: Originally proposed the EM problem, equivalent to constrained spanning tree problems
2. Mulmuley-Vazirani-Vazirani: Provided randomized polynomial-time algorithm using the isolation lemma
3. El Maalouly et al.: Research on deterministic algorithms for special graph classes

Parameterized Algorithm Theory

1. Neighborhood Diversity: Algorithm metatheorems by Lampis et al.
2. Bandwidth Parameter: Applications in various graph problems
3. Dynamic Programming Methods: Applications on structured graphs with bounded treewidth

Top-k Optimization Problems

Similar top-k objectives have been studied in clustering and load balancing problems, but are relatively new in matching problems.

Conclusions and Discussion

Main Conclusions

1. Advantages of Structured Graphs: The structure of blown-up graphs can be effectively exploited to design better algorithms
2. Power of Parameterized Methods: Appropriate parameterization can transform difficult problems into tractable ones
3. Trade-off Between Approximation and Exactness: Sacrificing slight exactness can substantially improve algorithm efficiency

Limitations

1. Graph Structure Restrictions: Algorithms apply only to blown-up graphs, with limited effectiveness on general graphs
2. Parameter Dependence: Algorithm efficiency remains unsatisfactory when neighborhood diversity or bandwidth is large
3. Practical Performance: Theoretical complexity bounds may be overly pessimistic in practice

Future Directions

1. Other Graph Parameters: Explore algorithms based on other structural parameters (such as treewidth, pathwidth)
2. Lower Bound Research: Establish tighter complexity lower bounds
3. Practical Implementation: Develop practically usable algorithm implementations and conduct experimental evaluation

In-Depth Evaluation

Strengths

1. Theoretical Contribution: Substantial progress on an important open problem
2. Technical Innovation: Clever exploitation of blown-up graph structure and multiple separator techniques
3. Systematic Research: Complete framework from exact algorithms to approximation algorithms to subexponential algorithms
4. Rigorous Proofs: Complete and rigorous mathematical proofs

Weaknesses

1. Limited Practicality: Lacks experimental validation on real data
2. Constant Factors: Constants in theoretical analysis may be large, affecting practical efficiency
3. Graph Class Restrictions: Applies only to specific graph structures, with limited generality

Impact

1. Theoretical Value: Provides new research perspective on the P=RP problem
2. Methodological Contribution: Algorithm design techniques on blown-up graphs may apply to other problems
3. Parameterized Complexity: Enriches the content of parameterized algorithm theory

Applicable Scenarios

1. Network Design: Matching problems in networks with modular structure
2. Resource Allocation: Resource matching in hierarchical systems
3. Theoretical Research: Serves as foundational tool for studying other matching problems

References

The paper cites 17 important references covering classical works in matching theory, parameterized complexity, graph algorithms, and other fields, providing a solid theoretical foundation for the research.