Authors:Faisal N. Abu-Khzam; Cristina Bazgan; Katrin Casel; Henning Fernau Pages: 2517 - 2550 Abstract: Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios, however, the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality k without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to k. Further, we derive some polynomial-time solvable cases for \(k=2\) with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of k. PubDate: 2018-09-01 DOI: 10.1007/s00453-017-0374-5 Issue No:Vol. 80, No. 9 (2018)

Authors:Sushmita Gupta; Sanjukta Roy Pages: 2551 - 2573 Abstract: In this paper we consider a problem that arises from a strategic issue in the stable matching model (with complete preference lists) from the viewpoint of exact-exponential time algorithms. Specifically, we study the Stable Extension of Partial Matching (SEOPM) problem, where the input consists of the complete preference lists of men, and a partial matching. The objective is to find (if one exists) a set of preference lists of women, such that the men-optimal Gale–Shapley algorithm outputs a perfect matching that contains the given partial matching. Kobayashi and Matsui (Algorithmica 58:151–169, 2010) proved this problem is NP-complete. In this article, we give an exact-exponential algorithm for SEOPM running in time \(2^{{\mathcal {O}} (n)}\) , where n denotes the number of men/women. We complement our algorithmic finding by showing that unless Exponential Time Hypothesis (ETH) fails, our algorithm is asymptotically optimal. That is, unless ETH fails, there is no algorithm for SEOPM running in time \(2^{o(n)}\) . Our algorithm is a non-trivial combination of a parameterized algorithm for Subgraph Isomorphism, a relationship between stable matching and finding an out-branching in an appropriate graph and enumerating all possible non-isomorphic out-branchings. Our results cover both the cases when the preference lists are strict and complete, and when they are strict but possibly incomplete. PubDate: 2018-09-01 DOI: 10.1007/s00453-017-0382-5 Issue No:Vol. 80, No. 9 (2018)

Authors:Michael Etscheid; Matthias Mnich Pages: 2574 - 2615 Abstract: The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results: We show that an algorithm by Crowston et al. (Algorithmica 72(3):734–757, 2015) for (Signed) Max-Cut Above Edwards−Erd ő s Bound can be implemented so as to run in linear time \(8^k\cdot O(m)\) ; this significantly improves the previous analysis with run time \(8^k\cdot O(n^4)\) . We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards−Erd ő s Bound with O(k) vertices, improving a kernel with \(O(k^3)\) vertices by Crowston et al. (Theor Comput Sci 513:53–64, 2013). We improve all known kernels for parameterizations above strongly \(\lambda \) -extendible properties (a generalization of the Max-Cut results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics, Guwahati, 2013) from \(O(k^3)\) vertices to O(k) vertices. Therefore, Max Acyclic Subdigraph parameterized above Poljak–Turzík bound admits a kernel with O(k) vertices and can be solved in \(2^{O(k)}\cdot n^{O(1)}\) time; this answers an open question by Crowston et al. (Proceedings of FSTTCS 2012, Leibniz international proceedings in informatics, Hyderabad, 2012). All presented kernels can be computed in time O(km). PubDate: 2018-09-01 DOI: 10.1007/s00453-017-0388-z Issue No:Vol. 80, No. 9 (2018)

Authors:Aritra Banik; Fahad Panolan; Venkatesh Raman; Vibha Sahlot Pages: 2616 - 2636 Abstract: Frèchet distance is an important geometric measure that captures the distance between two curves or more generally point sets. In this paper, we consider a natural variant of Fréchet distance problem with multiple choice, provide an approximation algorithm and address its parameterized and kernelization complexity. A multiple choice problem consists of a set of color classes \(\mathcal {Q}=\{Q_1,Q_2,\ldots ,Q_n\}\) , where each class \(Q_i\) consists of a pair of points \(Q_i = \{q_i, \bar{q_i}\}\) . We call a subset \(A\subset \{q_i , \bar{q_i}:1\le i\le n\}\) conflict-free if A contains at most one point from each color class. The standard objective in multiple choice problem is to select a conflict-free subset that optimizes a given function. Given a line-segment \(\ell \) and a set \(\mathcal {Q}\) of a pair of points in \(\mathbb {R}^2\) , our objective is to find a conflict-free subset that minimizes the Fréchet distance between \(\ell \) and the point set, where the minimum is taken over all possible conflict-free subsets. We first show that this problem is NP-hard, and provide a 3-approximation algorithm. Then we develop a simple randomized FPT algorithm for the problem when parametrized by the solution size, which is later derandomized using universal family of sets. We believe that our derandomization technique can be of independent interest, and can be used to solve other parameterized multiple choice problems. The randomized algorithm runs in \(\mathcal {O}(2^k n \log ^2 n)\) time, and the derandomized deterministic algorithm runs in \(2^k k^{\mathcal {O}(\log k)} n \log ^2 n\) time, where k, the parameter, is the number of elements in the conflict-free subset solution. Finally we present a simple branching algorithm for the problem running in \(\mathcal {O}(2^k n\log n)\) time. We also show that the problem does not have a polynomial sized kernel under standard complexity theoretic assumptions. PubDate: 2018-09-01 DOI: 10.1007/s00453-017-0352-y Issue No:Vol. 80, No. 9 (2018)

