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


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 Kt+1 or a complete bipartite graph Kt,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


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={r1, … , rt} 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 G1=(V1,T1), … , Gt=(Vt,Tt) such that (i) for each i, Gi is a tree with ri ∈ Vi, and (ii) for each v ∈ V, the multiset {ri ∈ R| v ∈ Vi} 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


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.


  California Payday Loans. If you have already decided to take Generic Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.