Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles

1. Maxim A. Babenko. Improved algorithms for even factors and square-free simple bmatchings. Algorithmica, 64(3):362–383, 2012. doi:10.1007/s00453-012-9642-6.

2. Krist´

of B´

erczi. The triangle-free 2-matching polytope of subcubic graphs. Technical

Report TR-2012-2, Egerv´

ary Research Group, 2012.

3. Krist´

of B´

erczi and Yusuke Kobayashi. An algorithm for (n − 3)-connectivity augmentation problem: Jump system approach. Journal of Combinatorial Theory, Series B,

102(3):565–587, 2012. doi:10.1016/j.jctb.2011.08.007.

4. Krist´

of B´

erczi and L´

aszl´

o A. V´

egh. Restricted b-matchings in degree-bounded graphs.

In Integer Programming and Combinatorial Optimization, pages 43–56. Springer Berlin

Heidelberg, 2010. doi:10.1007/978-3-642-13036-6_4.

5. Michele Conforti, G´

erard Cornu´

ejols, and Giacomo Zambelli. Extended formulations in

combinatorial optimization. 4OR, 8(1):1–48, 2010. doi:10.1007/s10288-010-0122-z.

6. G´

erard Cornu´

ejols and William Pulleyblank. A matching problem with side conditions.

Discrete Mathematics, 29(2):135–159, 1980. doi:10.1016/0012-365x(80)90002-3.

7. G´

erard Cornuejols and William R. Pulleyblank. Perfect triangle-free 2-matchings. In

Mathematical Programming Studies, pages 1–7. Springer Berlin Heidelberg, 1980. doi:

10.1007/bfb0120901.

8. William H. Cunningham. Matching, matroids, and extensions. Mathematical Programming, 91(3):515–542, 2002. doi:10.1007/s101070100256.

9. Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of

Research of the National Bureau of Standards B, 69:125–130, 1965.

10. Andr´

as Frank. Restricted t-matchings in bipartite graphs. Discrete Applied Mathematics, 131(2):337–346, 2003. doi:10.1016/s0166-218x(02)00461-4.

11. Martin Gr¨

otschel, L´

aszlo Lov´

asz, and Alexander Schrijver. Geometric Algorithms and

Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer,

1988.

12. David Hartvigsen. Extensions of Matching Theory. PhD thesis, Carnegie Mellon University, 1984.

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

20

Yusuke Kobayashi

13. David Hartvigsen. The square-free 2-factor problem in bipartite graphs. In Integer Programming and Combinatorial Optimization, pages 234–241. Springer Berlin Heidelberg,

1999. doi:10.1007/3-540-48777-8_18.

14. David Hartvigsen. Finding maximum square-free 2-matchings in bipartite graphs. Journal of Combinatorial Theory, Series B, 96(5):693–705, 2006. doi:10.1016/j.jctb.

2006.01.004.

15. David Hartvigsen and Yanjun Li. Polyhedron of triangle-free simple 2-matchings in

subcubic graphs. Mathematical Programming, 138(1-2):43–82, 2012. doi:10.1007/

s10107-012-0516-0.

16. Satoru Iwata and Yusuke Kobayashi. A weighted linear matroid parity algorithm. In

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing STOC 2017, pages 264–276. ACM Press, 2017. doi:10.1145/3055399.3055436.

17. Volker Kaibel. Extended formulations in combinatorial optimization. Technical report,

arXiv:1104.1023, 2011.

18. Zolt´

an Kir´

aly. C4 –free 2-factors in bipartite graphs. Technical Report TR-2012-2,

Egerv´

ary Research Group, 1999.

19. Yusuke Kobayashi. A simple algorithm for finding a maximum triangle-free 2-matching

in subcubic graphs. Discrete Optimization, 7(4):197–202, 2010. doi:10.1016/j.disopt.

2010.04.001.

20. Yusuke Kobayashi. Triangle-free 2-matchings and M-concave functions on jump systems.

Discrete Applied Mathematics, 175:35–42, 2014. doi:10.1016/j.dam.2014.05.016.

21. Yusuke Kobayashi. Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles. In Integer Programming and Combinatorial Optimization, pages 280–293.

Springer International Publishing, 2020. doi:10.1007/978-3-030-45771-6_22.

22. Yusuke Kobayashi, J´

acint Szab´

o, and Kenjiro Takazawa. A proof of Cunningham’s

conjecture on restricted subgraphs and jump systems. Journal of Combinatorial Theory,

Series B, 102(4):948–966, 2012. doi:10.1016/j.jctb.2012.03.003.

23. Adam N. Letchford, Gerhard Reinelt, and Dirk Oliver Theis. Odd minimum cut sets

and b-matchings revisited. SIAM Journal on Discrete Mathematics, 22(4):1480–1487,

2008. doi:10.1137/060664793.

24. M´

arton Makai. On maximum cost Kt,t -free t-matchings of bipartite graphs. SIAM

Journal on Discrete Mathematics, 21(2):349–360, 2007. doi:10.1137/060652282.

25. Yunsun Nam. Matching theory: subgraphs with degree constraints and other properties.

