Publishing type：Research paper (scientific journal)  

The terminal backup problems ([E. Anshelevich and A. Karagiozova, SIAM J. Comput., 40 (2011), pp. 678-708]) form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum-cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga [SIAM J. Discrete Math., 30 (2016), pp. 777-800] gave a 4/3-approximation algorithm based on an LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog(nUA) · MF(kn,m + k2n)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(n' ,m') is the time complexity of a max-flow algorithm in a network with n' nodes and m' edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, which is called a separately capacitated multiflow. We show a min-max theorem which extends the Lovász-Cherkassky theorem to the node-capacity setting. Our results build on discrete convexity in the node-connectivity terminal backup problem.

DOI： 10.1137/20m1361857

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we address computation of the degree deg Det A of Dieudonné determinant Det A ofA=∑k=1mAkxktck, where Ak are n× n matrices over a field K, xk are noncommutative variables,t is a variable commuting with xk, ck are integers,and the degree is considered for t.This problem generalizes noncommutative Edmonds' problem andfundamental combinatorial optimization problemsincluding the weighted linear matroid intersection problem.It was shown that deg Det A is obtained bya discrete convex optimization on a Euclidean building (Hirai 2019).We extend this framework by incorporating a cost-scaling techniqueand show that deg Det Acan be computed in time polynomial of n, m, log 2C, where C: = max k| ck|.We give a polyhedral interpretation of deg Det ,which says that deg Det A is given by linear optimizationover an integral polytope with respect to objective vector c= (ck).Based on it, we show that our algorithm becomes a strongly polynomial one.We also apply our result to an algebraic combinatorial optimization problemarising from a symbolic matrix having 2 × 2 -submatrix structure.

DOI： 10.1007/s00037-022-00227-4

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) A= (Aαβxαβ) , where Aαβ is a 2 × 2 matrix over a field F and xαβ is an indeterminate for α= 1 , 2 , ⋯ , μ and β= 1 , 2 , ⋯ , ν. This problem can be viewed as an algebraic generalization of the bipartite matching problem and was considered by Iwata and Murota (SIAM J Matrix Anal Appl 16(3):719–734, 1995). Recent interests in this problem lie in the connection with non-commutative Edmonds’ problem by Ivanyos et al. (Comput Complex 27:561–593, 2018) and Garg et al. (Found. Comput. Math. 20:223–290, 2020), where a result by Iwata and Murota implicitly states that the rank and non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a simple and combinatorial O((μν) 2min { μ, ν}) -time algorithm for computing the symbolic rank of a (2 × 2) -type generic partitioned matrix of size 2 μ× 2 ν. Our algorithm is inspired by the Wong sequence algorithm by Ivanyos et al. for the nc-rank of a general symbolic matrix, and requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of A for an arbitrary field F.

