We develop a new characterization of potential maximal cliques of a triconnected planar graph and, using this characterization, give a polynomial delay algorithm generating all potential maximal cliques of a given triconnected planar graph. Combined with the dynamic programming algorithm due to Bouchitté and Todinca, this algorithm leads to a treewidth algorithm for general planar graphs that runs in time linear in the number of potential maximal cliques and polynomial in the number of vertices.

Let tw(G) denote the treewidth of graph G. Given a graph G and a positive integer k such that tw(G) <= k + 1, we are to decide if tw(G) <= k. We give a certifying algorithm RTW ("R" for recursive) for this task: it returns one or more tree-decompositions of G of width <= k if the answer is YES and a minimal contraction H of G such that tw(H) > k otherwise. RTW uses a heuristic variant of Tamaki's PID algorithm for treewidth (ESA2017), which we call HPID. RTW, given G and k, interleaves the execution of HPID with recursive calls on G /e for edges e of G, where G / e denotes the graph obtained from G by contracting edge e. If we find that tw(G / e) > k, then we have tw(G) > k with the same certificate. If we find that tw(G / e) <= k, we "uncontract" the bags of the certifying tree-decompositions of G / e into bags of G and feed them to HPID to help progress. If the question is not resolved after the recursive calls are made for all edges, we finish HPID in an exhaustive mode. If it turns out that tw(G) > k, then G is a certificate for tw(G') > k for every G' of which G is a contraction, because we have found tw(G / e) <= k for every edge e of G. This final round of HPID guarantees the correctness of the algorithm, while its practical efficiency derives from our methods of "uncontracting" bags of tree-decompositions of G / e to useful bags of G, as well as of exploiting those bags in HPID. Experiments show that our algorithm drastically extends the scope of practically solvable instances. In particular, when applied to the 100 instances in the PACE 2017 bonus set, the number of instances solved by our implementation on a typical laptop, with the timeout of 100, 1000, and 10000 seconds per instance, are 72, 92, and 98 respectively, while these numbers are 11, 38, and 68 for Tamaki's PID solver and 65, 82, and 85 for his new solver (SEA 2022).

For a graph $G$, let $Π(G)$ denote the set of all potential maximal cliques of $G$. For each subset $Π$ of $Π(G)$, let $\tw(G, Π)$ denote the smallest $k$ such that there is a tree-decomposition of $G$ of width $k$ whose bags all belong to $Π$. Bouchitté and Todinca observed in 2001 that $\tw(G, Π(G))$ is exactly the treewidth of $G$ and developed a dynamic programming algorithm to compute it. Indeed, their algorithm can readily be applied to an arbitrary non-empty subset $Π$ of $Π(G)$ and computes $\tw(G, Π)$, or reports that it is undefined, in time $|Π||V(G)|^{O(1)}$. This efficient tool for computing $\tw(G, Π)$ allows us to conceive of an iterative improvement procedure for treewidth upper bounds which maintains, as the current solution, a set of potential maximal cliques rather than a tree-decomposition. We design and implement an algorithm along this approach. Experiments show that our algorithm vastly outperforms previously implemented heuristic algorithms for treewidth.

Consider a dynamic programming scheme for a decision problem in which all subproblems involved are also decision problems. An implementation of such a scheme is positive-instance driven (PID), if it generates positive subproblem instances, but not negative ones, building each on smaller positive instances. We take the dynamic programming scheme due to Bouchitté and Todinca for treewidth computation, which is based on minimal separators and potential maximal cliques, and design a variant (for the decision version of the problem) with a natural PID implementation. The resulting algorithm performs extremely well: it solves a number of standard benchmark instances for which the optimal solutions have not previously been known. Incorporating a new heuristic algorithm for detecting safe separators, it also solves all of the 100 public instances posed by the exact treewidth track in PACE 2017, a competition on algorithm implementation. We describe the algorithm and prove its correctness. We also perform an experimental analysis counting combinatorial structures involved, which gives insights into the advantage of our approach over more conventional approaches and points to the future direction of theoretical and engineering research on treewidth computation.

