3,512 research outputs found
An FPT Algorithm for Minimum Additive Spanner Problem
Get PDFFor a positive integer t and a graph G, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus t. The Minimum Additive t-Spanner Problem is to find an additive t-spanner with the minimum number of edges in a given graph, which is known to be NP-hard. Since we need to care about global properties of graphs when we deal with additive t-spanners, the Minimum Additive t-Spanner Problem is hard to handle and hence only few results are known for it. In this paper, we study the Minimum Additive t-Spanner Problem from the viewpoint of parameterized complexity. We formulate a parameterized version of the problem in which the number of removed edges is regarded as a parameter, and give a fixed-parameter algorithm for it. We also extend our result to the case with both a multiplicative approximation factor α and an additive approximation parameter β, which we call (α, β)-spanners
Finding a Maximum Restricted t-Matching via Boolean Edge-CSP
Get PDFThe problem of finding a maximum 2-matching without short cycles has received significant attention due to its relevance to the Hamilton cycle problem. This problem is generalized to finding a maximum t-matching which excludes specified complete t-partite subgraphs, where t is a fixed positive integer. The polynomial solvability of this generalized problem remains an open question. In this paper, we present polynomial-time algorithms for the following two cases of this problem: in the first case the forbidden complete t-partite subgraphs are edge-disjoint; and in the second case the maximum degree of the input graph is at most 2t-1. Our result for the first case extends the previous work of Nam (1994) showing the polynomial solvability of the problem of finding a maximum 2-matching without cycles of length four, where the cycles of length four are vertex-disjoint. The second result expands upon the works of Bérczi and Végh (2010) and Kobayashi and Yin (2012), which focused on graphs with maximum degree at most t+1. Our algorithms are obtained from exploiting the discrete structure of restricted t-matchings and employing an algorithm for the Boolean edge-CSP
One-Face Shortest Disjoint Paths with a Deviation Terminal
Get PDFFor an undirected graph G and distinct vertices s₁, t₁, … , s_k, t_k called terminals, the shortest k-disjoint paths problem asks for k pairwise vertex-disjoint paths P₁, … , P_k such that P_i connects s_i and t_i for i = 1, … , k and the sum of their lengths is minimized. This problem is a natural optimization version of the well-known k-disjoint paths problem, and its polynomial solvability is widely open. One of the best results on the shortest k-disjoint paths problem is due to Datta et al. [Datta et al., 2018], who present a polynomial-time algorithm for the case when G is planar and all the terminals are on one face. In this paper, we extend this result by giving a polynomial-time randomized algorithm for the case when all the terminals except one are on some face of G. In our algorithm, we combine the arguments of Datta et al. with some results on the shortest disjoint (A + B)-paths problem shown by Hirai and Namba [Hirai and Namba, 2018]. To this end, we present a non-trivial bijection between k disjoint paths and disjoint (A + B)-paths, which is a key technical contribution of this paper
Improved Analysis of Highest-Degree Branching for Feedback Vertex Set
Get PDFRecent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning heuristic. In this paper, we prove that this empirically fast algorithm runs in O(3.460^k n) time, where k is the solution size. This improves the previous best O(3.619^k n)-time deterministic algorithm obtained by Kociumaka and Pilipczuk (Inf. Process. Lett., 2014)
The Directed Disjoint Shortest Paths Problem
Get PDFIn the k disjoint shortest paths problem (k-DSPP), we are given a graph and its vertex pairs (s_1, t_1), ... , (s_k, t_k), and the objective is to find k pairwise disjoint paths P_1, ... , P_k such that each path P_i is a shortest path from s_i to t_i, if they exist. If the length of each edge is equal to zero, then this problem amounts to the disjoint paths problem, which is one of the well-studied problems in algorithmic graph theory and combinatorial optimization. Eilam-Tzoreff (1998) focused on the case when the length of each edge is positive, and showed that the undirected version of 2-DSPP can be solved in polynomial time. Polynomial solvability of the directed version was posed as an open problem by Eilam-Tzoreff (1998). In this paper, we solve this problem affirmatively, that is, we give a first polynomial time algorithm for the directed version of 2-DSPP when the length of each edge is positive. Note that the 2 disjoint paths problem in digraphs is NP-hard, which implies that the directed 2-DSPP is NP-hard if the length of each edge can be zero. We extend our result to the case when the instance has two terminal pairs and the number of paths is a fixed constant greater than two. We also show that the undirected k-DSPP and the vertex-disjoint version of the directed k-DSPP can be solved in polynomial time if the input graph is planar and k is a fixed constant
Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average
Get PDFWe study the problem of fairly allocating a set of indivisible goods to
multiple agents and focus on the proportionality, which is one of the classical
fairness notions. Since proportional allocations do not always exist when goods
are indivisible, approximate concepts of proportionality have been considered
in the previous work. Among them, proportionality up to the maximin good
(PROPm) has been the best approximate notion of proportionality that can be
achieved for all instances. In this paper, we introduce the notion of
proportionality up to the least valued good on average (PROPavg), which is a
stronger notion than PROPm, and show that a PROPavg allocation always exists
for all instances and can be computed in polynomial time. %% for all instances.
Our results establish PROPavg as a notable non-trivial fairness notion that can
be achieved for all instances. Our proof is constructive, and based on a new
technique that generalizes the cut-and-choose protocol and uses a recursive
technique.Comment: 21 pages, 3 figures, 2 table
An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover
Get PDFThe 2-Edge-Connected Spanning Subgraph problem (2-ECSS) is one of the most fundamental and well-studied problems in the context of network design. We are given an undirected graph G, and the objective is to find a 2-edge-connected spanning subgraph H of G with the minimum number of edges. For this problem, a lot of approximation algorithms have been proposed in the literature. In particular, very recently, Garg, Grandoni, and Ameli gave an approximation algorithm for 2-ECSS with a factor of 1.326, which is the best approximation ratio. In this paper, under the assumption that a maximum triangle-free 2-matching can be found in polynomial time in a graph, we give a (1.3+ε)-approximation algorithm for 2-ECSS, where ε is an arbitrarily small positive fixed constant. Note that a complicated polynomial-time algorithm for finding a maximum triangle-free 2-matching is announced by Hartvigsen in his PhD thesis, but it has not been peer-reviewed or checked in any other way. In our algorithm, we compute a minimum triangle-free 2-edge-cover in G with the aid of the algorithm for finding a maximum triangle-free 2-matching. Then, with the obtained triangle-free 2-edge-cover, we apply the arguments by Garg, Grandoni, and Ameli
Subquadratic Submodular Maximization with a General Matroid Constraint
Get PDFWe consider fast algorithms for monotone submodular maximization with a general matroid constraint. We present a randomized (1 - 1/e - ε)-approximation algorithm that requires Õ_{ε}(√r n) independence oracle and value oracle queries, where n is the number of elements in the matroid and r ≤ n is the rank of the matroid. This improves upon the previously best algorithm by Buchbinder-Feldman-Schwartz [Mathematics of Operations Research 2017] that requires Õ_{ε}(r² + √rn) queries.
Our algorithm is based on continuous relaxation, as with other submodular maximization algorithms in the literature. To achieve subquadratic query complexity, we develop a new rounding algorithm, which is our main technical contribution. The rounding algorithm takes as input a point represented as a convex combination of t bases of a matroid and rounds it to an integral solution. Our rounding algorithm requires Õ(r^{3/2} t) independence oracle queries, while the previously best rounding algorithm by Chekuri-Vondrák-Zenklusen [FOCS 2010] requires O(r² t) independence oracle queries. A key idea in our rounding algorithm is to use a directed cycle of arbitrary length in an auxiliary graph, while the algorithm of Chekuri-Vondrák-Zenklusen focused on directed cycles of length two
Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid
Get PDFA key theorem in algorithmic graph-minor theory is a min-max relation
between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of Robertson
and Seymour, which ultimately proves Wagner's Conjecture about the structure of minor-closed graph properties.
In 2008, Demaine and Hajiaghayi proved a remarkable linear min-max
relation for graphs excluding any fixed minor H: every H-minor-free
graph of treewidth at least c_H r has an r times r-grid minor for some
constant c_H. However, as they pointed out, there is still a major
problem left in this theorem. The problem is that their proof heavily
depends on Graph Minor Theory, most of which lacks explicit bounds and
is believed to have very large bounds. Hence c_H is not explicitly
given in the paper and therefore this result is usually not strong
enough to derive efficient algorithms.
Motivated by this problem, we give another (relatively short and
simple) proof of this result without using big machinery of Graph
Minor Theory. Hence we can give an explicit bound for c_H (an exponential function of a polynomial of |H|). Furthermore, our result
gives a constant w=2^O(r^2 log r) such that every graph of treewidth
at least w has an r times r-grid minor, which improves the previously
known best bound 2^Theta(r^5)$ given by Robertson, Seymour, and Thomas
in 1994
Edge-disjoint Odd Cycles in 4-edge-connected Graphs
Get PDFFinding edge-disjoint odd cycles is one of the most important problems
in graph theory, graph algorithm and combinatorial optimization. In
fact, it is closely related to the well-known max-cut problem. One of
the difficulties of this problem is that the Erdös-Pósa property does not hold for odd cycles in general. Motivated by this fact, we prove that for any positive integer k, there exists an integer f(k) satisfying the following: For any 4-edge-connected graph G=(V,E),
either G has edge-disjoint k odd cycles or there exists an edge set F
subseteq E with |F| <= f(k) such that G-F is bipartite. We note that
the 4-edge-connectivity is best possible in this statement.
Similar approach can be applied to an algorithmic question. Suppose
that the input graph G is a 4-edge-connected graph with n vertices.
We show that, for any epsilon > 0, if k = O ((log log log n)^{1/2-epsilon}), then the edge-disjoint k odd cycle packing in G can be solved in polynomial time of n
- …