DOI： 10.1007/s10107-021-01676-5

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we address the minimum-cost node-capacitated multiflow problem in undirected networks. For this problem, Babenko and Karzanov (JCO 24: 202–228, 2012) showed strong polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in O(mlog (nCD) SF (kn, m, k)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, C is the maximum node capacity, D is the maximum edge cost, and SF (n′, m′, η) is the time complexity of solving the submodular flow problem in a network of n′ nodes, m′ edges, and a submodular function with η-time-computable exchange capacity. Our algorithm is built on discrete convex analysis on graph structures and the concept of reducible bisubmodular flows.

DOI： 10.1007/s10107-021-01683-6

Scopus

Publishing type：Research paper (scientific journal)  

A phylogenetic tree is a graphical representation of an evolutionary history of taxa in which the leaves correspond to the taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from small phylogenetic trees, particularly, quartet trees. Quartet Compatibility is the problem of deciding whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that Quartet Compatibility is NP-hard and that there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial-time algorithms for Quartet Compatibility for these systems.

DOI： 10.1007/s00453-022-00945-9

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we present a new model and mechanisms for auctions in twosided markets of buyers and sellers, where budget constraints are imposed on buyers. Our model incorporates polymatroidal environments and is applicable to a variety of models that include multiunit auctions, matching markets, and reservation exchangemarkets. Our mechanisms are built on the polymatroidal network flow model by Lawler and Martel. Additionally, they feature nice properties such as the incentive compatibility of buyers, individual rationality, Pareto optimality, and strong budget balance. The firstmechanismis a two-sided generalization of the polyhedral clinching auction by Goel et al. for one-sided markets. The second mechanism is a reduce-to-recover algorithm that reduces the market to be one-sided, applies the polyhedral clinching auction by Goel et al., and lifts the resulting allocation to the original two-sided market via the polymatroidal network flow. Both mechanisms are implemented by polymatroid algorithms. We demonstrate how our framework is applied to the Internet display advertisement auctions.

DOI： 10.1287/moor.2021.1124

Scopus

Publishing type：Research paper (scientific journal)  

Murota (1998) and Murota and Shioura (1999) introduced concepts of M-convex function and M♮-convex function as discrete convex functions, which are generalizations of valuated matroids due to Dress and Wenzel (1992). In the present paper we consider a new operation defined by a convolution of sections of an M♮-convex function that transforms the given M♮-convex function to an M-convex function, which we call a compression of an M♮-convex function. For the class of valuated generalized matroids, which are special M♮-convex functions, the compression induces a valuated permutohedron together with a decomposition of the valuated generalized matroid into flag-matroid strips, each corresponding to a maximal linearity domain of the induced valuated permutohedron. We examine the details of the structure of flag-matroid strips and the induced valuated permutohedron by means of discrete convex analysis of Murota.

DOI： 10.1016/j.jcta.2021.105525

Scopus

Publishing type：Research paper (scientific journal)  

The orthoscheme complex of a graded poset is a metrization of its order complex such that the simplex of each maximal chain is isometric to the Euclidean simplex of vertices 0 , e1, e1+ e2, … , e1+ e2+ ⋯ + en. This notion was introduced by Brady and McCammond in geometric group theory, and has applications in discrete optimization and submodularity theory. We address the question of which poset can yield the orthoscheme complex with CAT(0) property. The orthoscheme complex of a modular lattice has been shown to be CAT(0), and it is conjectured that this is the case for a modular semilattice. In this paper, we prove this conjecture affirmatively. This result implies that a larger class of weakly modular graphs yields CAT(0) complexes.

DOI： 10.1007/s10711-021-00623-0

Scopus

Publishing type：Research paper (scientific journal)  

For a metric μ on a finite set T, the minimum 0-extension problem 0-Ext[μ] is defined as follows: Given V⊇T and c:V2→Q+, minimize ∑c(xy)μ(γ(x),γ(y)) subject to γ:V→T,γ(t)=t(∀t∈T), where the sum is taken over all unordered pairs in V. This problem generalizes several classical combinatorial optimization problems such as the minimum cut problem or the multiterminal cut problem. Karzanov and Hirai established a complete classification of metrics μ for which 0-Ext[μ] is polynomial time solvable or NP-hard. This result can also be viewed as a sharpening of the general dichotomy theorem for finite-valued CSPs (Thapper and Živný 2016) specialized to 0-Ext[μ]. In this paper, we consider a directed version 0⃗-Ext[μ] of the minimum 0-extension problem, where μ and c are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext[μ] to 0⃗-Ext[μ]: If μ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant “directed” edge-length, then 0⃗-Ext[μ] is NP-hard. We also show a partial converse: If μ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then 0⃗-Ext[μ] is tractable. We further provide a new NP-hardness condition characteristic of 0⃗-Ext[μ], and establish a dichotomy for the case where μ is a directed metric of a star.

DOI： 10.1016/j.disopt.2021.100642

Scopus

Publishing type：Research paper (scientific journal)  

We study the noncommutative rank (nc-rank) computation of a symbolic matrix whose entries are linear forms in noncommutative variables. For this problem, polynomial time algorithms were given by Garg, Gurvits, Oliveira, and Wigderson over the rational numbers, and by Ivanyos, Qiao, and Subrahmanyam over arbitrary fields. We present a significantly different polynomial time algorithm that works for any field. Our algorithm is based on a combination of submodular optimization on modular lattices and convex optimization on CAT(0) spaces.

DOI： 10.1137/20M138836X

Scopus

Publishing type：Research paper (scientific journal)  

This article investigates structural, geometrical, and topological characterizations and properties of weakly modular graphs and of cell complexes derived from them. The unifying themes of our investigation are various “nonpositive curvature” and “local-to-global” properties and characterizations of weakly modular graphs and their subclasses. Weakly modular graphs have been introduced as a far-reaching common generalization of median graphs (and more generally, of modular and orientable modular graphs), Helly graphs, bridged graphs, and dual polar graphs occurring under different disguises (1-skeletons, collinearity graphs, covering graphs, domains, etc.) in several seemingly-unrelated fields of mathematics: • Metric graph theory • Geometric group theory • Incidence geometries and buildings • Theoretical computer science and combinatorial optimization We give a local-to-global characterization of weakly modular graphs and their subclasses in terms of simple connectedness of associated triangle-square complexes and specific local combinatorial conditions. In particular, we revisit characterizations of dual polar graphs by Cameron and by Brouwer-Cohen. We also show that (disk-)Helly graphs are precisely the clique-Helly graphs with simply connected clique complexes. With l1-embeddable weakly modular and sweakly modular graphs we associate high-dimensional cell complexes, having several strong topological and geometrical properties (contractibility and the CAT(0) property). Their cells have a specific structure: they are basis polyhedra of even Δ-matroids in the first case and orthoscheme complexes of gated dual polar subgraphs in the second case. We resolve some open problems concerning subclasses of weakly modular graphs: we prove a Brady-McCammond conjecture about CAT(0) metric on the orthoscheme complexes of modular lattices; we answer Chastand's question about prime graphs for pre-median graphs. We also explore negative curvature for weakly modular graphs.

DOI： 10.1090/memo/1309

Scopus

Publishing type：Research paper (scientific journal)  

A modular semilattice is a semilattice generalization of a modular lattice. We establish a Birkhoff-type representation theorem for modular semilattices, which says that every modular semilattice is isomorphic to the family of ideals in a certain poset with additional relations. This new poset structure, which we axiomatize in this paper, is called a PPIP (projective poset with inconsistent pairs). A PPIP is a common generalization of a PIP (poset with inconsistent pairs) and a projective ordered space. The former was introduced by Barthélemy and Constantin for establishing Birkhoff-type theorem for median semilattices, and the latter by Herrmann, Pickering, and Roddy for modular lattices. We show the Θ(n) representation complexity and a construction algorithm for PPIP-representations of (∧,∨)-closed sets in the product Ln of modular semilattice L. This generalizes the results of Hirai and Oki for a special median semilattice Sk. We also investigate implicational bases for modular semilattices. Extending earlier results of Wild and Herrmann for modular lattices, we determine optimal implicational bases and develop a polynomial time recognition algorithm for modular semilattices. These results can be applied to retain the minimizer set of a submodular function on a modular semilattice.

DOI： 10.1007/s11083-019-09516-0

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we address the weighted linear matroid intersection problem from computation of the degree of the determinant of a symbolic matrix. We show that a generic algorithm computing the degree of noncommutative determinants, proposed by the second author, becomes an O(mn3log n) time algorithm for the weighted linear matroid intersection problem, where two matroids are given by column vectors of n× m matrices A, B. We reveal that our algorithm is viewed as a “nonstandard” implementation of Frank’s weight splitting algorithm for linear matroids. This gives a linear algebraic reasoning to Frank’s algorithm. Although our algorithm is slower than existing algorithms in the worst case estimate, it has a notable feature. Contrary to existing algorithms, our algorithm works on different matroids represented by another “sparse” matrices A, B, which skips unnecessary Gaussian eliminations for constructing residual graphs.

DOI： 10.1007/s13160-020-00413-3

Scopus

Publishing type：Research paper (international conference proceedings)  

For a metric µ on a finite set T, the minimum 0-extension problem 0-Ext[µ] is defined as follows: Given V ⊇ T and c: (V/2) → Q+, minimize P c(xy)µ(γ(x), γ(y)) subject to γ: V → T, γ(t) = t (∀t ∈ T), where the sum is taken over all unordered pairs in V . This problem generalizes several classical combinatorial optimization problems such as the minimum cut problem or the multiterminal cut problem. The complexity dichotomy of 0-Ext[µ] was established by Karzanov and Hirai, which is viewed as a manifestation of the dichotomy theorem for finite-valued CSPs due to Thapper and Živný. In this paper, we consider a directed version →0 -Ext[µ] of the minimum 0-extension problem, where µ and c are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext[µ] to →0 -Ext[µ]: If µ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant “directed” edge-length, then →0 -Ext[µ] is NP-hard. We also show a partial converse: If µ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then →0 -Ext[µ] is tractable. We further provide a new NP-hardness condition characteristic of → 0 -Ext[µ], and establish a dichotomy for the case where µ is a directed metric of a star.

DOI： 10.4230/LIPIcs.MFCS.2020.46

Scopus

Publishing type：Research paper (scientific journal)  

A simple lattice-theoretic characterization for affine buildings of type A is obtained. We introduce a class of modular lattices, called uniform modular lattices, and show that uniform modular lattices and affine buildings of type A constitute the same object. This is an affine counterpart of the well-known equivalence between projective geometries ( complemented modular lattices) and spherical buildings of type A.

DOI： 10.1515/advgeom-2020-0007

Scopus

Publishing type：Research paper (international conference proceedings)  

The terminal backup problems [Anshelevich and Karagiozova, 2011] form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga (2016) gave a 4/3-approximation algorithm based on LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog(mUA)·MF(kn,m+k2n)) time, where m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(n0,m0) is the time complexity of a max-flow algorithm in a network with n0 nodes and m0 edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, called a separately-capacitated multiflow. We show a min-max theorem which extends Lovász-Cherkassky theorem to the node-capacity setting. Our results build on discrete convex analysis for the node-connectivity terminal backup problem.