PhD thesis, University of British Columbia, 1994.

26. Manfred W. Padberg and M. R. Rao. Odd minimum cut-sets and b-matchings. Mathematics of Operations Research, 7(1):67–80, 1982.

27. Gyula Pap.

Combinatorial algorithms for matchings, even factors and squarefree 2-factors.

Mathematical Programming, 110(1):57–69, 2007.

doi:10.1007/

s10107-006-0053-9.

28. Kenjiro Takazawa. A weighted Kt,t -free t-factor algorithm for bipartite graphs. Mathematics of Operations Research, 34(2):351–362, 2009. doi:10.1287/moor.1080.0365.

29. Kenjiro Takazawa. Decomposition theorems for square-free 2-matchings in bipartite

graphs. Discrete Applied Mathematics, 233:215–223, 2017. doi:10.1016/j.dam.2017.

07.035.

30. Kenjiro Takazawa. Excluded t-factors in bipartite graphs: A unified framework for

nonbipartite matchings and restricted 2-matchings. In Integer Programming and

Combinatorial Optimization, pages 430–441. Springer International Publishing, 2017.

doi:10.1007/978-3-319-59250-3_35.

31. Kenjiro Takazawa. Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs. Discrete Optimization, 26:26–40, 2017. doi:10.1016/j.disopt.2017.

05.003.

A Proof of Lemma 5

By symmetry, it suffices to consider (G1 , b1 , T1 ). Since the tightness of (10) for (S ∗ , F0∗ , F1∗ )

implies that x1 (δG1 (r)) = 1, we can easily see that (x1 , y1 ) satisfies (1), (2), (4)–(7). In what

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

Weighted Triangle-free 2-matching Problem

21

follows, we consider

(10) for

P(x1 , y1 ) in (G1 , b1 , T1 ). For edge sets F0 , F1 ⊆ E1 , we denote

g(F00 , F10 ) = e∈F 0 x1 (e)+ e∈F 0 (1−x1 (e)) to simplify the notation. For (S 0 , F00 , F10 ) ∈ F1 ,

let h(S 0 , F00 , F10 ) denote the left-hand side of (10). To derive a contradiction, let (S 0 , F00 , F10 ) ∈

F1 be a minimizer of h(S , F0 , F1 ) and assume that h(S 0 , F00 , F10 ) < 1. By changing the roles

of S 0 and V 0 \ S 0 if necessary, we may assume that r 6∈ S 0 .

For T ∈ TS+∗ , let v1 , v2 , v3 , α, β, and γ be as in Figures 7–10. Let G0T = (VT0 , ET0 ) be

the subgraph of G1 corresponding to T , that is, the subgraph induced by {r, p1 , p2 , v2 , v3 }

(Figure 7), {r, p3 , v1 } (Figure 8), {r, p1 , p2 , p3 , v2 , v3 } (Figure 9), or {r, p4 , v1 } (Figure 10).

Let Sˆ = S 0 ∩ (VT0 \ {v1 , v2 , v3 }), Fˆ0 = F00 ∩ ET0 , and Fˆ1 = F10 ∩ ET0 .

We show the following properties (P1)–(P9) in Section A.1, and show that (x1 , y1 )

satisfies (10) by using these properties in Section A.2.

ˆ + |Fˆ1 | is even.

(P1) If T is of type (A) or (B) and v2 , v3 6∈ S 0 , then b1 (S)

ˆ + |Fˆ1 | is even, then g(Fˆ0 , Fˆ1 ) ≥ min{x(α) +

(P2) If T is of type (A), v2 , v3 ∈ S 0 , and b1 (S)

x(γ), 2 − x(α) − x(γ) − 2yβ }.

ˆ + |Fˆ1 | is even, then g(Fˆ0 , Fˆ1 ) ≥ yα + yγ +

(P3) If T is of type (B), v2 , v3 ∈ S 0 , and b1 (S)

yαβ + yβγ .

ˆ + |Fˆ1 | is odd, then g(Fˆ0 , Fˆ1 ) ≥

(P4) If T is of type (A) or (B), v2 , v3 ∈ S 0 , and b1 (S)

y∅ + yβ + yαγ .

ˆ + |Fˆ1 | is even, then g(Fˆ0 , Fˆ1 ) ≥

(P5) If T is of type (A) or (B), v2 ∈ S 0 , v3 6∈ S 0 , and b1 (S)

min{x(α) + x(β), 2 − x(α) − x(β) − 2yγ }.

ˆ + |Fˆ1 | is odd, then g(Fˆ0 , Fˆ1 ) ≥

(P6) If T is of type (A) or (B), v2 ∈ S 0 , v3 6∈ S 0 , and b1 (S)

y∅ + yγ + yαβ .

ˆ + |Fˆ1 | is even.

(P7) If T is of type (A’) or type (B’) and v1 6∈ S 0 , then b1 (S)

ˆ + |Fˆ1 | is even, then g(Fˆ0 , Fˆ1 ) =

(P8) If T is of type (A’) or type (B’), v1 ∈ S 0 , and b1 (S)

min{x(α) + x(γ), 2 − x(α) − x(γ) − 2yβ }.

