As two fundamental problems, graph cuts and graph matching have been investigated over decades, resulting in vast literature in these two topics respectively. However the way of jointly applying and solving graph cuts and matching receives few attention. In this paper, we first formalize the problem of simultaneously cutting a graph into two partitions i.e. graph cuts and establishing their correspondence i.e. graph matching. Then we develop an optimization algorithm by updating matching and cutting alternatively, provided with theoretical analysis. The efficacy of our algorithm is verified on both synthetic dataset and real-world images containing similar regions or structures.
Graph partition and cuts have been a long-standing research topic. The general idea is to obtain high similarity among nodes within partition and low across partitions. The minimum weight @math -cut problem aims to divide the graph into @math disjoint non-empty partitions such that the cut metric is minimized, with no balance constraint enforced. As shown in @cite_27 , this problem can be solved optimally in @math when @math is given. Without knowing @math , the problem becomes NP-complete. When the (roughly) equal size constraint is involved, early work have proved it is NP-complete. Extended theoretical study is presented in @cite_5 . To limit the scope, we focus in this paper on two-cut partition and forgo a more generalized treatment of (relaxed) @math -cut problem for future study.
@cite_5 @cite_27
2113513143 2086565575
In this paper we consider the problem of (k, υ)-balanced graph partitioning - dividing the vertices of a graph into k almost equal size components (each of size less than υ • n k) so that the capacity of edges between different components is minimized. This problem is a natural generalization of several other problems such as minimum bisection, which is the (2,1)-balanced partitioning problem. We present a bicriteria polynomial time approximation algorithm with an O(log2n)-approximation for any constant υ > 1. For υ = 1 we show that no polytime approximation algorithm can guarantee a finite approximation ratio unless P=NP. Previous work has only considered the (k, υ)-balanced partitioning problem for υ ≥ 2. The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for arbitrary k and its version involving fixing a vertex in each component is NP hard even for k=3. A polynomial algorithm for the case of a fixed k is presented. >