DOI： 10.4230/LIPIcs.ICALP.2020.65

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we address the problem of counting integer points in a rational polytope described by P(y) = {x ∈ ℝm: Ax = y, x ≥ 0}, where A is an n × m integer matrix and y is an n-dimensional integer vector. We study the Z transformation approach initiated in works by Brion and Vergne, Beck, and Lasserre and Zeron from the numerical analysis point of view and obtain a new algorithm on this problem. If A is nonnegative, then the number of integer points in P(y) can be computed in O(poly(n, m, ||y||∞)(||y||∞ + 1)n) time and O(poly(n, m, ||y||∞)) space. This improves, in terms of space complexity, a naive DP algorithm with O((||y||∞ + 1)n)-size dynamic programming table. Our result is based on the standard error analysis of the numerical contour integration for the inverse Z transform and establishes a new type of an inclusion-exclusion formula for integer points in P(y). We apply our result to hypergraph b-matching and obtain a O(poly(n, m, ||b||∞)(||b||∞+ 1)(1−1/k)n) time algorithm for counting b-matchings in a k-partite hypergraph with n vertices and m hyperedges. This result is viewed as a b-matching generalization of the classical result by Ryser for k = 2 and its multipartite extension by Björklund and Husfeldt.

DOI： 10.1287/moor.2019.0997

Scopus

Publishing type：Research paper (international conference proceedings)  

In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) [Formula Presented], where [Formula Presented] is a [Formula Presented] matrix over a field [Formula Presented] and [Formula Presented] is an indeterminate for [Formula Presented] and [Formula Presented]. This problem can be viewed as an algebraic generalization of the bipartite matching problem, and was considered by Iwata and Murota (1995). One of recent interests on this problem lies in the connection with non-commutative Edmonds’ problem by Ivanyos, Qiao and Subrahamanyam (2018), and Garg, Gurvits, Oliveiva and Wigderson (2019), where a result by Iwata and Murota implicitly says that the rank and the non-commutative rank (nc-rank) are the same for this class of symbolic matrices. The main result of this paper is a combinatorial [Formula Presented]-time algorithm for computing the symbolic rank of a [Formula Presented]-type generic partitioned matrix of size [Formula Presented]. Our algorithm is based on the Wong sequence algorithm by Ivanyos, Qiao, and Subrahamanyam for the nc-rank of a general symbolic matrix, but is simpler. Our proposed algorithm requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of A for an arbitrary field [Formula Presented].

DOI： 10.1007/978-3-030-45771-6_16

Scopus

Publishing type：Research paper (scientific journal)  

A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper and Živn?classified the tractability of binary VCSP instances according to the concept of "triangle," and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa, Murota, and Živn?made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWPcan be transformed into a function represented as the sum of two quadratic M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this article,we give an algorithmic answer to a natural question:What binary finite-valued CSP instances can be represented as the sum of two quadratic M-convex functions and can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-Time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.

DOI： 10.1145/3329862

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we present a lattice-theoretic characterization for valuated matroids, which is an extension of the well-known cryptomorphic equivalence between matroids and geometric lattices (= atomistic semimodular lattices). We introduce a class of semimodular lattices, called uniform semimodular lattices, and establish a cryptomorphic equivalence between integer-valued valuated matroids and uniform semimodular lattices. Our result includes a coordinate-free lattice-theoretic characterization of integer points in tropical linear spaces, incorporates the Dress-Terhalle completion process of valuated matroids, and establishes a smooth connection with Euclidean buildings of type A.