ˆ + |Fˆ1 | is odd, then g(Fˆ0 , Fˆ1 ) =

(P9) If T is of type (A’) or type (B’), v1 ∈ S 0 , and b1 (S)

y∅ + yβ + yαγ .

Note that each T ∈ TS+∗ satisfies exactly one of (P1)–(P9) by changing the labels of v2

and v3 if necessary.

A.1 Proofs of (P1)–(P9)

A.1.1 When T is of type (A)

We first consider the case when T is of type (A).

ˆ + |Fˆ1 | is odd, then

Proof of (P1). Suppose that T is of type (A) and v2 , v3 6∈ S 0 . If b1 (S)

either p1 ∈ Sˆ and |Fˆ1 ∩ δG1 (p1 )| is even or p2 ∈ Sˆ and |Fˆ1 ∩ δG1 (p2 )| is even. In the former

case, h(S 0 , F00 , F10 ) ≥ min{x1 (e1 ) + x1 (e5 ), 2 − x1 (e1 ) − x1 (e5 )} = 1, which is a contradiction.

ˆ + |Fˆ1 | is even.

The same argument can be applied to the latter case. Therefore, b1 (S)

ˆ + |Fˆ1 | is even. If

Proof of (P2). Suppose that T is of type (A), v2 , v3 ∈ S 0 , and b1 (S)

p1 6∈ S 0 , then we define (S 00 , F000 , F100 ) ∈ F1 as (S 00 , F000 , F100 ) = (S 0 ∪{p1 }, F00 \{e5 }, F10 ∪{e1 }) if

e5 ∈ F00 and (S 00 , F000 , F100 ) = (S 0 ∪{p1 }, F00 ∪{e1 }, F10 \{e5 }) if e5 ∈ F10 . Since h(S 00 , F000 , F100 ) =

h(S 0 , F00 , F10 ) holds, by replacing (S 0 , F00 , F10 ) with (S 00 , F000 , F100 ), we may assume that p1 ∈

S 0 . Similarly, we may assume that p2 ∈ S 0 , which implies that Sˆ = {p1 , p2 }, Fˆ0 ∪ Fˆ1 =

{e1 , e2 , e3 , e4 }, and |Fˆ1 | is even. Then, g(Fˆ0 , Fˆ1 ) ≥ min{x(α) + x(γ), 2 − x(α) − x(γ) − 2yβ }

by the following case analysis.

– If Fˆ1 = ∅, then g(Fˆ0 , Fˆ1 ) = x1 (e1 ) + x1 (e2 ) + x1 (e3 ) + x1 (e4 ) = 2 − x(α) − x(γ) − 2yβ .

– If |Fˆ1 | ≥ 2, then g(Fˆ0 , Fˆ1 ) ≥ 2−(x1 (e1 )+x1 (e2 )+x1 (e3 )+x1 (e4 )) = x(α)+x(γ)+2yβ ≥

x(α) + x(γ).

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

22

Yusuke Kobayashi

ˆ + |Fˆ1 | is odd. In the

Proof of (P4). Suppose that T is of type (A), v2 , v3 ∈ S 0 , and b1 (S)

same way as (P2), we may assume that Sˆ = {p1 , p2 }, Fˆ0 ∪ Fˆ1 = {e1 , e2 , e3 , e4 }, and |Fˆ1 | is

odd. Then, g(Fˆ0 , Fˆ1 ) ≥ y∅ + yβ + yαγ by the following case analysis and by the symmetry

of v2 and v3 .

– If |Fˆ1 | = 3, then g(Fˆ0 , Fˆ1 ) ≥ 3 − (x1 (e1 ) + x1 (e2 ) + x1 (e3 ) + x1 (e4 )) ≥ 1 ≥ y∅ + yβ + yαγ .

– If Fˆ1 = {e1 }, then g(Fˆ0 , Fˆ1 ) ≥ (1 − x1 (e1 )) + x1 (e2 ) ≥ y∅ + yβ + yαγ .

– If Fˆ1 = {e3 }, then g(Fˆ0 , Fˆ1 ) ≥ 1 − x1 (e3 ) ≥ y∅ + yβ + yαγ .

ˆ + |Fˆ1 | is even. In

Proof of (P5). Suppose that T is of type (A), v2 ∈ S 0 , v3 6∈ S 0 , and b1 (S)

the same way as (P2), we may assume that p1 ∈ S 0 . If p2 ∈ S 0 , then b1 (p2 )+|F10 ∩δG1 (p2 )| is

even by the same calculation as (P1). Therefore, we may assume that p2 6∈ S 0 , since otherwise

we can replace (S 0 , F00 , F10 ) with (S 0 \ {p2 }, F00 \ δG1 (p2 ), F10 \ δG1 (p2 )) without increasing

the value of h(S 0 , F00 , F10 ). That is, we may assume that Sˆ = {p1 }, Fˆ0 ∪ Fˆ1 = {e1 , e3 },

and |Fˆ1 | is odd. Then, g(Fˆ0 , Fˆ1 ) ≥ min{(1 − x1 (e1 )) + x1 (e3 ), x1 (e1 ) + (1 − x1 (e3 ))} =

