关键词: 子图构建, 分数目标函数, 最长路问题, 最小比路问题, 不可近似性

Abstract: Recently, we have noticed a practical application of subgraph construction problems. An enterprise plans to build a network with a specified subgraph structure (such as spanning tree, path, arborescence, etc.) using a special material of fixed length. When using this material to construct each edge, considering the relatively high splicing cost of materials, we agreed to use several complete materials and more than one section of leftover material for construction, to ensure the least splicing times. The total income of the completed network is proportional to its total length. The total income is used for three parts of expenses, among which a fixed percentage is used to pay benefits to shareholders, and the rest is used to repay construction expenses and pay salaries to employees. In order to raise the salary of employees and ensure the smooth operation of the entire network, the construction cost per unit length of network must be reduced as much as possible. Usually, doubly edge-weighted subgraph optimization problems are to find some edges which form a particular subgraph, the objective is to minimize a ratio on those two weight functions. Motivated by doubly edge-weighted subgraph optimization problems and above practical application, this paper study the following extended problem, which is denoted as SC-FRA. Given a weighted graph G=(V,E) equipped with a length function w: E→Z⁺ and a construction cost function c: E→Z⁺, suppose we have some stock pieces with fixed length L and unit price c₀. We seek an edge subset E′ that forms a specified subgraph structure S, subject to the additional constraint that every edge in E′ must be assembled from these stock pieces, the objective is to minimize 公式, where k (E′) is defined as the number of stock pieces with length L required to assemble all edges in the set E′. In the SC-FRA problem, the construction process of each e in E′ involves two distinct cases. (1)Case w(e)<L: Construct the edge e using a single segment of length w(e) cut from a stock piece of length L. (2)Case w(e)≥L: Use i(e)=「w(e)/L=-1 complete stock pieces of length L. Additionally, cut a residual segment of length w′(e)=w(e)-i(e)·L from another stock piece of length L. Combine these components to construct the edge e. And we should permit at most one piece of length less than L in any edge in such an edge-construction process, i.e., we should not permit at least two pieces of length less than L in some edge in our edge-construction process.
MEGIDDO (1979) established that the existence of a polynomial-time exact algorithm for linear objective minimization under certain constraints implies a corresponding polynomial-time exact algorithm for rational objective minimization within the same constraints. CORREA et al. (2010) developed a generalized approximation preservation framework. Their seminal result demonstrates that any linear objective optimization problem admitting an approximation algorithm induces a structurally equivalent rational objective counterpart sharing identical constraints and approximation factor. For describing the algorithm strategy for solving SC-FRA problem conveniently, we write S-LIN and S-RAT for optimization problems that have the same subgraph structure S as SC-FRA and minimize a linear objective function or rational objective function, respectively. We design algorithms to solve the SC-FRA problem according to the following strategy. Firstly, we construct an instance of the S-RAT problem from an instance of the SC-FRA problem. And then, we invoke Megiddo or Correa’s algorithm to solve the instance of the S-RAT problem, thus an edge subset E′ is obtained. Finally, the FFD algorithm is executed to construct all the edges in E′ with material of length L.
Our methodology yields three fundamental results. (1)When the S-LIN problem admits a polynomial-time exact algorithm, we derive an asymptotically optimal polynomial-time solution for SC-FRA, achieving a cost-to-length ratio that is guaranteed to exceed the optimum by at most c₀/L. (2)For NP-hard S-LIN instances with existing α-approximation algorithms, our framework constructs an asymptotic α-approximation scheme for SC-FRA. (3)When SC-FRA’s subgraph structure corresponds to a path, we prove that both SC-FRA and the corresponding S-RAT problem (i.e. the minimum-ratio path problem) exhibit inherent inapproximability within factor f(n), where f(n) is a polynomial-time computable function.

Key words: subgraph construction, fractional objective function, the longest path problem, the minimum ratio path problem, inapproximability