DOI： 10.1016/j.jcta.2019.02.013

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we consider the computation of the degree of the Dieudonne determinant of a linear symbolic matrix A = A0 + A1x1 + \cdot \cdot \cdot + Amxm, where each Ai is an n \times n polynomial matrix over \BbbK [t] and x1, x2, . . ., xm are pairwise ``noncommutative"" variables. This quantity is regarded as a weighted generalization of the noncommutative rank (nc-rank) of a linear symbolic matrix, and its computation is shown to be a generalization of several basic combinatorial optimization problems, such as weighted bipartite matching and weighted linear matroid intersection problems. Based on the work on nc-rank by Fortin and Reutenauer [Sem. Lothar. Combin., 52 (2004), B52f] and Ivanyos, Qiao, and Subrahmanyam [Comput. Complex., 27 (2018), pp. 561-593], we develop a framework to compute the degree of the Dieudonne determinant of a linear symbolic matrix. We show that the deg-det computation reduces to a discrete convex optimization problem on the Euclidean building for SL(\BbbK (t)n). To deal with this optimization problem, we introduce a class of discrete convex functions on the building. This class is a natural generalization of L-convex functions in discrete convex analysis (DCA). We develop a DCA-oriented algorithm (steepest descent algorithm) to compute the degree of determinants. Our algorithm works with matrix computation on \BbbK and uses a subroutine to compute a certificate vector subspace for the nc-rank, where the number of calls of the subroutine is sharply estimated. Our algorithm enhances some classical combinatorial optimization algorithms with new insights, and it is also understood as a variant of the combinatorial relaxation algorithm, which was developed earlier by Murota for computing the degree of the (ordinary) determinant.

DOI： 10.1137/18M1190823

Scopus

Publishing type：Research paper (international conference proceedings)  

A phylogenetic tree is a graphical representation of an evolutionary history in a set of taxa in which the leaves correspond to taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from smaller pieces of phylogenetic trees, particularly, quartet trees. Quartet Compatibility is to decide whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that Quartet Compatibility is NP-hard but there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial time algorithms for Quartet Compatibility for these systems. We also see that complete/full multipartite quartet systems naturally arise from a limited situation of block-restricted measurement.

DOI： 10.4230/LIPIcs.ISAAC.2018.57

Scopus

Publishing type：Research paper (scientific journal)  

In this article, we develop an O((m log k)MSF(n, m, 1))-time algorithm to find a half-integral node-capacitated multiflow of the maximum total flow-value in a network with n nodes, m edges, and k terminals, where MSF(n, m, γ ) denotes the time complexity of solving the maximum submodular flow problem in a network with n nodes, m edges, and the complexity γ of computing the exchange capacity of the submodular function describing the problem. By using Fujishige-Zhang algorithm for submodular flow, we can find a maximum half-integral multiflow in O(mn 3 log k) time. This is the first combinatorial strongly polynomial time algorithm for this problem. Our algorithm is built on a developing theory of discrete convex functions on certain graph structures. Applications include “ellipsoid-free” combinatorial implementations of a 2-approximation algorithm for the minimum node-multiway cut problem by Garg, Vazirani, and Yannakakis.

DOI： 10.1145/3291531

Scopus

Publishing type：Research paper (scientific journal)  

A k-submodular function is a generalization of submodular and bisubmodular functions. This paper establishes a compact representation for minimizers of a k-submodular function by a poset with inconsistent pairs (PIP). This is a generalization of Ando–Fujishige’s signed poset representation for minimizers of a bisubmodular function. We completely characterize the class of PIPs (elementary PIPs) arising from k-submodular functions. We give algorithms to construct the elementary PIP of minimizers of a k-submodular function f for three cases: (i) a minimizing oracle of f is available, (ii) f is network-representable, and (iii) f arises from a Potts energy function. Furthermore, we provide an efficient enumeration algorithm for all maximal minimizers of a Potts k-submodular function. Our results are applicable to obtain all maximal persistent labelings in actual computer vision problems. We present experimental results for real vision instances.

DOI： 10.1007/s10878-017-0142-0

Scopus

Publishing type：Research paper (scientific journal)  

Björklund and Husfeldt developed a randomized polynomial time algorithm to solve the shortest two disjoint paths problem. Their algorithm is based on computation of permanents modulo 4 and the isolation lemma. In this paper, we consider the following generalization of the shortest two disjoint paths problem, and develop a similar algebraic algorithm. The shortest perfect (A+ B) -path packing problem is: given an undirected graph G and two disjoint node subsets A, B with even cardinalities, find shortest | A| / 2 + | B| / 2 disjoint paths whose ends are both in A or both in B. Besides its NP-hardness, we prove that this problem can be solved in randomized polynomial time if | A| + | B| is fixed. Our algorithm basically follows the framework of Björklund and Husfeldt but uses a new technique: computation of hafnian modulo 2 k combined with Gallai’s reduction from T-paths to matchings. We also generalize our technique for solving other path packing problems, and discuss its limitation.

DOI： 10.1007/s00453-017-0334-0

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we develop a polynomial time algorithm to compute a Dulmage–Mendelsohn-type decomposition of a matrix partitioned into submatrices of rank at most 1.

DOI： 10.1016/j.laa.2018.02.008

Scopus

Publishing type：Research paper (international conference proceedings)  

A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions. An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper-Živný classified the tractability of binary VCSP instances according to the concept of “triangle,” and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa-Murota-Živný made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this paper, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.