min{x(α) + x(β), 2 − x(α) − x(β)} ≥ min{x(α) + x(β), 2 − x(α) − x(β) − 2yγ }.

ˆ + |Fˆ1 | is odd. In

Proof of (P6). Suppose that T is of type (A), v2 ∈ S 0 , v3 6∈ S 0 , and b1 (S)

the same way as (P5), we may assume that Sˆ = {p1 }, Fˆ0 ∪ Fˆ1 = {e1 , e3 }, and |Fˆ1 | is even.

Then, g(Fˆ0 , Fˆ1 ) ≥ min{x1 (e1 ) + x1 (e3 ), 2 − x1 (e1 ) − x1 (e3 )} = min{y∅ + yγ + yαβ , 2 − (y∅ +

yγ + yαβ )} = y∅ + yγ + yαβ .

A.1.2 When T is of type (A’)

Second, we consider the case when T is of type (A’).

ˆ + |Fˆ1 | is odd, then

Proof of (P7). Suppose that T is of type (A’) and v1 6∈ S 0 . If b1 (S)

Sˆ = {p3 } and |Fˆ1 | is odd. This shows that h(S 0 , F00 , F10 ) ≥ g(Fˆ0 , Fˆ1 ) ≥ 1 by the following

case analysis, which is a contradiction.

– If Fˆ1 = {e1 }, then g(Fˆ0 , Fˆ1 ) ≥ (1 − x1 (e1 )) + x1 (e2 ) + x1 (e9 ) ≥ 1. The same argument

can be applied to the case of Fˆ1 = {e2 } by the symmetry of α and γ.

– If Fˆ1 = {ei } for some i ∈ {3, 4, 8}, then g(Fˆ0 , Fˆ1 ) ≥ (1 − x1 (ei )) + x1 (e9 ) ≥ 1.

– If Fˆ1 = {e9 }, then g(Fˆ0 , Fˆ1 ) = 1 + 2y∅ ≥ 1.

– If |Fˆ1 | ≥ 3, then g(Fˆ0 , Fˆ1 ) ≥ 3−(x1 (e1 )+x1 (e2 )+x1 (e3 )+x1 (e4 )+x1 (e8 )+x1 (e9 )) ≥ 1.

ˆ + |Fˆ1 | is even.

Therefore, b1 (S)

ˆ + |Fˆ1 | is even. Then,

Proof of (P8). Suppose that T is of type (A’), v1 ∈ S 0 , and b1 (S)

g(F0 , F1 ) ≥ min{x(α) + x(γ), 2 − x(α) − x(γ) − 2yβ } by the following case analysis.

– If Fˆ0 = {e8 , e9 } and Fˆ1 = ∅, then g(Fˆ0 , Fˆ1 ) = x1 (e8 ) + x1 (e9 ) = x(α) + x(γ).

– If Fˆ0 = ∅ and Fˆ1 = {e8 , e9 }, then g(Fˆ0 , Fˆ1 ) = (1 − x1 (e8 )) + (1 − x1 (e9 )) = 2 − x(α) −

x(γ) ≥ 2 − x(α) − x(γ) − 2yβ .

– If Fˆ0 ∪ Fˆ1 = {e1 , e2 , e3 , e4 }, then g(Fˆ0 , Fˆ1 ) ≥ min{x(α) + x(γ), 2 − x(α) − x(γ) − 2yβ }

by the same calculation as (P2) in Section A.1.1.

ˆ + |Fˆ1 | is odd. Then,

Proof of (P9). Suppose that T is of type (A’), v1 ∈ S 0 , and b1 (S)

g(Fˆ0 , Fˆ1 ) ≥ y∅ + yβ + yαγ by the following case analysis.

– If Fˆ0 = {e8 } and Fˆ1 = {e9 }, then g(Fˆ0 , Fˆ1 ) = x1 (e8 ) + (1 − x1 (e9 )) = y∅ + yβ + yαγ .

– If Fˆ0 = {e9 } and Fˆ1 = {e8 }, then g(Fˆ0 , Fˆ1 ) = (1 − x1 (e8 )) + x1 (e9 ) ≥ 1 ≥ y∅ + yβ + yαγ .

– If Fˆ0 ∪ Fˆ1 = {e1 , e2 , e3 , e4 }, then g(Fˆ0 , Fˆ1 ) ≥ y∅ + yβ + yαγ by the same calculation as

(P4) in Section A.1.1.

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

Weighted Triangle-free 2-matching Problem

23

e1 e2

e6

e5

e3 p1 e4

e7

p3 e9

e8 p2

11 r*

v3

v2

e13

e12

e14

e16 e15

Fig. 12 Construction of G+

A.1.3 When T is of type (B)

Third, we consider the case when T is of type (B). Let G+ = (V + , E + ) be the graph obtained

from G0T = (VT0 , ET0 ) in Figure 9 by adding a new vertex r∗ , edges e11 = rr∗ , e12 = v2 r∗ ,

e13 = v3 r∗ , and self-loops e14 , e15 , e16 that are incident to v2 , v3 , and r∗ , respectively