Book embedding is one of the most well-known graph drawing models and is extensively studied in the literature. The special case where the number of pages is one is of particular interest: an embedding in this case has a natural circular representation useful for visualization and graphs that can be embedded in one page without crossings form an important graph class, namely that of outerplanar graphs. In this paper, we consider the problem of minimizing the number of crossings in a one-page book embedding, which we call one-page crossing minimization. Here, we are given a graph G with n vertices together with a non-negative integer k and are asked whether G can be embedded into a single page with at most k crossings. Bannister and Eppstein (GD 2014) showed that this problem is fixed-parameter tractable. Their algorithm is derived through the application of Courcelle's theorem (on graph properties definable in the monadic second-order logic of graphs) and runs in f(L)n time, where L = 2^{O(k^2)} is the length of the formula defining the property that the one-page crossing number is at most k and f is a computable function without any known upper bound expressible as an elementary function. We give an explicit dynamic programming algorithm with a drastically improved running time of 2^{O(k log k)}n.

To solve hard graph problems from the parameterized perspective, structural parameters have commonly been used. In particular, vertex cover number is frequently used in this context. In this paper, we study the problem of computing the treedepth of a given graph G. We show that there are an O(tau(G)^3) vertex kernel and an O(4^{tau(G)}*tau(G)*n) time fixed-parameter algorithm for this problem, where tau(G) is the size of a minimum vertex cover of G and n is the number of vertices of G.

We give a subexponential fixed parameter algorithm for one-sided crossing minimization. It runs in $O(k2^{\sqrt{2k}} + n)$ time, where n is the number of vertices of the given graph and parameter k is the number of crossings. The exponent of $O(\sqrt{k})$ in this bound is asymptotically optimal assuming the Exponential Time Hypothesis and the previously best known algorithm runs in $2^{O(\sqrt{k}\log k)} + n^{O(1)}$ time. We achieve this significant improvement by the use of a certain interval graph naturally associated with the problem instance and a simple dynamic program on this interval graph. The linear dependency on n is also achieved through the use of this interval graph.

For graph G, let bw(G) denote the branchwidth of G and gm(G) the largest integer g such that G contains a g×g grid as a minor. We show that bw(G)≤3 gm(G) for every planar graph G. This is an improvement over the bound bw(G)≤4 gm(G) due to Robertson, Seymour and Thomas. Our proof is constructive and implies quadratic time constant-factor approximation algorithms for planar graphs for both problems of finding a largest grid minor and of finding an optimal branch-decomposition: (3+ϵ)-approximation for the former and (2+ϵ)-approximation for the latter, where ϵ is an arbitrary positive constant. We also study the tightness of the above bound. We show that for any constant c<2, the bound of ${\mathop {\mathrm {bw}}}(G)\leq c\; {\mathop {\mathrm {gm}}}(G) + o({\mathop {\mathrm {gm}}}(G))$ does not hold in general for a planar graph G.

We propose efficient implementations of Seymour and Thomas algorithm which, given a planar graph and an integer β, decides whether the graph has the branchwidth at least β. The computational results of our implementations show that the branchwidth of a planar graph can be computed in a practical time and memory space for some instances of size about one hundred thousand edges. Previous studies report that a straightforward implementation of the algorithm is memory consuming, which could be a bottleneck for solving instances with more than a few thousands edges. Our results suggest that with efficient implementations, the memory space required by the algorithm may not be a bottleneck in practice. Applying our implementations, an optimal branch decomposition of a planar graph of practical size can be computed in a reasonable time. Branch-decomposition based algorithms have been explored as an approach for solving many NP-hard problems on graphs. The results of this paper suggest that the approach could be practical.

We give an O ( n 3 ) time algorithm for constructing a minimum-width branch-decomposition of a given planar graph with n vertices. This is achieved through a refinement to the previously best known algorithm of Seymour and Thomas, which runs in O ( n 4 ) time.

We consider the problem of finding low-cost spanning trees for sets of n points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a given set of m barriers.We obtain the following results:if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost O(min(m2, mfi)); if the barriers are disjoint line segments, then there is always a spanning tree of cost O(m); if the barriers are disjoint fat objects, discs for example, then there is always a spanning tree of cost O(n + m).All our bounds are worst-case optimal.