DOI： 10.4230/LIPIcs.STACS.2018.39

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we study classes of discrete convex functions: submodular functions on modular semilattices and L-convex functions on oriented modular graphs. They were introduced by the author in complexity classification of minimum 0-extension problems. We clarify the relationship to other discrete convex functions, such as k-submodular functions, skew-bisubmodular functions, L-convex functions, tree submodular functions, and UJ-convex functions. We show that they actually can be viewed as submodular/L-convex functions in our sense. We also prove a sharp iteration bound of the steepest descent algorithm for minimizing our L-convex functions. The underlying structures, modular semilattices and oriented modular graphs, have rich connections to projective and polar spaces, Euclidean building, and metric spaces of global nonpositive curvature (CAT(0) spaces). By utilizing these connections, we formulate an analogue of the Lovász extension, introduce well-behaved subclasses of submodular/L-convex functions, and show that these classes can be characterized by the convexity of the Lovász extension. We demonstrate applications of our theory to combinatorial optimization problems that include multicommodity flow, multiway cut, and related labeling problems: these problems had been outside the scope of discrete convex analysis so far.

DOI： 10.15807/jorsj.61.71

Scopus

Publishing type：Research paper (scientific journal)  

We study a representation of an antimatroid by Horn rules, motivated by its recent application to computer-aided educational systems. We associate any set R of Horn rules with the unique maximal antimatroid A(R) that is contained in the union-closed family K(R) naturally determined by R. We address algorithmic and Boolean function theoretic aspects on the association R↦A(R), where R is viewed as the input. We present linear time algorithms to solve the membership problem and the inference problem for A(R). We also provide efficient algorithms for generating all members and all implicates of A(R). We show that this representation is essentially equivalent to the Korte–Lovász representation of antimatroids by rooted sets. Based on the equivalence, we provide a quadratic time algorithm to construct the uniquely-determined minimal representation. These results have potential applications to computer-aided educational systems, where an antimatroid is used as a model of the space of possible knowledge states of learners, and is constructed by giving Horn queries to a human expert.

DOI： 10.1016/j.jmp.2016.09.002

Scopus

Publishing type：Research paper (scientific journal)  

A 0-extension of graph Γ is a metric d on a set V containing the vertex set VΓ of Γ such that d extends the shortest path metric of Γ and for all x∈V there exists a vertex s in Γ with d(x,s)=0. The minimum 0-extension problem 0-Ext[Γ] on Γ is: given a set V⊇VΓ and a nonnegative cost function c defined on the set of all pairs of V, find a 0-extension d of Γ with ∑xyc(xy)d(x,y) minimum. The 0-extension problem generalizes a number of basic combinatorial optimization problems, such as minimum (s,t)-cut problem and multiway cut problem. Karzanov proved the polynomial solvability of 0-Ext[Γ] for a certain large class of modular graphs Γ, and raised the question: What are the graphs Γ for which 0-Ext[Γ] can be solved in polynomial time? He also proved that 0-Ext[Γ] is NP-hard if Γ is not modular or not orientable (in a certain sense). In this paper, we prove the converse: if Γ is orientable and modular, then 0-Ext[Γ] can be solved in polynomial time. This completes the classification of graphs Γ for which 0-Ext[Γ] is tractable. To prove our main result, we develop a theory of discrete convex functions on orientable modular graphs, analogous to discrete convex analysis by Murota, and utilize a recent result of Thapper and Živný on valued CSP.

DOI： 10.1007/s10107-014-0824-7

Scopus

Publishing type：Research paper (international conference proceedings)  

k-submodular functions were introduced by Huber and Kolmogorov as a generalization of bisubmodular functions. This paper establishes a compact representation of minimizers of k-submodular functions by posets with inconsistent pairs (PIPs), and completely characterizes the class of PIPs (elementary PIPs) corresponding to minimizers of k-submodular functions. Our representation coincides with Birkhoff’s representation theorem if k = 1 and with signed-poset representation by Ando and Fujishige if k = 2.We also give algorithms to construct the elementary PIP representing the minimizers of a k-submodular function f for three cases: (i) a minimizing oracle of f is available, (ii) f is networkrepresentable, and (iii) f is the objective function of the relaxation of multiway cut problem. Furthermore, we provide an efficient algorithm to enumerate all maximal minimizers from the PIP representation. Our results are applied to obtain all maximal persistent assignments in labeling problems arising from computer vision.

DOI： 10.1007/978-3-319-45587-7_33

Scopus

Publishing type：Research paper (scientific journal)  

In this note, we consider the uncrossing game for a skew-supermodular function f, which is a two-player game with players, Red and Blue, and abstracts the uncrossing procedure in the cut-covering linear program associated with f. Extending the earlier results by Karzanov for {0, 1}-valued skew-supermodular functions, we present an improved polynomial time strategy for Red to win, and give a strongly polynomial time uncrossing procedure for dual solutions of the cut-covering LP as its consequence. We also mention its implication on the optimality of laminar solutions.

DOI： 10.15807/jorsj.59.218

Scopus

Publishing type：Research paper (scientific journal)  

k-submodular functions, introduced by Huber and Kolmogorov, are functions defined on {0, 1, 2;...,k}n satisfying certain submodular-type inequalities. k-submodular functions typically arise as relaxations of NP-hard problems, and the relaxations by k-submodular functions play key roles in design of eficient, approximation, or fixed-parameter tractable algorithms. Motivated by this, we consider the following problem: Given a function f :{1,2...,k}n→ℝ∪{+∞}, determine whether f can be extended to a k-submodular function g : {0,1,2,...K,}n→ℝ∪{+∞}, where g is called a k-submodular relaxation of f, i.e., the restriction of g on {1,2,...k,}n is equal to f. We give a characterization, in terms of polymorphisms, of the functions which admit a k-submodular relaxation, and also give a combinatorial O((kn)2)-time algorithm to find a k-submodular relaxation or establish that a k-submodular relaxation does not exist. Our algorithm has interesting properties: (1) If the input function is integer valued, then our algorithm outputs a half-integral relaxation, and (2) if the input function is binary, then our algorithm outputs the unique optimal relaxation. We present applications of our algorithm to valued constraint satisfaction problems.