(Figure 12). We define bT : V + → Z≥0 as bT (v) = 1 for v ∈ {r, p1 , p2 , p3 } and bT (v) = 2

for v ∈ {r∗ , v2 , v3 }. We also define xT : E + → Z≥0 as xT (e) = x1 (e) for e ∈ ET0 and

xT (e11 ) = yα +yγ +yαβ +yβγ , xT (e12 ) = yα +yβ +yαγ +yβγ , xT (e13 ) = yβ +yγ +yαβ +yαγ ,

xT (e14 ) = y∅ + yγ , xT (e15 ) = y∅ + yα , and xT (e16 ) = y∅ . For J ∈ ET , define bT -factors MJ

in G+ as follows:

M∅ = {e1 , e7 , e14 , e15 , e16 },

Mα = {e4 , e8 , e11 , e12 , e15 },

Mβ = {e1 , e8 , e9 , e12 , e13 },

Mγ = {e3 , e9 , e11 , e13 , e14 },

Mαβ = {e5 , e8 , e9 , e11 , e13 },

Mαγ = {e2 , e8 , e9 , e12 , e13 },

Mβγ = {e6 , e8 , e9 , e11 , e12 }.

E + is

Then, we obtain

J∈ET y1 (J) = 1 and

J∈ET y1 (J)xMJ = xT , where xMJ ∈ R

the characteristic vector of MJ . This shows that xT is in the bT -factor polytope in G+ .

Therefore, xT satisfies (3) with respect to G+ and bT . We now show (P1), (P3), (P4), (P5),

and (P6).

ˆ + |Fˆ1 | is odd,

Proof of (P1). Suppose that T is of type (B) and v2 , v3 6∈ S 0 . If b1 (S)

ˆ + |Fˆ1 | is also odd. Since xT satisfies (3) with respect to G+ and bT , we obtain

then bT (S)

g(Fˆ0 , Fˆ1 ) ≥ 1. This shows that h(S 0 , F00 , F10 ) ≥ 1, which is a contradiction. Therefore,

ˆ + |Fˆ1 | is even.

b1 (S)

ˆ + |Fˆ1 | is even. Since

Proof of (P3). Suppose that T is of type (B), v2 , v3 ∈ S 0 , and b1 (S)

bT (Sˆ ∪ {r∗ , v2 , v3 }) + |Fˆ1 ∪ {e11 }| is odd and xT satisfies (3), we obtain g(Fˆ0 , Fˆ1 ) + (1 −

xT (e11 )) ≥ 1. Therefore, g(Fˆ0 , Fˆ1 ) ≥ xT (e11 ) = yα + yγ + yαβ + yβγ .

ˆ + |Fˆ1 | is odd. Since

Proof of (P4). Suppose that T is of type (B), v2 , v3 ∈ S 0 , and b1 (S)

bT (S ∪ {r , v2 , v3 }) + |F1 | is odd and xT satisfies (3), we obtain g(F0 , Fˆ1 ) + xT (e11 ) ≥ 1.

Therefore, g(Fˆ0 , Fˆ1 ) ≥ 1 − xT (e11 ) = y∅ + yβ + yαγ .

ˆ + |Fˆ1 | is even.

Proof of (P5). Suppose that T is of type (B), v2 ∈ S 0 , v3 6∈ S 0 , and b1 (S)

ˆ then we can add p2 to S 0 without decreasing the value of

If Sˆ ∩ {p1 , p3 } =

6 ∅ and p2 6∈ S,

h(S 0 , F00 , F10 ). Therefore, we can show g(Fˆ0 , Fˆ1 ) ≥ {x(α) + x(β), 2 − x(α) − x(β) − 2yγ } by

the following case analysis.

– Suppose that Sˆ = {p1 , p2 , p3 }, which implies that Fˆ0 ∪ Fˆ1 = {e1 , e2 , e6 , e9 } and |Fˆ1 | is

odd.

– If Fˆ1 = {ei } for i ∈ {1, 2, 6}, then g(Fˆ0 , Fˆ1 ) ≥ (1 − x1 (ei )) + x1 (e9 ) ≥ x(α) + x(β).

– If Fˆ1 = {e9 }, then g(Fˆ0 , Fˆ1 ) = yα + yβ + yαγ + yβγ + 2y∅ = 2 − x(α) − x(β) − 2yγ .

– If |Fˆ1 | = 3, then g(Fˆ0 , Fˆ1 ) ≥ 3 − (x1 (e1 ) + x1 (e2 ) + x1 (e6 ) + x1 (e9 )) ≥ x(α) + x(β).

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

24

Yusuke Kobayashi

– Suppose that Sˆ = {p1 , p2 }, which implies that Fˆ0 ∪ Fˆ1 = {e1 , e2 , e4 , e6 , e7 } and |Fˆ1 | is

even.

– If Fˆ1 = ∅, then g(Fˆ0 , Fˆ1 ) = x1 (e1 ) + x1 (e2 ) + x1 (e4 ) + x1 (e6 ) + x1 (e7 ) = 2 − x(α) −

x(β) − 2yγ .