Authors:R. Krithika; Abhishek Sahu; Prafullkumar Tale Pages: 2637 - 2655 Abstract: We study the parameterized complexity of various graph theoretic problems in the dynamic framework where the input graph is being updated by a sequence of edge additions and deletions. Vertex subset problems on graphs typically deal with finding a subset of vertices having certain properties. In real world applications, the graph under consideration often changes over time and due to this dynamics, the solution at hand might lose the desired properties. The goal in the area of dynamic graph algorithms is to efficiently maintain a solution under these changes. Recomputing a new solution on the new graph is an expensive task especially when the number of modifications made to the graph is significantly smaller than the size of the graph. In the context of parameterized algorithms, two natural parameters are the size k of the symmetric difference of the edge sets of the two graphs (on n vertices) and the size r of the symmetric difference of the two solutions. We study the Dynamic \(\Pi \) -Deletion problem which is the dynamic variant of the classical \(\Pi \) -Deletion problem and show NP-hardness, fixed-parameter tractability and kernelization results. For specific cases of Dynamic \(\Pi \) -Deletion such as Dynamic Vertex Cover and Dynamic Feedback Vertex Set, we describe improved algorithms and linear kernels. Specifically, we show that Dynamic Vertex Cover has a deterministic algorithm with \(1.0822^k n^{\mathcal {O}(1)}\) running time and Dynamic Feedback Vertex Set has a randomized algorithm with \(1.6667^k n^{\mathcal {O}(1)}\) running time. We also show that Dynamic Connected Feedback Vertex Set can be solved in \(2^{\mathcal {O}(k)} n^{\mathcal {O}(1)}\) time. For each of Dynamic Connected Vertex Cover, Dynamic Dominating Set and Dynamic Connected Dominating Set, we describe an algorithm with \(2^k n^{\mathcal {O}(1)}\) running time and show that this is the optimal running time (up to polynomial factors) assuming the Set Cover Conjecture. PubDate: 2018-09-01 DOI: 10.1007/s00453-017-0349-6 Issue No:Vol. 80, No. 9 (2018)

Authors:Diptapriyo Majumdar; Venkatesh Raman Pages: 2683 - 2724 Abstract: A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure in the input. In particular, we consider parameterizations where the parameter is (instead of the solution size), the distance to a class of graphs where the problem is polynomial time solvable, and sometimes smaller than the solution size. Here, by distance to a class of graphs, we mean the minimum number of vertices whose removal results in a graph in the class. Such a set of vertices is also called the ‘deletion set’. In this paper, we show that FVS is fixed-parameter tractable by an \({{\mathcal {O}}}(2^k n^{{{\mathcal {O}}}(1)})\) time algorithm, but is unlikely to have polynomial kernel when parameterized by the number of vertices of the graph whose degree is at least 4. This answers a question asked in an earlier paper. We also show that an algorithm with running time \({{\mathcal {O}}}((\sqrt{2} - \epsilon )^k n^{{{\mathcal {O}}}(1)})\) is not possible unless SETH fails. When parameterized by k, the number of vertices, whose deletion results in a split graph, we give an \({{\mathcal {O}}}(3.148^k n^{{{\mathcal {O}}}(1)})\) time algorithm. When parameterized by k, the number of vertices whose deletion results in a cluster graph (a disjoint union of cliques), we give an \({{\mathcal {O}}}(5^k n^{{{\mathcal {O}}}(1)})\) algorithm. Regarding kernelization results, we show that When parameterized by k, the number of vertices, whose deletion results in a pseudo-forest, FVS has an \({{\mathcal {O}}}(k^7)\) vertices kernel improving from the previously known \({{\mathcal {O}}}(k^{10})\) bound. When parameterized by the number k of vertices, whose deletion results in a mock-d-forest, we give a kernel with \({{\mathcal {O}}}(k^{3d+3})\) vertices. We also prove a lower bound of \(\varOmega (k^{d+2})\) size (under complexity theoretic assumptions). Mock-forest is a graph where each vertex is contained in at most one cycle. Mock-d-forest for a constant d is a mock-forest where each component has at most d cycles. PubDate: 2018-09-01 DOI: 10.1007/s00453-018-0419-4 Issue No:Vol. 80, No. 9 (2018)