DOI： 10.1137/15M101926X

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we develop a theory of new classes of discrete convex functions, called L-extendable functions and alternating L-convex functions, defined on the product of trees. We establish basic properties for optimization: a local-to-global optimality criterion, the steepest descend algorithm by successive k-submodular function minimizations, the persistency property, and the proximity theorem. Our theory is motivated by minimum cost free multiflow problem. To this problem, Goldberg and Karzanov gave two combinatorial weakly polynomial time algorithms based on capacity and cost scalings, without explicit running time. As an application of our theory, we present a new simple polynomial proximity scaling algorithm to solve minimum cost free multiflow problem in O(nlog(nAC)MF(kn,km)) time, where n is the number of nodes, m is the number of edges, k is the number of terminals, A is the maximum of edge-costs, C is the total sum of edge-capacities, and MF(^n′,^m′) denotes the time complexity to find a maximum flow in a network of ^n′ nodes and ^m′ edges. Our algorithm is designed to solve, in the same time complexity, a more general class of multiflow problems, minimum cost node-demand multiflow problem, and is the first combinatorial polynomial time algorithm to this class of problems. We also give an application to network design problem.

DOI： 10.1016/j.disopt.2015.07.001

Scopus

Publishing type：Research paper (scientific journal)  

Let T be a tree with a vertex set {1, 2, . . ., N}. Denote by dij the distance between vertices i and j. In this paper, we present an explicit combinatorial formula of principal minors of the matrix (tdij), and its applications to tropical geometry, study of multivariate stable polynomials, and representation of valuated matroids. We also give an analogous formula for a skew-symmetric matrix associated with T.

DOI： 10.1016/j.jcta.2015.02.005

Scopus

Publishing type：Research paper (scientific journal)  

In recent years, practical research related to distributed power generation and networked distribution grids has been increasing. This research uses a relatively abstract model for the cost reduction in the Digital Grid Power Network. In the Digital Grid, the traditional wide-area synchronous grid is divided into smaller segmented grids which are connected asynchronously. In this paper, we demonstrate how to formulate the minimized cost of power generation by using linear programming methods, while considering the cost of electric transmission and distribution and using asynchronous power interchange among separate grids.

DOI： 10.1140/epjst/e2014-02277-8

Scopus

Publishing type：Research paper (scientific journal)  

Network synthesis problem is the problem of constructing a minimum cost network satisfying a given flow-requirement. A classical result of Gomory and Hu is that if the cost is uniform and the flow requirement is integer-valued, then there exists a half-integral optimal solution. They also gave a simple algorithm to find a half-integral optimal solution. In this paper, we show that this half-integrality and the Gomory-Hu algorithm can be extended to a class of fractional cut-covering problems defined by skew-supermodular functions. Application to approximation algorithm is also given. © The Operations Research Society of Japan.

DOI： 10.15807/jorsj.57.63

Scopus

Publishing type：Research paper (scientific journal)  

Cognitive radio technology improves radio resource usage by reconfiguring the wireless connection settings according to the optimum decisions, which are made on the basis of the collected context information. This paper focuses on optimization algorithms for decision making to optimize radio resource usage in heterogeneous cognitive wireless networks. For networks with centralized management, we proposed a novel optimization algorithm whose solution is guaranteed to be exactly optimal. In order to avoid an exponential increase of computational complexity in large-scale wireless networks, we model the target optimization problem as a minimum cost-flow problem and find the solution of the problem in polynomial time. For the networks with decentralized management, we propose a distributed algorithm using the distributed energy minimization dynamics of the Hopfield-Tank neural network. Our algorithm minimizes a given objective function without any centralized calculation. We derive the decision-making rule for each terminal to optimize the entire network. We demonstrate the validity of the proposed algorithms by several numerical simulations and the feasibility of the proposed schemes by designing and implementing them on experimental cognitive radio network systems. © 2014 IEEE.

DOI： 10.1109/JPROC.2014.2306255

Scopus

Publishing type：Research paper (scientific journal)  

We consider the weighted maximum multiflow problem with respect to a terminal weight. We show that if the dimension of the tight span associated with the weight is at most 2, then this problem has a 1=12-integral optimal multiflow for every Eulerian supply graph. This result solves a weighted generalization of Karzanov's conjecture for classifying commodity graphs with finite fractionality. In addition, our proof technique proves the existence of an integral or half-integrality optimal multiflow for a large class of multiflow maximization problems, and it gives a polynomial time algorithm. © 2014 INFORMS.

DOI： 10.1287/moor.2013.0600

Scopus

Publishing type：Research paper (scientific journal)  

Given an undirected graph G=(V,E) with a terminal set S⊆V, a weight function [InlineEquation not available: see fulltext.] on terminal pairs, and an edge-cost a:E→Z+, the μ-weighted minimum-cost edge-disjoint S-paths problem (μ-CEDP) is to maximize ∑P∈Pμμ(sP, tP)−a(P) over all edge-disjoint sets P of S-paths, where sP, tP denote the ends of P and a(p) is the sum of edge-cost a(e) over edges e in P. Our main result is a complete characterization of terminal weights μ for which μ-CEDP is tractable and admits a combinatorial min–max theorem. We prove that if μ is a tree metric, then μ-CEDP is solvable in polynomial time and has a combinatorial min–max formula, which extends Mader’s edge-disjoint S-paths theorem and its minimum-cost generalization by Karzanov. Our min–max theorem includes the dual half-integrality, which was earlier conjectured by Karzanov for a special case. We also prove that μ-EDP, which is μ-CEDP with a=0, is NP-hard if μ is not a truncated tree metric, where a truncated tree metric is a weight function represented as pairwise distances between balls in a tree. On the other hand, μ-CEDP for a truncated tree metric μ reduces to μ′-CEDP for a tree metric μ′. Thus our result is best possible unless P = NP. As an application, we obtain a good approximation algorithm for μ-EDP with “near” tree metric μ by utilizing results from the theory of low-distortion embedding.

