## Invited Session Thu.3.H 3008

#### Thursday, 15:15 - 16:45 h, Room: H 3008

**Cluster 2: Combinatorial optimization** [...]

### Discrete structures and algorithms III

**Chair: Satoru Fujishige**

**Thursday, 15:15 - 15:40 h, Room: H 3008, Talk 1**

**Yusuke Kobayashi**

An algorithm for finding a maximum *t*-matching excluding complete partite subgraphs

**Coauthor: Xin Yin**

**Abstract:**

For an integer *t* and a fixed graph *H*, we consider the problem of finding a maximum *t*-matching not containing *H* as a subgraph, which we call the *H*-free *t*-matching problem. This problem is a generalization of the problem of finding a maximum *2*-matching with no short cycles, which has been well-studied as a natural relaxation of the Hamiltonian circuit problem. When *H* is a complete graph *K*_{t+1} or a complete bipartite graph *K*_{t,t}, in 2010, Bérczi and Végh gave a polynomial-time algorithm for the *H*-free *t*-matching problem in simple graphs with maximum degree at most *t+1*. Our main contribution is to extend this result to the case when *H* is a *t*-regular complete partite graph. We also show that the problem is NP-complete when *H* is a connected *t*-regular graph that is not complete partite. Since it is known that, for a connected *t*-regular graph *H*, the degree sequences of all *H*-free *t*-matchings in a graph form a jump system if and only if *H* is a complete partite graph, our results show that the polynomial-time solvability of the *H*-free *t*-matching problem is consistent with this condition.

**Thursday, 15:45 - 16:10 h, Room: H 3008, Talk 2**

**Shin-Ichi Tanigawa**

Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries

**Coauthor: Naoki Katoh**

**Abstract:**

As an extension of a classical tree-partition problem, we consider decompositions of graphs into edge-disjoint (rooted-)trees with an additional matroid constraint. Specifically, suppose we are given a graph *G=(V,E)*, a multiset *R={r*_{1}, … , r_{t}} of vertices in *V*, and a matroid *M* on *R*. We prove a necessary and sufficient condition for *G* to be decomposed into *t* edge-disjoint subgraphs *G*_{1}=(V_{1},T_{1}), … , G_{t}=(V_{t},T_{t}) such that (i) for each *i*, *G*_{i} is a tree with *r*_{i} ∈ V_{i}, and (ii) for each *v ∈ V*, the multiset *{r*_{i} ∈ R| v ∈ V_{i}} is a base of *M*. If *M* is a free matroid, this is a decomposition into *t* edge-disjoint spanning trees; thus, our result is a proper extension of Nash-Williams' tree-partition theorem.

Such a matroid constraint is motivated by combinatorial rigidity theory. As a direct application of our decomposition theorem, we present characterizations of the infinitesimal rigidity of frameworks with non-generic "boundary'', which extend classical Laman's theorem for generic *2*-rigidity of bar-joint frameworks and Tay's theorem for generic *d*-rigidity of body-bar frameworks.

**Thursday, 16:15 - 16:40 h, Room: H 3008, Talk 3**

**Kiyohito Nagano**

Size-constrained submodular minimization through minimum norm base

**Coauthors: Kazuyuki Aihara, Yoshinobu Kawahara**

**Abstract:**

A number of combinatorial optimization problems in machine learning can be described as the problem of minimizing a submodular function. It is known that the unconstrained submodular minimization problem can be solved in strongly polynomial time. However, additional constraints make the problem intractable in many settings. In this paper, we discuss the submodular minimization under a size constraint, which is NP-hard, and generalizes the densest subgraph problem and the uniform graph partitioning problem. Because of NP-hardness, it is difficult to compute an optimal solution even for a prescribed size constraint. In our approach, we do not give approximation algorithms. Instead, the proposed algorithm computes optimal solutions for some of possible size constraints in polynomial time. Our algorithm utilizes the basic polyhedral theory associated with submodular functions. Additionally, we evaluate the performance of the proposed algorithm through computational experiments.