Authors:Atsuki Nagao; Kazuhisa Seto; Junichi Teruyama Pages: 2725 - 2741 Abstract: We present a satisfiability algorithm for k-indexed binary decision diagrams (k-IBDDs). The proposed exponential space and deterministic algorithm solves the satisfiability of k-IBDDs, i.e., k-IBDD SAT, for instances with n variables and cn nodes in \(O\left( 2^{(1-\mu _k(c))n}\right) \) time, where \(\mu _k(c) = \varOmega \left( \frac{1}{(k^2 2^k\log {c})^{2^{k-1}-1}}\right) \) . We also provide a polynomial space and deterministic algorithm that solves a k-IBDD SAT of polynomial size for any constant \(k \ge 2\) in \(O\left( 2^{ n - n^{ 1/2^{k-1} }}\right) \) time. In addition, the proposed algorithm is applicable to equivalence checking of two IBDDs. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0332-2 Issue No:Vol. 80, No. 10 (2018)

Authors:Zahed Rahmati; Timothy M. Chan Pages: 2742 - 2756 Abstract: Given a set P of n moving points in fixed dimension d, where the trajectory of each point is a polynomial of degree bounded by some constant, we present a kinetic data structure (KDS) for maintenance of the closest pair on P. Assuming the closest pair distance is between 1 and \(\varDelta \) over time, our KDS uses \(O(n \log \varDelta )\) space and processes \(O(n^{2} \beta \log \varDelta \log n + n^{2} \beta \log \varDelta \log \log \varDelta )\) events, each in worst-case time \(O(\log ^2 n + \log ^2 \log \varDelta )\) . Here, \(\beta \) is an extremely slow-growing function. The locality of the KDS is \(O(\log n + \log \log \varDelta )\) . Our closest pair KDS supports insertions and deletions of points. An insertion or deletion takes worst-case time \(O(\log \varDelta \log ^2 n + \log \varDelta \log ^2 \log \varDelta )\) . Also, we use a similar approach to provide a KDS for the all \(\varepsilon \) -nearest neighbors in \(\mathbb {R}^d\) . The complexities of the previous KDSs, for both closest pair and all \(\varepsilon \) -nearest neighbors, have polylogarithmic factors, where the number of logs depends on dimension d. Assuming \(\varDelta \) is polynomial in n, our KDSs obtain improvements on the previous KDSs. Our solutions are based on a kinetic clustering on P. Though we use ideas from the previous clustering KDS by Hershberger, we simplify and improve his work. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0338-9 Issue No:Vol. 80, No. 10 (2018)

Authors:Syed M. Meesum; Saket Saurabh Pages: 2757 - 2776 Abstract: In this paper we continue our study of graph modification problems defined by reducing the rank of the adjacency matrix of the given graph, and extend our results from undirected graphs to modifying the rank of skew-adjacency matrix of oriented graphs. An instance of a graph modification problem takes as input a graph G and a positive integer k, and the objective is to either delete k vertices/edges or edit k edges so that the resulting graph belongs to a particular family \(\mathcal{F}\) of graphs. Given a fixed positive integer r, we define \(\mathcal{F}_r\) as the family of oriented graphs where for each \(G\in \mathcal{F}_r\) , the rank of the skew-adjacency matrix of G is at most r. Using the family \(\mathcal{F}_r\) we do algorithmic study, both in classical and parameterized complexity, of the following graph modification problems: \(r\) -Rank Vertex Deletion, \(r\) -Rank Edge Deletion. We first show that both the problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time \(2^{\mathcal{O}(k \log r)}n^{\mathcal{O}(1)}\) for \(r\) -Rank Vertex Deletion, and an algorithm for \(r\) -Rank Edge Deletion running in time \(2^{\mathcal{O}(f(r) \sqrt{k} \log k )}n^{\mathcal{O}(1)}\) . In addition to our FPT results we design polynomial kernels for these problems. Our main structural result, which is the fulcrum of all our algorithmic results, is that for a fixed integer r the size of any “reduced graph” in \(\mathcal{F}_r\) is upper bounded by \(3^r\) . This result is of independent interest and generalizes a similar result of Kotlov and Lovász regarding reduced oriented graphs of rank r. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0340-2 Issue No:Vol. 80, No. 10 (2018)