DOI： 10.1007/s10107-013-0713-5

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we establish a novel duality relationship between node-capacitated multiflows and tree-shaped facility locations. We prove that the maximum value of a tree-distance-weighted maximum node-capacitated multiflow problem is equal to the minimum value of the problem of locating subtrees in a tree, and the maximum is attained by a half-integral multiflow. Utilizing this duality, we show that a half-integral optimal multiflow and an optimal location can be found in strongly polynomial time. These extend previously known results in the maximum free multiflow problems. We also show that the set of tree-distance weights is the only class having bounded fractionality in maximum node-capacitated multiflow problems. © 2011 Springer and Mathematical Optimization Society.

DOI： 10.1007/s10107-011-0506-7

Scopus

Publishing type：Research paper (international conference proceedings)  

The minimum 0-extension problem 0-Ext[Γ] on a graph Γ is: given a set V including the vertex set VΓ of Γ and a nonnegative cost function c denned on the set of all pairs of V, find a 0-extension d of the path metric dΓ of Γ with ∑xy c(xy)d(x, y) minimum, where a 0-extension is a metric d on V such that the restriction of d to VΓ coincides with d Γ and for all x ∈ V there exists a vertex s in Γ with d(x, s) = 0. 0-Ext[Γ] includes a number of basic combinatorial optimization problems, such as minimum (s, t)-cut problem and multiway cut problem. Karzanov proved the polynomial solvability for a certain large class of modular graphs, and raised the question: What are the graphs Γ for which 0-Ext[Γ] can be solved in polynomial time? He also proved that 0-Ext[Γ] is NP-hard if Γ is not modular or not orientable (in a certain sense). In this paper, we prove the converse: if Γ is orientable and modular, then 0-Ext[Γ] can be solved in polynomial time. This completes the classification of the tractable graphs for the 0-extension problem. To prove our main result, we develop a theory of discrete convex functions on orientable modular graphs, analogous to discrete convex analysis by Murota, and utilize a recent result of Thapper and Živný on Valued-CSP. Copyright © SIAM.

Scopus

Publishing type：Research paper (scientific journal)  

An extension (V, d) of a metric space (S, μ) is a metric space with S ⊆ V, and is said to be tight if there is no other extension (V, d′) of (S, μ) with d′ ≤ d. Isbell and Dress independently found that every tight extension embeds isometrically into a certain metrized polyhedral complex associated with (S, μ), called the tight span. This paper develops an analogous theory for directed metrics, which are "not necessarily symmetric" distance functions satisfying the triangle inequality. We introduce a directed version of the tight span and show that it has a universal embedding property for tight extensions. Also we introduce a new natural class of extensions, called cyclically tight extensions, and we show that there also exists a certain polyhedral complex having a universal property relative to cyclically tightness. This polyhedral complex coincides with (a fiber of) the tropical polytope spanned by the column vectors of -μ, which was earlier introduced by Develin and Sturmfels. Thus this gives a tight-span interpretation to the tropical polytope generated by a nonnegative square matrix satisfying the triangle inequality. As an application, we prove the following directed version of the tree metric theorem: A directed metric μ is a directed tree metric if and only if the tropical rank of -μ is at most two. Also we describe how tight spans and tropical polytopes are applied to the study of multicommodity flows in directed networks. © 2012 Springer Basel AG.

DOI： 10.1007/s00026-012-0146-5

Scopus

Publishing type：Research paper (scientific journal)  

We consider the multiflow feasibility problem whose demand graph is the vertex-disjoint union of two triangles. We show that this problem has a 1/12-integral solution whenever it is feasible and satisfies the Euler condition. This solves a conjecture raised by Karzanov, and completes the classification of the demand graphs having bounded fractionality. We reduce this problem to the multiflow maximization problem whose terminal weight is the graph metric of the complete bipartite graph, and show that it always has a 1/12-integral optimal multiflow for every inner Eulerian graph. © 2012 Elsevier Inc..

DOI： 10.1016/j.jctb.2012.02.001

Scopus

Publishing type：Research paper (scientific journal)  

In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight μ, we define a metrized polyhedral complex, called the directed tight span Tμ, and prove that the dual of the μ-weighted maximum multiflow problem reduces to a facility location problem on Tμ. Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by μ. By utilizing this duality, we establish the classifications of terminal weights admitting a combinatorial minmax relation (i) for every network and (ii) for every Eulerian network. Our result includes the LomonosovFrank theorem for directed free multiflows and IbarakiKarzanovNagamochi's directed multiflow locking theorem as special cases. © 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disopt.2011.03.001

Scopus

Publishing type：Research paper (scientific journal)  

In multiflow maximization problems, there are several combinatorial duality relations, such as the Ford-Fulkerson max-flow min-cut theorem for single commodity flows, Hu's max-biflow min-cut theorem for two-commodity flows, the Lovász-Cherkassky duality theorem for free multiflows, and so on. In this paper, we provide a unified framework for such multiflow combinatorial dualities by using the notion of a folder complex, which is a certain 2-dimensional polyhedral complex introduced by Chepoi. We show that for a nonnegative weight μ on terminal set, the μ-weighted maximum multiflow problem admits a combinatorial duality relation if and only if μ is represented by distances between certain subsets in a folder complex, and we show that the corresponding combinatorial dual problem is a discrete location problem on the graph of the folder complex. This extends a result of Karzanov in the case of metric weights. © 2011 Society for Industrial and Applied Mathematics.

DOI： 10.1137/090767054

Scopus

Publishing type：Research paper (scientific journal)  