Article Free Access Share on Latent semantic indexing: a probabilistic analysis Authors: Christos H. Papadimitriou Computer Science Division, U. C. Berkeley Computer Science Division, U. C. BerkeleyView Profile , Hisao Tamaki Computer Science Department, Meiji University Computer Science Department, Meiji UniversityView Profile , Prabhakar Raghavan IBM Almaden Research Center IBM Almaden Research CenterView Profile , Santosh Vempala Department of Mathematics, M.I.T. Department of Mathematics, M.I.T.View Profile Authors Info & Claims PODS '98: Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsMay 1998 Pages 159–168https://doi.org/10.1145/275487.275505Published:01 May 1998Publication History 277citation2,760DownloadsMetricsTotal Citations277Total Downloads2,760Last 12 Months261Last 6 weeks43 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ℛ d for fixed d . More specifically, let 𝒯 be any set of s halfspaces. Let x =(x 1 , …, x d ) be an arbitrary point in ℛ d . With each t ∈ 𝒯 we associate a boolean indicator function I t (x) which is 1 if and only if x is in the halfspace t . The concept class, 𝒞 d s , that we study consists of all concepts formed by any Boolean function over I t1 , …, I ts for t i ∈ 𝒯. This class is much more general than any geometric concept class known to be PAC-learnable. Our results can be extended easily to learn efficiently any Boolean combination of a polynomial number of concepts selected from any concept class 𝒞 over ℛ d given that the VC-dimension of 𝒞 has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from 𝒞 consistent with a given set of labeled examples. We also present a statistical query version of our algorithm that can tolerate random classification noise. Finally we present a generalization of the standard ε-net result of Haussler and Welzl [1987] and apply it to give an alternative noise-tolerant algorithm for d = 2 based on geometric subdivisions.

We study the embedding of the butterfly network in its faulty version, where each node is independently faulty with some constant probability p. We give a method of such self-embedding of the N-node butterfly with O(1) load, O((log log N) 2.6 ) dilation, and O((log log N) c ) congestion, which succeeds with probability at least 1 - N -1 if p < 1 - \sqrt{2/3} \simeq 0.1835$, where c is a constant that depends on p; c is about 8.84 for p = 0.1 and approaches log 2 40 \simeq 5.32$ as $p \rightarrow 0$. The method is constructive and in fact yields an N log O(1) N time deterministic algorithm to construct the claimed embedding with the claimed success probability when given the random faulty butterfly. We also show that we can make the dilation as low as O(log log N), although at the cost of log O(1) N congestion. These embeddings are level-preserving in the sense that each node is mapped to a node in the same level of the butterfly as the original node. We also derive a lower bound of log log N - o(log log N) on the dilation of a level-preserving embedding with $N^\alpha$ load, for any constant $\alpha < 1/3$ and any constant node-failure probability p > 0. Thus, the bounds on dilation are tight up to a constant factor, as far as level-preserving embeddings are concerned.

Article Free Access Share on Distribution of distances and triangles in a point set and algorithms for computing the largest common point sets Authors: Tatsuya Akutsu Human Genome Center, Institute of Medical Science, University of Tokyo, Tokyo 108, Japan Human Genome Center, Institute of Medical Science, University of Tokyo, Tokyo 108, JapanView Profile , Hisao Tamaki IBM Tokyo Research Laboratory, Yamato, Kanagawa 242, Japan IBM Tokyo Research Laboratory, Yamato, Kanagawa 242, JapanView Profile , Takeshi Tokuyama IBM Tokyo Research Laboratory, Yamato, Kanagawa 242, Japan IBM Tokyo Research Laboratory, Yamato, Kanagawa 242, JapanView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 314–323https://doi.org/10.1145/262839.262989Published:01 August 1997Publication History 8citation481DownloadsMetricsTotal Citations8Total Downloads481Last 12 Months14Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k Authors: Tetsuo Asano Dept. af Engr. Informatics, Osaka Electro-Communication University, Neyagawa 572, Japan Dept. af Engr. Informatics, Osaka Electro-Communication University, Neyagawa 572, JapanView Profile , Naoki Katoh Dept. of Management Science, Kobe university of Commerce, Kobe 651-21, Japan Dept. of Management Science, Kobe university of Commerce, Kobe 651-21, JapanView Profile , Hisao Tamaki IBM Tokyo Research Laboratory, Yamato 242, Japan IBM Tokyo Research Laboratory, Yamato 242, JapanView Profile , Takeshi Tokuyama IBM Tokyo Research Laboratory, Yamato 242, Japan IBM Tokyo Research Laboratory, Yamato 242, JapanView Profile Authors Info & Claims STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computingMay 1997 Pages 275–283https://doi.org/10.1145/258533.258602Online:04 May 1997Publication History 31citation606DownloadsMetricsTotal Citations31Total Downloads606Last 12 Months51Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over Rd for fixed d.