– If |Fˆ1 | ≥ 2, then g(Fˆ0 , Fˆ1 ) ≥ 2 − (x1 (e1 ) + x1 (e2 ) + x1 (e4 ) + x1 (e6 ) + x1 (e7 )) ≥

x(α) + x(β).

– Suppose that Sˆ = {p2 }, which implies that Fˆ0 ∪ Fˆ1 = {e3 , e5 , e7 } and |Fˆ1 | is odd.

– If Fˆ1 = {ei } for i ∈ {3, 7}, then g(Fˆ0 , Fˆ1 ) ≥ (1 − x1 (ei )) + x1 (e5 ) ≥ x(α) + x(β).

– If Fˆ1 = {e5 }, then g(Fˆ0 , Fˆ1 ) ≥ (1 − x1 (e5 )) + x1 (e7 ) ≥ 2 − x(α) − x(β) − 2yγ .

– If Fˆ1 = {e3 , e5 , e7 }, then g(Fˆ0 , Fˆ1 ) = 3 − (x1 (e3 ) + x1 (e5 ) + x1 (e7 )) ≥ x(α) + x(β).

– Suppose that Sˆ = {p2 , p3 }, which implies that Fˆ0 ∪ Fˆ1 = {e3 , e4 , e5 , e9 } and |Fˆ1 | is even.

– If Fˆ1 = ∅, then g(Fˆ0 , Fˆ1 ) = x1 (e3 ) + x1 (e4 ) + x1 (e5 ) + x1 (e9 ) = x(α) + x(β) + 2yγ ≥

x(α) + x(β).

– If |Fˆ1 | ≥ 2, then g(Fˆ0 , Fˆ1 ) ≥ 2 − (x1 (e3 ) + x1 (e4 ) + x1 (e5 ) + x1 (e9 )) = 2 − x(α) −

x(β) − 2yγ .

– If Sˆ = ∅, then Fˆ0 ∪ Fˆ1 = {e5 , e8 } and |Fˆ1 | is even. Therefore, g(Fˆ0 , Fˆ1 ) ≥ min{x1 (e5 ) +

x1 (e8 ), 2 − x1 (e5 ) − x1 (e8 )} ≥ min{x(α) + x(β), 2 − x(α) − x(β) − 2yγ }.

ˆ + |Fˆ1 | is odd.

Proof of (P6). Suppose that T is of type (B), v2 ∈ S 0 , v3 6∈ S 0 , and b1 (S)

Since bT (S ∪ {v2 }) + |F1 | is odd and xT satisfies (3), we obtain g(F0 , F1 ) + xT (e12 ) ≥ 1.

Therefore, g(Fˆ0 , Fˆ1 ) ≥ 1 − xT (e12 ) = y∅ + yγ + yαβ .

A.1.4 When T is of type (B’)

Finally, we consider the case when T is of type (B’).

ˆ + |Fˆ1 | is odd, then

Proof of (P7). Suppose that T is of type (B’) and v1 6∈ S 0 . If b1 (S)

S = {p4 } and h(S , F0 , F1 ) ≥ min{x1 (e1 ) + x1 (e10 ), 2 − x1 (e1 ) − x1 (e10 )} = 1, which is a

ˆ + |Fˆ1 | is even.

contradiction. Therefore, b1 (S)

ˆ + |Fˆ1 | is even. If

Proof of (P8). Suppose that T is of type (B’), v1 ∈ S 0 , and b1 (S)

p4 6∈ S 0 , then we define (S 00 , F000 , F100 ) ∈ F1 as (S 00 , F000 , F100 ) = (S 0 ∪ {p4 }, F00 \ {e10 }, F10 ∪

{e1 }) if e10 ∈ F00 and (S 00 , F000 , F100 ) = (S 0 ∪ {p4 }, F00 ∪ {e1 }, F10 \ {e10 }) if e10 ∈ F10 . Since

h(S 00 , F000 , F100 ) = h(S 0 , F00 , F10 ), by replacing (S 0 , F00 , F10 ) with (S 00 , F000 , F100 ), we may assume

that p4 ∈ S 0 . Then, since Fˆ0 ∪ Fˆ1 = {e1 , e2 } and |Fˆ1 | is odd, we obtain g(Fˆ0 , Fˆ1 ) ≥

min{(1 − x1 (e1 )) + x1 (e2 ), x1 (e1 ) + (1 − x1 (e2 ))} ≥ min{x(α) + x(γ), 2 − x(α) − x(γ) − 2yβ }.

ˆ + |Fˆ1 | is odd. In the same

Proof of (P9). Suppose that T is of type (B’), v1 ∈ S 0 , and b1 (S)

way as (P8), we may assume that S = {p4 }, F0 ∪ F1 = {e1 , e2 }, and |Fˆ1 | is even. Then,

g(Fˆ0 , Fˆ1 ) ≥ min{x1 (e1 ) + x1 (e2 ), (1 − x1 (e1 )) + (1 − x1 (e2 ))} = min{y∅ + yβ + yαγ , 2 − (y∅ +

yβ + yαγ )} = y∅ + yβ + yαγ .