This note addresses the undirected multiflow (multicommodity flow) theory. A multifiow in a network with terminal set T can be regarded as a single commodity (A, T\ A)-flow for any nonempty proper subset A C T by ignoring flows not connecting A and T \ A. A set system A on T is said to be lockable if for every network having T as terminal set there exists a multiflow being simultaneously a maximum (A, T \ A)-fiow for every A c A. The multiflow locking theorem, due to Karzanov and Lomonosov, says that A is lockable if and only if it is 9-cross-free. A multiflow can also be regarded as a single commodity (A, B)-flow for every partial cut (A, B) of terminals, where a partial cut is a pair of disjoint subsets (not necessarily a bipartition). Based on this observation, we study the locking property for partial cuts, and prove an analogous characterization for a lockable family of partial cuts. © 2010 The Operations Research Society of Japan.

DOI： 10.15807/jorsj.53.149

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we consider the metric packing problem for the commodity graph of disjoint two triangles K3+K3, which is dual to the multiflow feasibility problem for the commodity graph K3+K3. We prove a strengthening of Karzanov's conjecture concerning quarterintegral packings by certain bipartite metrics. © 2010 János Bolyai Mathematical Society and Springer Verlag.

DOI： 10.1007/s00493-010-2447-9

Scopus

Publishing type：Research paper (international conference proceedings)  

This paper addresses a fundamental issue in the multicommodity flow theory. For an undirected capacitated supply graph (G,c) having commodity graph H, the maximum multiflow problem is to maximize the total flow-value of multicommodity flows with respect to (G,c;H). For a commodity graph H, the fractionality of H is the least positive integer k with property that there exists a 1/k-integral optimal multiflow in the maximum multiflow problem for every integer-capacitated supply graph (G,c) having H as a commodity graph. If such a positive integer k does not exist, then the fractionality is defined to be +∞. Around 1990, Karzanov raised the problem of classifying commodity graphs with finite fractionality, gave a necessary condition (property P) for the finiteness of fractionality, and conjectured that the property P is also sufficient. Our main result affirmatively solves Karzanov's conjecture in algorithmic form: If H has property P, then there exists a 1/24-integral optimal multiflow in maximum multiflow problem for every integer-capacitated supply graph having H as a commodity graph, and there exists a strongly polynomial time algorithm to find it. Our proof is based on a special combinatorial duality relation involving a class of CAT(0) complexes, and on a fractional version of the splitting-off method for finding an optimal multiflow with a bounded denominator. © 2010 ACM.

DOI： 10.1145/1806689.1806707

Scopus

Publishing type：Research paper (scientific journal)  

In this paper, we give a complete characterization of the class of weighted maximum multiflow problems whose dual polyhedra have bounded fractionality. This is a common generalization of two fundamental results of Karzanov. The first one is a characterization of commodity graphs H for which the dual of maximum multiflow problem with respect to H has bounded fractionality, and the second one is a characterization of metrics d on terminals for which the dual of metric-weighed maximum multiflow problem has bounded fractionality. A key ingredient of the present paper is a nonmetric generalization of the tight span, which was originally introduced for metrics by Isbell and Dress. A theory of nonmetric tight spans provides a unified duality framework to the weighted maximum multiflow problems, and gives a unified interpretation of combinatorial dual solutions of several known min-max theorems in the multiflow theory. © 2009 Elsevier Inc. All rights reserved.

DOI： 10.1016/j.jctb.2009.03.001

Scopus

Publishing type：Research paper (scientific journal)  

We propose a new classifier, named electric network classifiers, for semi-supervised learning on graphs. Our classifier is based on nonlinear electric network theory and classifies data set with respect to the sign of electric potential. Close relationships to C-SVM and graph kernel methods are revealed. Unlike other graph kernel methods, our classifier does not require heavy kernel computations but obtains the potential directly using efficient network flow algorithms. Furthermore, with flexibility of its formulation, our classifier can incorporate various edge characteristics; influence of edge direction, unsymmetric dependence and so on. Therefore, our classifier has the potential to tackle large complex real world problems. Experimental results show that the performance is fairly good compared with the diffusion kernel and other standard methods.

DOI： 10.15807/jorsj.50.219

Scopus

Publishing type：Research paper (scientific journal)  

This paper sheds new light on split decomposition theory and T-theory from the viewpoint of convex analysis and polyhedral geometry. By regarding finite metrics as discrete concave functions, Bandelt-Dress' split decomposition can be derived as a special case of more general decomposition of polyhedral/discrete concave functions introduced in this paper. It is shown that the combinatorics of splits discussed in connection with the split decomposition corresponds to the geometric properties of a hyperplane arrangement and a point configuration. Using our approach, the split decomposition of metrics can be naturally extended to distance functions, which may violate the triangle inequality, using partial split distances. © 2006 Springer Science+Business Media, Inc.

DOI： 10.1007/s00454-006-1243-1

Scopus

Publishing type：Research paper (scientific journal)  

A characterization is given to the distance between subtrees of a tree defined as the shortest path length between subtrees. This is a generalization of the four-point condition for tree metrics. For this, we use the theory of the tight span and obtain an extension of the famous result by Dress that a metric is a tree metric if and only if its tight span is a tree. © Birkhäuser Verlag, Basel, 2006.

DOI： 10.1007/s00026-006-0277-7

Scopus

Publishing type：Research paper (scientific journal)  

We reveal a close relationship between quadratic M-convex functions and tree metrics: A quadratic function defined on the integer lattice points is M-convex if and only if it has a tree representation. Furthermore, a discrete analogue of the Hessian matrix is defined for functions on the integer points. A function is M-convex if and only if the negative of the 'discrete Hessian matrix' is a tree metric matrix at each integer point. Thus, the M-convexity of a function can be characterized by that of its local quadratic approximations.

DOI： 10.1007/bf03167590

Scopus