Authors:Riley Murray; Samir Khuller; Megan Chao Pages: 2777 - 2798 Abstract: The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of n jobs on m distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into m “subjobs” and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0345-x Issue No:Vol. 80, No. 10 (2018)

Authors:Hassan AbouEisha; Shahid Hussain; Vadim Lozin; Jérôme Monnot; Bernard Ries; Viktor Zamaraev Pages: 2799 - 2817 Abstract: An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0346-9 Issue No:Vol. 80, No. 10 (2018)

Authors:Martijn van Ee; René Sitters Pages: 2818 - 2833 Abstract: The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem, the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we study the uniform model, where a vertex is in the active set with probability p independently of the other vertices, and give the first constant-factor approximation for a priori TRP. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0351-z Issue No:Vol. 80, No. 10 (2018)

Authors:Emile Ziedan; Deepak Rajendraprasad; Rogers Mathew; Martin Charles Golumbic; Jérémie Dusart Pages: 2834 - 2848 Abstract: A linear ordering of the vertices of a graph G separates two edges of G if both the endpoints of one precede both the endpoints of the other in the order. We call two edges \(\{a,b\}\) and \(\{c,d\}\) of G strongly independent if the set of endpoints \(\{a,b,c,d\}\) induces a \(2K_2\) in G. The induced separation dimension of a graph G is the smallest cardinality of a family \(\mathcal {L}\) of linear orders of V(G) such that every pair of strongly independent edges in G are separated in at least one of the linear orders in \(\mathcal {L}\) . For each \(k \in \mathbb {N}\) , the family of graphs with induced separation dimension at most k is denoted by \({\text {ISD}}(k)\) . In this article, we initiate a study of this new dimensional parameter. The class \({\text {ISD}}(1)\) or, equivalently, the family of graphs which can be embedded on a line so that every pair of strongly independent edges are disjoint line segments, is already an interesting case. On the positive side, we give characterizations for chordal graphs in \({\text {ISD}}(1)\) which immediately lead to a polynomial time algorithm which determines the induced separation dimension of chordal graphs. On the negative side, we show that the recognition problem for \({\text {ISD}}(1)\) is NP-complete for general graphs. Nevertheless, we show that the maximum induced matching problem can be solved efficiently in \({\text {ISD}}(1)\) . We then briefly study \({\text {ISD}}(2)\) and show that it contains many important graph classes like outerplanar graphs, chordal graphs, circular arc graphs and polygon-circle graphs. Finally, we describe two techniques to construct graphs with large induced separation dimension. The first one is used to show that the maximum induced separation dimension of a graph on n vertices is \(\Theta (\lg n)\) and the second one is used to construct AT-free graphs with arbitrarily large induced separation dimension. The second construction is also used to show that, for every \(k \ge 2\) , the recognition problem for \({\text {ISD}}(k)\) is NP-complete even on AT-free graphs. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0353-x Issue No:Vol. 80, No. 10 (2018)

Authors:Benjamin Grimmer Pages: 2849 - 2873 Abstract: We consider a variety of NP-Complete network connectivity problems. We introduce a novel dual-based approach to approximating network design problems with cut-based linear programming relaxations. This approach gives a 3/2-approximation to Minimum 2-Edge-Connected Spanning Subgraph that is equivalent to a previously proposed algorithm. One well-studied branch of network design models ad hoc networks where each node can either operate at high or low power. If we allow unidirectional links, we can formalize this into the problem Dual Power Assignment (DPA). Our dual-based approach gives a 3 / 2-approximation to DPA, improving the previous best approximation known of \(11/7\approx 1.57\) . Another standard network design problem is Minimum Strongly Connected Spanning Subgraph (MSCS). We propose a new problem generalizing MSCS and DPA called Star Strong Connectivity (SSC). Then we show that our dual-based approach achieves a 1.6-approximation ratio on SSC. As a consequence of our dual-based approximations, we prove new upper bounds on the integrality gaps of these problems. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0356-7 Issue No:Vol. 80, No. 10 (2018)