A.2 Condition (10)

Recall that r 6∈ S 0 is assumed and note that x1 (δG1 (r)) = 1. Let T(P 3) ⊆ TS+∗ be the set

of triangles satisfying the conditions in (P3), i.e., the set of triangles of type (B) such that

ˆ + |Fˆ1 | is even. Since yα + yγ + yαβ + yβγ = 1 − x1 (eT ) − x1 (eT )

v2 , v3 ∈ S 0 and b1 (S)

holds for each triangle T ∈ TS+∗ of type (B), if there exist two triangles T, T 0 ∈ T(P 3) , then

h(S 0 , F00 , F10 ) ≥ (1 − x1 (eT

1 ) − x1 (e2 )) + (1 − x1 (e1 ) − x1 (e2 )) ≥ 2 − x1 (δG1 (r)) = 1, which

is a contradiction. Similarly, if there exists a triangle T ∈ T(P 3) and an edge e ∈ (δG1 (r) \

ET0 ) ∩ F10 , then h(S 0 , F00 , F10 ) ≥ (1 − x1 (eT

1 ) − x1 (e2 )) + (1 − x1 (e)) ≥ 2 − x1 (δG1 (r)) = 1,

which is a contradiction. Therefore, either T(P 3) = ∅ holds or T(P 3) consists of exactly one

triangle, say T , and (δG1 (r) \ ET0 ) ∩ F10 = ∅.

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

Weighted Triangle-free 2-matching Problem

25

Assume that T(P 3) = {T } and (δG1 (r) \ ET0 ) ∩ F10 = ∅. Define (S 00 , F000 , F100 ) ∈ F1 as

S 00 = S 0 ∪ VT0 , F000 = (F00 4δG1 (r)) \ ET0 , and F100 = F10 \ ET0 , where 4 denotes the symmetric

ˆ +

difference. Note that (F000 , F100 ) is a partition of δG1 (S 00 ), b1 (S 00 ) + |F100 | = (b1 (S 0 ) + b1 (S))

T )) −

