We consider the problem of finding a strongly connected spanning subdigraph with the minimum number of arcs in a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamilt...
详细信息
We consider the problem of finding a strongly connected spanning subdigraph with the minimum number of arcs in a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We show that the problem is polynomially solvable for quasi-transitive digraphs. We describe the minimum number of arcs in such a spanning subdigraph of a quasi-transitive digraph in terms of the path covering number. Our proofs are based on a number of results ( some of which are new and interesting in their own right) on the structure of cycles and paths in quasi-transitive digraphs and in extended semicomplete digraphs. In particular, we give a new characterization of the longest cycle in an extended semicomplete digraph. Finally, we point out that our proofs imply that the MSSS problem is solvable in polynomial time for all digraphs that can be obtained from strong semicomplete digraphs on at least two vertices by replacing each vertex with a digraph belonging to a family of digraphs whose path covering number can be decided in polynomial time.
作者：
Makino, KOno, HIbaraki, TKyushu Univ
Grad Sch Informat Sci & Elect Engn Dept Comp Sci & Commun Engn Fukuoka 8128581 Japan Osaka Univ
Grad Sch Engn Sci Div Syst & Human Sci Osaka 5608531 Japan Kyoto Univ
Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan
The interior and exterior functions of a Boolean function f were introduced in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209-231), as stability (or robustness) measures of the f. In this paper, we investigate...
详细信息
The interior and exterior functions of a Boolean function f were introduced in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209-231), as stability (or robustness) measures of the f. In this paper, we investigate the complexity of two problems alpha-INTERIOR and alpha-EXTERIOR, introduced therein. We first answer the question about the complexity of YANTERIOR left open in Makino and lbaraki (Discrete Appl. Math. 69 (1996) 209-231);it has no polynomial total time algorithm even if a is bounded by a constant, unless P = NP. However, for positive h-term DNF functions with h bounded by a constant, problems alpha-INTERIOR and alpha-EXTERIOR can be solved in (input) polynomial time and polynomial delay, respectively. Furthermore, for positive k-DNF functions, alpha-INTERIOR for two cases in which k = 1, and alpha and k are both bounded by a constant, can be solved in polynomial delay and in polynomial time, respectively. (C) 2003 Elsevier B.V. All rights reserved.
A graph is chordal if it contains no chordless cycles of length at least four and (q, t) if no set of at most q vertices induces more than t paths of length three. It is known that the isomorphism problem is isomorphi...
详细信息
A graph is chordal if it contains no chordless cycles of length at least four and (q, t) if no set of at most q vertices induces more than t paths of length three. It is known that the isomorphism problem is isomorphism complete for chordal graphs and for (6,3) graphs. We present polynomial methods to determine the automorphism partition and to test isomorphism of graphs which are both chordal and (6,3). The approach is based on the study of simplicial partitions of chordal graphs. It is proved that for chordal (6,3) graphs the automorphism partition coincides with the coarsest regular simplicial partition. This yields an O(n+m log n) isomorphism test.
We study out-branchings rooted at a given vertex s with the extra requirement that these satisfy certain balance conditions, such as balancing the number of arcs out of s, the number of vertices in each subtree of the...
详细信息
We study out-branchings rooted at a given vertex s with the extra requirement that these satisfy certain balance conditions, such as balancing the number of arcs out of s, the number of vertices in each subtree of the branching etc. We obtain polynomial algorithms for several of the problems and study the borderline between polynomial and NP-complete special cases of the problems. (C) 2015 Elsevier B.V. All rights reserved.
In this paper, the computational complexity of propositional clause set counter-factuals is discussed. It is shown that the computational complexity of propositional clause setcounterfactuals is at the second level of...
详细信息
In this paper, the computational complexity of propositional clause set counter-factuals is discussed. It is shown that the computational complexity of propositional clause setcounterfactuals is at the second level of the polynomial hierarchy, and that the computationalcomplexity of propositional Horn clause set counterfactuals is at the first level of the polynomialhierarchy. Furthermore, some polynomial algorithms are presented for some special propositionalclause set, such as the unique satisfiable clause set and the clause set of which only one subset isminimally inconsistent with the input clause whose inconsistency check can be solved in polynomialtime.
Given a digraph D = (V, A) and a positive integer k, a subset B subset of A is called a k-arborescence, if it is the disjoint union of k spanning arborescences. When also arc-costs c : A -> R are given, minimizing ...
详细信息
Given a digraph D = (V, A) and a positive integer k, a subset B subset of A is called a k-arborescence, if it is the disjoint union of k spanning arborescences. When also arc-costs c : A -> R are given, minimizing the cost of a k-arborescence is well-known to be tractable. In this paper we take on the following problem: what is the minimum cardinality of a set of arcs the removal of which destroys every minimum c-cost karborescence. Actually, the more general weighted problem is also considered, that is, arc weights w : A -> R+ (unrelated to c) are also given, and the goal is to find a minimum weight set of arcs the removal of which destroys every minimum c-cost k-arborescence. An equivalent version of this problem is where the roots of the arborescences are fixed in advance. In an earlier paper (Bernath and Pap, 2013) we solved this problem for k = 1. This work reports on other partial results on the problem. We solve the case when both c and w are uniform-that is, find a minimum size set of arcs that covers all k-arborescences. Our algorithm runs in polynomial time for this problem. The solution uses a result of Barasz et al. (2005) saying that the family of so-called in-solid sets (sets with the property that every proper subset has a larger in-degree) satisfies the Helly-property, and thus can be (efficiently) represented as a subtree hypergraph. We also give an algorithm for the case when only c is uniform but w is not. This algorithm is only polynomial if k is not part of the input. (C) 2016 Published by Elsevier B.V.
In this paper, we propose new large-update path-following interior-point algorithms for P-*(kappa)-nonlinear complementarity problems (NCPs). We define new classes of parametric kernel functions and based on these fun...
详细信息
In this paper, we propose new large-update path-following interior-point algorithms for P-*(kappa)-nonlinear complementarity problems (NCPs). We define new classes of parametric kernel functions and based on these functions new search directions and proximity measures are defined. We show that if a strictly feasible starting point is available and the undertaken problem satisfies certain conditions, then new large-update path-following interior-point algorithms for P-*(kappa)-NCPs have O((1 + 2 kappa) root n log n log n mu(0)/epsilon) iteration complexity which is currently the best known result for such methods. (C) 2012 Elsevier Ltd. All rights reserved.
In this paper we consider a type of constrained maximum capacity path (CMCP) problem which can be described as how to increase the capacity vector of a network so that the capacities of the maximum capacity path for e...
详细信息
In this paper we consider a type of constrained maximum capacity path (CMCP) problem which can be described as how to increase the capacity vector of a network so that the capacities of the maximum capacity path for every pair of nodes in the network can be increased to the maximum extent while the total cost for the increment of capacity is within a given budget limit. We transform this problem into solving some minimum spanning tree problems and propose a strongly polynomial algorithm for this problem. Finally we discuss other methods and show the advantage of the proposed algorithm.
In this paper, we give new polynomially testable sufficiency conditions for a given instance of the traveling salesman problem (TSP) to have an optimal tour that is pyramidal. This properly generalizes the Demidenko c...
详细信息
In this paper, we give new polynomially testable sufficiency conditions for a given instance of the traveling salesman problem (TSP) to have an optimal tour that is pyramidal. This properly generalizes the Demidenko condition and the conditions of Warren. We thus have new, nontrivial polynomially testable and polynomially solvable eases of TSP. (C) 1999 Elsevier Science Ltd. All rights reserved.
The cluster deletion problem (CD) asks for transforming a given graph into a disjoint union of cliques by removing as few edges as possible. CD is among the most studied combinatorial optimization problem and, for gen...
详细信息
The cluster deletion problem (CD) asks for transforming a given graph into a disjoint union of cliques by removing as few edges as possible. CD is among the most studied combinatorial optimization problem and, for general graphs, it is NP-hard. In the present paper, we identify a new polynomially solvable CD subproblem. We specifically propose a two-phase polynomial-time algorithm that optimally solves CD on the class of (butterfly,diamond)-free graphs. For this latter class of graphs, our two-phase algorithm provides optimal solutions even for another clustering variant, namely, cluster editing. Then, we propose a 2-optimal CD algorithm dedicated to the super-class of diamond-free graphs. For this class, we also show that CD, when parameterised by the number of deleted edges, admits a quadratic-size kernel. Finally, we report the results of experiments carried out on numerous diamond-free graphs, showing the effectiveness of the proposed approximate algorithm in terms of solution quality.
暂无评论