Authors:Uriel Feige; Yael Hitron Pages: 2874 - 2908 Abstract: We study the Ordered Covering (OC) problem. The input is a finite set of n elements X, a color function \(c:X \rightarrow \{0,1\}\) and a collection \(\mathcal {S}\) of subsets of X. A solution consists of an ordered tuple \(T=(S_1,\dots ,S_{\ell })\) of sets from \(\mathcal {S}\) which covers X, and a coloring \(g:\{S_i\}_{i=1}^\ell \rightarrow \{0,1\}\) such that \(\forall x \in X\) , the first set covering x in the tuple, namely \(S_j\) with \(j=\min \{i : x \in S_i\}\) , has color \(g(S_j)=c(x)\) . The minimization version is to find a solution using the minimum number of sets. Variants of OC include OC \((\alpha _0,\alpha _1)\) in which each element of color \(i \in \{0,1\}\) appears in at most \(\alpha _i\) sets of \(\mathcal {S}\) , and k–OC in which the first set of the solution \(S_1\) is required to have color 0, and there are at most \(k-1\) alternations of colors in the solution. Among other results we show: There is a polynomial time approximation algorithm for Min–OC(2, 2) with approximation ratio 2. (This is best possible unless Vertex Cover can be approximated within a ratio better than 2.) Moreover, Min–OC(2, 2) can be solved optimally in polynomial time if the underlying instance is bipartite. For every \(\alpha _0, \alpha _1 \ge 2\) , there is a polynomial time approximation algorithm for Min–3–OC \((\alpha _0,\alpha _1)\) with approximation \(\alpha _1(\alpha _0 - 1)\) . Unless the unique games conjecture is false, this is best possible. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0357-6 Issue No:Vol. 80, No. 10 (2018)

Authors:Bernhard Bliem; Stefan Woltran Pages: 2909 - 2940 Abstract: A secure set S in a graph is defined as a set of vertices such that for any \(X\subseteq S\) the majority of vertices in the neighborhood of X belongs to S. It is known that deciding whether a set S is secure in a graph is \(\mathrm {\text {co-}NP}\) -complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph G and integer k, a non-empty secure set for G of size at most k exists. In this work, we pinpoint the complexity of this problem by showing that it is \(\mathrm {\Sigma ^P_2}\) -complete. Furthermore, the problem has so far not been subject to a parameterized complexity analysis that considers structural parameters. In the present work, we prove that the problem is \(\mathrm {W[1]}\) -hard when parameterized by treewidth. This is surprising since the problem is known to be FPT when parameterized by solution size and “subset problems” that satisfy this property usually tend to be FPT for bounded treewidth as well. Finally, we give an upper bound by showing membership in \(\mathrm {XP}\) , and we provide a positive result in the form of an FPT algorithm for checking whether a given set is secure on graphs of bounded treewidth. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0358-5 Issue No:Vol. 80, No. 10 (2018)

Authors:Tim Nonner Pages: 2941 - 2956 Abstract: We are given an interval graph \( G = (V,E) \) where each interval \( I \in V\) has a weight \( w_I \in \mathbb {Q}^+ \) . The goal is to color the intervals \( V\) with an arbitrary number of color classes \( C_1, C_2, \ldots , C_k \) such that \( \sum _{i=1}^k \max _{I \in C_i} w_I \) is minimized. This problem, called max-coloring interval graphs or weighted coloring interval graphs, contains the classical problem of coloring interval graphs as a special case for uniform weights, and it arises in many practical scenarios such as memory management. Pemmaraju, Raman, and Varadarajan showed that max-coloring interval graphs is NP-hard [21] and presented a 2-approximation algorithm. We settle the approximation complexity of this problem by giving a polynomial-time approximation scheme (PTAS), that is, we show that there is an \( (1+\epsilon ) \) -approximation algorithm for any \( \epsilon > 0 \) . The PTAS also works for the bounded case where the sizes of the color classes are bounded by some arbitrary \( k \le n \) . PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0362-9 Issue No:Vol. 80, No. 10 (2018)

Authors:Naoyuki Kamiyama Pages: 2957 - 2971 Abstract: In this paper, we consider the non-negative submodular function minimization problem with covering type linear constraints. Assume that there exist m linear constraints, and we denote by \(\varDelta _i\) the number of non-zero coefficients in the ith constraints. Furthermore, we assume that \(\varDelta _1 \ge \varDelta _2 \ge \cdots \ge \varDelta _m\) . For this problem, Koufogiannakis and Young proposed a polynomial-time \(\varDelta _1\) -approximation algorithm. In this paper, we propose a new polynomial-time primal-dual approximation algorithm based on the approximation algorithm of Takazawa and Mizuno for the covering integer program with \(\{0,1\}\) -variables and the approximation algorithm of Iwata and Nagano for the submodular function minimization problem with set covering constraints. The approximation ratio of our algorithm is \(\max \{\varDelta _2, \min \{\varDelta _1, 1 + \varPi \}\}\) , where \(\varPi \) is the maximum size of a connected component of the input submodular function. PubDate: 2018-10-01 DOI: 10.1007/s00453-017-0363-8 Issue No:Vol. 80, No. 10 (2018)