(|F10 | − |Fˆ1 |) ≡ 1 (mod 2), and h(S 0 , F00 , F10 ) − h(S 00 , F000 , F100 ) ≥ (1 − x1 (eT

(e

1 2

00

00

00

x1 (δG1 (r) \ {x1 (eT

1 ), x1 (e2 )}) = 0. By these observations, (S , F0 , F1 ) ∈ F1 is also a

00

00

00

00

minimizer of h. This shows that (V \ S , F0 , F1 ) ∈ F1 is a minimizer of h such that

r ∈ V 00 \ S 00 . Furthermore, if a triangle T 0 ∈ TS+∗ satisfies the conditions in (P3) with respect

to (V 00 \S 00 , F000 , F100 ), then T 0 is a triangle of type (B) such that v2 , v3 6∈ S 0 and b1 (S)+|

Fˆ1 | is

odd with respect to (S 0 , F00 , F10 ), which contradicts (P1). Therefore, by replacing (S 0 , F00 , F10 )

with (V 00 \ S 00 , F000 , F100 ), we may assume that T(P 3) = ∅.

In what follows, we construct (S, F0 , F1 ) ∈ F for which (x, y) violates (10) to derive a

contradiction. We initialize (S, F0 , F1 ) as S = S 0 ∩ V , F0 = F00 ∩ E, and F1 = F10 ∩ E, and

apply the following procedures for each triangle T ∈ TS+∗ .

– Suppose that T satisfies the condition in (P1) or (P7). In this case, we do nothing.

– Suppose that T satisfies the condition in (P2) or (P8). If g(Fˆ0 , Fˆ1 ) ≥ x(α) + x(γ), then

add α and γ to F0 . Otherwise, since g(Fˆ0 , Fˆ1 ) ≥ 2 − x(α) − x(γ) − 2yβ , add α and γ to

F1 .

– Suppose that T satisfies the condition in (P4) or (P9). In this case, add α to F0 and

add γ to F1 .

– Suppose that T satisfies the condition in (P5). If g(Fˆ0 , Fˆ1 ) ≥ x(α) + x(β), then add α

and β to F0 . Otherwise, since g(Fˆ0 , Fˆ1 ) ≥ 2 − x(α) − x(β) − 2yγ , add α and β to F1 .

– Suppose that T satisfies the condition in (P6). In this case, add α to F0 and add β to

F1 .

Note that exactly one of the above procedures is applied for each T ∈ TS+∗ , because T(P 3) = ∅.

Then, we see that (S, F0 , F1 ) ∈ F holds and the left-hand side of (10) with respect to

(S, F0 , F1 ) is at most h(S 0 , F00 , F10 ) by (P1)–(P9). Since h(S 0 , F00 , F10 ) < 1 is assumed, (x, y)

violates (10) for (S, F0 , F1 ) ∈ F , which is a contradiction.

B Proof of Lemma 6

We first show that M1 ⊕ M2 forms a T -free b-factor. We can easily see that replacing

(M1 ∪ M2 ) ∩ {ef | f ∈ F˜0∗ } with {f ∈ F˜0∗ | ef ∈ M1 ∩ M2 } does not affect the degrees of

vertices in V . Since M1 ∪ M2 contains exactly one of {efu , efv } or efr (= efr0 ) for f = uv ∈ F˜1∗ ,

replacing (M1 ∪ M2 ) ∩ {efu , efr , efv | f = uv ∈ F˜1∗ } with {f ∈ F˜1∗ | efr 6∈ M1 ∩ M2 } does not

affect the degrees of vertices in V .

For every T ∈ TS+∗ of type (A) or (A’), since |ϕ(M1 , M2 , T ) ∩ {α, γ}| = |MT ∩ {e8 , e9 }|,

|ϕ(M1 , M2 , T ) ∩ {α, β}| = |MT ∩ {e3 , e5 }|, and |ϕ(M1 , M2 , T ) ∩ {β, γ}| = |MT ∩ {e4 , e6 }|

hold by the definition of ϕ(M1 , M2 , T ), replacing MT with ϕ(M1 , M2 , T ) does not affect the

degrees of vertices in V .

Furthermore, for every T ∈ TS+∗ of type (B) or (B’), since |ϕ(M1 , M2 , T ) ∩ {α, γ}| =

|MT ∩ {e2 , e10 }|, |ϕ(M1 , M2 , T ) ∩ {α, β}| = |MT ∩ {e5 , e8 }|, and |ϕ(M1 , M2 , T ) ∩ {β, γ}| =

|MT ∩ {e6 , e9 }| hold by the definition of ϕ(M1 , M2 , T ), replacing MT with ϕ(M1 , M2 , T )

does not affect the degrees of vertices in V .

Since b(v) = b1 (v) for v ∈ S ∗ and b(v) = b2 (v) for v ∈ V ∗ \ S ∗ , this shows that M1 ⊕ M2

forms a b-factor. Since Mj P

is Tj -free for j ∈ {1, 2}, M1 ⊕ M2 is a T -free b-factor.

We next show that x = (M1 ,M2 )∈M λ(M1 ,M2 ) xM1 ⊕M2 . By the definitions of x1 , x2 , M1 ⊕

M2 , and λ(M1 ,M2 ) , it holds that

x(e) =

(M1 ,M2 )∈M

for e ∈ E \

T ∈TS+∗

E(T ).

λ(M1 ,M2 ) xM1 ⊕M2 (e)

(11)

A Self-archived copy in

Kyoto University Research Information Repository

https://repository.kulib.kyoto-u.ac.jp

26

Yusuke Kobayashi

Let T ∈ TS+∗ be a triangle of type (A) for (G1 , b1 , T1 ) and let α, β, and γ be as in

Figures 7 and 8. By the definition of ϕ(M1 , M2 , T ), we obtain

λ(M1 ,M2 ) xM1 ⊕M2 (β) =

{λ(M1 ,M2 ) | ϕ(M1 , M2 , T ) = {α, β}, {β, γ}, or {β}}

(M1 ,M2 )∈M

= x1 (e3 ) + x1 (e4 ) + x2 (e7 ) = yαβ + yβγ + yβ = x(β).

We also obtain

λ(M1 ,M2 ) xM1 ⊕M2 (α) =

{λ(M1 ,M2 ) | ϕ(M1 , M2 , T ) 6= {γ}, {β, γ}, {β}}

(M1 ,M2 )∈M

= 1 − x1 (e1 ) − x1 (e4 ) − x2 (e7 ) = 1 − y∅ − yγ − yβγ − yβ = x(α).

Since a similar equality holds for γ by symmetry, (11) holds for e ∈ {α, β, γ}. Since T is a

triangle of type (A’) for (G1 , b1 , T1 ) if and only if it is of type (A) for (G2 , b2 , T2 ), the same

argument can be applied when T is a triangle of type (A’) for (G1 , b1 , T1 ).

Let T ∈ TS+∗ be a triangle of type (B) for (G1 , b1 , T1 ) and let α, β, and γ be as in

Figures 9 and 10. By the definition of ϕ(M1 , M2 , T ), we obtain

λ(M1 ,M2 ) xM1 ⊕M2 (β) =

{λ(M1 ,M2 ) | ϕ(M1 , M2 , T ) 6= ∅, {α}, {γ}, {α, γ}}

(M1 ,M2 )∈M

= 1 − x1 (e2 ) − x1 (e3 ) − x1 (e4 ) − x1 (e7 ) = 1 − yαγ − yγ − yα − y∅ = x(β).

We also obtain

λ(M1 ,M2 ) xM1 ⊕M2 (α) =

{λ(M1 ,M2 ) | ϕ(M1 , M2 , T ) = {α}, {α, β}, or {α, γ}}

(M1 ,M2 )∈M

= x1 (e2 ) + x1 (e4 ) + x1 (e5 ) = yαγ + yα + yαβ = x(α).

Since a similar equality holds for γ by symmetry, (11) holds for e ∈ {α, β, γ}. The same

argument can be applied when T is a triangle of type (B’) for (G1 , b1 , T1 ).

Therefore, (11) holds for every e ∈ E, which complete the proof.

...