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

摘要： 双权重网络优化问题通常是寻找一个满足指定子图结构的边子集,使得关于两种权重的比值达到最小。在本文研究的问题中,对于找到的边子集需要继续执行构建处理,目标是使得构建操作所需总费用与所选边子集总长度的比值达到最小,其规范描述如下:设有图G=(V,E),边集合E上定义了长度权重w:E→Z⁺和构建费用权重c:E→Z⁺,给定一些购买单价为c₀并且长度均为常数L的特定材料,要在图G中寻找一个满足指定子图结构S的边子集E′,使用给定材料按照约定方式构建E′中所有边,目标是使得总费用与总长度的比值公式达到最小,这里k(E′)表示构建E′中所有边使用的材料根数。本文设计了两个渐进近似算法分别求解该问题的两种情况,并针对一种特殊情况及相关问题给出三个不可近似性。

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