Let r be a collection of unbounded z-monotone Jordan arcs intersecting at most twice each other, which we call pseudo-parabolas, since two axis parallel parabolas intersects at most twice.We investigate how to cut pseudo-parabolas into the mum weight matroid base when the weight of each element changes as a quadratic function of a single parameter.1

Article Motion planning for a steering-constrained robot through moderate obstacles Share on Authors: Pankaj K. Agarwal Computer Science Department, Duke University, Box 90129, Durham, NC Computer Science Department, Duke University, Box 90129, Durham, NCView Profile , Prabhakar Raghavan IBM T.J. Watson Research Center, Yorktown Heights, NY IBM T.J. Watson Research Center, Yorktown Heights, NYView Profile , Hisao Tamaki IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, Kanagawa 242, Japan IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, Kanagawa 242, JapanView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 343–352https://doi.org/10.1145/225058.225158Online:29 May 1995Publication History 35citation649DownloadsMetricsTotal Citations35Total Downloads649Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the vertices; this vertex is labeled s. Each of several other vertices contains a single movable obstacle. The robot and the obstacles may only reside at vertices, although they may be moved across edges. A vertex may never contain more than one object (robot/obstacle). In one step, we may move either the robot or one of the obstacles from its current position /spl upsi/ to a vacant vertex adjacent to v. Our goal is to move the robot to a designated vertex t using the smallest number of steps possible. The problem is a simple abstraction of a robot motion planning problem, with the geometry replaced by the adjacencies in the graph. We point out its connections to robot motion planning. We study its complexity, giving exact and approximate algorithms for several cases.>

Suppose each node and each edge of a network is independently faulty with probability at most p and q respectively, where 0 < p, q < 1 are arbitrary constants independent of the size of the network. For each fixed integer d ≥ 2, we construct a network with O(N) nodes and with degree O(log log N) such that, after removing all the faulty nodes and edges, it still contains the N-node d-dimensional N1/d × … × N1/>d torus, and hence the mesh of the same size, with probability 1–N–Ω(loglog N). This is derived as a consequence of a simple constant-degree construction which tolerates random faults where the failure probability of each node is O(log–3d). We also give a simple constant-degree construction with O(N) nodes that tolerates O(N(1–2-d)/d worst case faults.

We study the robustness of the butterfly network against random static faults. Suppose that each edge of the butterfly is present independently of other edges with probability p. Our main result is that there is a 0-1 law on the existence of a linearsized component. More formally, there is a critical probability p such that for p above p, the faulted butterfly almost surely contains a linear-sized component, whereas for p below p, the faulted butterfly almost surely does not contain a linear-sized component. 1 Introduction Given a graph G, let G=p denote the random subgraph obtained by considering each edge independently and including it in the subgraph with probability p, excluding it with probability 1 \\Gamma p. 1 We call G=p a faulted version of G. A long list of theorems illustrate the basic fact that small changes in p can lead to dramatic changes in the connectivity of G=p. In this paper we add to this list a new theorem that shows the degree of fault-tolerance of the butter...

We consider deflection routing on the n x n mesh

The author studies the embedding of the butterfly network in a faulty version of itself where each node is independently faulty with some constant probability. He shows that such a self-embedding of the N-node butterfly with O(1) load, O((log logN)/sup 2.6/) dilation, and 0((log log N)/sup 8.2/) congestion is possible with high probability, assuming sufficiently small node-failure probability. This embedding is level-preserving in the sense that each node is mapped to a node in the same level of the butterfly. He also derives a lower bound of log log log N-c on the dilation of a level-preserving embedding with O(log/sup alpha / N) load, for any alpha , 00, and some constant c depending on alpha and p.>

Article Free Access Share on Robust bounded-degree networks with small diameters Author: Hisao Tamaki View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 247–256https://doi.org/10.1145/140901.141866Published:01 June 1992Publication History 5citation202DownloadsMetricsTotal Citations5Total Downloads202Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF