RBRobert D. Barish

Robert D. Barish

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Robert D. Barish has a total of 5 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Dihedral Tilings of the Sphere by Kites and Regular Polygons

    by Robert Barish, Kam Hang Cheng, Hoi Ping Luk

    In this article, we study the edge-to-edge dihedral tilings of the sphere by kites and regular m-gons with m ≥ 4. All such tilings have been identified and fully classified, using various combinatorial and geometric tools. New phenomena are observed among the tilings.

  • Open Access

    Sokoban-style PushPush Games with Unique Solutions

    by Robert D. Barish, Tetsuo Shibuya

    Based on the 1994 Macintosh computer game of the same name, the PushPush variation on Sokoban, which we refer to as PushPush-Storage, is a block pushing puzzle in which the player controls an agent on an integer lattice populated with blocks, where pushing a block causes it to slide to the maximum possible extent without momentum transfer to other blocks, and where the objective is to cover a fixed set of storage sites with unmoving blocks. Here, we consider the problem of designing non-trivial instances of PushPush-Storage puzzles where one can easily quantify how close the player is to finding a given solution. Towards this objective, we show that randomized polynomial time reductions from Boolean satisfiability problems can be used to efficiently construct PushPush-Storage puzzles having unique solutions while also not admitting polynomial time algorithms unless NP =RP. Accordingly, provided a game designer can find a solvable PushPush-Storage puzzle and its solution, the uniqueness of its solution provides a direct means of both quantifying the percentage completion of the puzzle and of determining if a player has become trapped. Finally, we establish that PushPush-Storage puzzles are hard for Ueda and Nagao's class of Another Solution Problem (ASP) function problems.

  • Open Access

    String editing under pattern constraints

    by Robert D. Barish, Tetsuo Shibuya

  • Open Access

    Proper colorability of segment intersection graphs

    by Robert D. Barish, Tetsuo Shibuya

    We consider the vertex proper coloring problem for highly restricted instances of geometric intersection graphs of line segments embedded in the plane. Provided a graph in the class UNIT-PURE-k-DIR, corresponding to intersection graphs of unit length segments lying in at most k directions with all parallel segments disjoint, and provided explicit coordinates for segments whose intersections induce the graph, we show for $$k = 4$$ k = 4 that it is NP-complete to decide if a proper 3-coloring exists, and moreover, $$\#P$$ # P -complete under many-one counting reductions to determine the number of such colorings. In addition, under the more relaxed constraint that segments have at most two distinct lengths, we show these same hardness results hold for finding and counting proper $$\left( k-1\right) $$ k - 1 -colorings for every $$k \ge 5$$ k ≥ 5 . More generally, we establish that the problem of proper 3-coloring an arbitrary graph with m edges can be reduced in $${\mathcal {O}}\left( m^2\right) $$ O m 2 time to the problem of proper 3-coloring a UNIT-PURE-4-DIR graph. This can then be shown to imply that no $$2^{o\left( \sqrt{n}\right) }$$ 2 o n time algorithm can exist for proper 3-coloring PURE-4-DIR graphs under the Exponential Time Hypothesis (ETH), and by a slightly more elaborate construction, that no $$2^{o\left( \sqrt{n}\right) }$$ 2 o n time algorithm can exist for counting the such colorings under the Counting Exponential Time Hypothesis (#ETH). Finally, we prove an NP-hardness result for the optimization problem of finding a maximum order proper 3-colorable induced subgraph of a UNIT-PURE-4-DIR graph.

  • Counting on Rainbow k-Connections

    by Robert D. Barish, Tetsuo Shibuya

  • Open Access

    Affine optimal k-proper connected edge colorings

    by Robert D. Barish, Tetsuo Shibuya

    We introduce affine optimal k-proper connected edge colorings as a variation on Fujita’s notion of optimal k-proper connected colorings (Fujita in Optim Lett 14(6):1371–1380, 2020. https://doi.org/10.1007/s11590-019-01442-9) with applications to the frequency assignment problem. Here, for a simple undirected graph G with edge set $$E_G$$ E G , such a coloring corresponds to a decomposition of $$E_G$$ E G into color classes $$C_1, C_2, \ldots , C_n$$ C 1 , C 2 , … , C n , with associated weights $$w_1, w_2, \ldots , w_n$$ w 1 , w 2 , … , w n , minimizing a specified affine function $${\mathcal {A}}\, {:=}\,\sum _{i=1}^{n} \left( w_i \cdot |C_i|\right)$$ A : = ∑ i = 1 n w i · | C i | , while also ensuring the existence of k vertex disjoint proper paths (i.e., simple paths with no two adjacent edges in the same color class) between all pairs of vertices. In this context, we define $$\zeta _{{\mathcal {A}}}^k(G)$$ ζ A k ( G ) as the minimum possible value of $${\mathcal {A}}$$ A under a k-proper connectivity requirement. For any fixed number of color classes, we show that computing $$\zeta _{{\mathcal {A}}}^k(G)$$ ζ A k ( G ) is treewidth fixed parameter tractable. However, we also show that determining $$\zeta _{{\mathcal {A}}^{\prime }}^k(G)$$ ζ A ′ k ( G ) with the affine function $${\mathcal {A}}^{\prime } \, {:=}\,0 \cdot |C_1| + |C_2|$$ A ′ : = 0 · | C 1 | + | C 2 | is NP-hard for 2-connected planar graphs in the case where $$k = 1$$ k = 1 , cubic 3-connected planar graphs for $$k = 2$$ k = 2 , and k-connected graphs $$\forall k \ge 3$$ ∀ k ≥ 3 . We also show that no fully polynomial-time randomized approximation scheme can exist for approximating $$\zeta _{{\mathcal {A}}^{\prime }}^k(G)$$ ζ A ′ k ( G ) under any of the aforementioned constraints unless $$NP=RP$$ N P = R P .