2023/09/15 更新

エトウ ヒロシ
江藤 宏
ETO Hiroshi
Scopus 論文情報  
総論文数: 0  総Citation: 0  h-index: 6

Citation Countは当該年に発表した論文の被引用数

所属
大学院情報工学研究院 知能情報工学研究系
職名
助教
外部リンク

取得学位

  • 九州工業大学  -  博士(情報工学)   2016年03月

学内職務経歴

  • 2022年10月 - 現在   九州工業大学   大学院情報工学研究院   知能情報工学研究系     助教

論文

  • Approximation Algorithms for the Longest Run Subsequence Problem 査読有り

    Asahiro Y., Gong M., Lin G., Ono H., Eto H., Jansson J., Miyano E., Tanaka S.

    Leibniz International Proceedings in Informatics, LIPIcs   259   2023年06月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s1 · · · sn over an alphabet Σ, a run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S′ of S is a sequence in which every symbol σ ∈ Σ occurs in at most one run. Given a string S, the goal of LRS is to find a longest run subsequence S∗ of S such that the length |S∗| is maximized over all the run subsequences of S. It is known that LRS is APX-hard even if each symbol has at most two occurrences in the input string, and that LRS admits a polynomial-time k-approximation algorithm if the number of occurrences of every symbol in the input string is bounded by k. In this paper, we design a polynomial-time k+1/2-approximation algorithm for LRS under the k-occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 2/3 to 4/3.

    DOI: 10.4230/LIPIcs.CPM.2023.2

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85165971942&origin=inward

  • Reconfiguration of Vertex-Disjoint Shortest Paths on Graphs 査読有り

    Saito R., Eto H., Ito T., Uehara R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   13973 LNCS   191 - 201   2023年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    We introduce and study reconfiguration problems for (internally) vertex-disjoint shortest paths: Given two tuples of internally vertex-disjoint shortest paths for fixed terminal pairs in an unweighted graph, we are asked to determine whether one tuple can be transformed into the other by exchanging a single vertex of one shortest path in the tuple at a time, so that all intermediate results remain tuples of internally vertex-disjoint shortest paths. We also study the shortest variant of the problem, that is, we wish to minimize the number of vertex-exchange steps required for such a transformation, if exists. These problems generalize the well-studied Shortest Path Reconfiguration problem. In this paper, we analyze the complexity of these problems from the viewpoint of graph classes, and give some interesting contrast.

    DOI: 10.1007/978-3-031-27051-2_17

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85151063938&origin=inward

  • Independent Set Under a Change Constraint from an Initial Solution 査読有り 国際誌

    Asahiro Y., Eto H., Korenaga K., Lin G., Miyano E., Nonoue R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   13898 LNCS   37 - 51   2023年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    In this paper, we study a type of incremental optimization variant of the Maximum Independent Set problem (MaxIS), called Bounded-Deletion Maximum Independent Set problem (BD-MaxIS): Given an unweighted graph (formula presented), an initial feasible solution (i.e., an independent set), and a non-negative integer k, the objective of BD-MaxIS is to find an independent set such that and |S| is maximized. The original MaxIS is generally NP-hard, but, it can be solved in polynomial time for perfect graphs (and therefore, comparability, co-comparability, bipartite, chordal, and interval graphs). In this paper, we show that BD-MaxIS is NP-hard even if the input is restricted to bipartite graphs, and hence to comparability graphs. On the other hand, fortunately, BD-MaxIS on co-comparability, interval, convex bipartite, and chordal graphs can be solved in polynomial time. Finally, we study the computational complexity on very similar variants of the Minimum Vertex Cover and the Maximum Clique problems for graph subclasses.

    DOI: 10.1007/978-3-031-30448-4_4

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85161382364&origin=inward

  • Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs 査読有り

    Eto H., Ito T., Liu Z., Miyano E.

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   105 ( 9 )   1211 - 1222   2022年09月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(学術雑誌)

    This paper studies generalized variants of the maximum independent set problem, called the Maximum Distance-d Independent Set problem (MaxDdIS for short). For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V, E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r ≥ 3) and planar graphs, as follows: (1) For every fixed integers d ≥ 3 and r ≥ 3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(r d-1)-approximation and O(r d-2|d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(r d-2|d)-approximation algorithms when restricted to d = r = 3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

    DOI: 10.1587/transfun.2021DMP0017

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85138237602&origin=inward

  • Reconfiguration of Regular Induced Subgraphs 査読有り

    Eto H., Ito T., Kobayashi Y., Otachi Y., Wasa K.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   13174 LNCS   35 - 46   2022年01月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    We study the problem of checking the existence of a step-by-step transformation of d-regular induced subgraphs in a graph, where d≥ 0 and each step in the transformation must follow a fixed reconfiguration rule. Our problem for d= 0 is equivalent to Independent Set Reconfiguration, which is one of the most well-studied reconfiguration problems. In this paper, we systematically investigate the complexity of the problem, in particular, on chordal graphs and bipartite graphs. Our results give interesting contrasts to known ones for Independent Set Reconfiguration.

    DOI: 10.1007/978-3-030-96731-4_4

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85127912089&origin=inward

  • Happy Set Problem on Subclasses of Co-comparability Graphs 査読有り

    Eto H., Ito T., Miyano E., Suzuki A., Tamura Y.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   13174 LNCS   149 - 160   2022年01月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    In this paper, we investigate the complexity of the Maximum Happy Set problem on subclasses of co-comparability graphs. For a graph G and its vertex subset S, a vertex v∈ S is happy if all v’s neighbors in G are contained in S. Given a graph G and a non-negative integer k, Maximum Happy Set is the problem of finding a vertex subset S of G such that | S| = k and the number of happy vertices in S is maximized. In this paper, we first show that Maximum Happy Set is NP-hard even for co-bipartite graphs. We then give an algorithm for n-vertex interval graphs whose running time is O(k2n2); this improves the best known running time O(kn8) for interval graphs. We also design an algorithm for n-vertex permutation graphs whose running time is O(k3n2). These two algorithmic results provide a nice contrast to the fact that Maximum Happy Set remains NP-hard for chordal graphs, comparability graphs, and co-comparability graphs.

    DOI: 10.1007/978-3-030-96731-4_13

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85127916934&origin=inward

  • Parameterized algorithms for the Happy Set problem 査読有り

    Asahiro Y., Eto H., Hanaka T., Lin G., Miyano E., Terabaru I.

    Discrete Applied Mathematics   304   32 - 44   2021年12月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(学術雑誌)

    In this paper we study the parameterized complexity for the MAXIMUM HAPPY SET problem (MaxHS): For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard with respect to k even if the input graph is a split graph. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by tree-width, by clique-width plus k, by neighborhood diversity, or by cluster deletion number.

    DOI: 10.1016/j.dam.2021.07.005

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85111074192&origin=inward

  • Computing the Largest Bond and the Maximum Connected Cut of a Graph 査読有り

    Duarte G.L., Eto H., Hanaka T., Kobayashi Y., Kobayashi Y., Lokshtanov D., Pedrosa L.L.C., Schouery R.C.S., Souza U.S.

    Algorithmica   83 ( 5 )   1421 - 1458   2021年05月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(学術雑誌)

    The cut-set ∂(S) of a graph G= (V, E) is the set of edges that have one endpoint in S⊂ V and the other endpoint in V\ S, and whenever G[S] is connected, the cut [S, V\ S] of G is called a connected cut. A bond of a graph G is an inclusion-wise minimal disconnecting set of G, i.e., bonds are cut-sets that determine cuts [S, V\ S] of G such that G[S] and G[V\ S] are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P=NP. Also, we show that Largest Bond and Maximum Connected Cut are NP-hard even for planar bipartite graphs, whereas Maximum Cut is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that Largest Bond and Maximum Connected Cut are NP-hard on split graphs, and restricted to graphs of clique-width w they can not be solved in time f(w) no(w) unless the Exponential Time Hypothesis fails, but they can be solved in time f(w) nO(w). Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number.

    DOI: 10.1007/s00453-020-00789-1

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85099220213&origin=inward

  • Complexity and approximability of the happy set problem 査読有り

    Asahiro Y., Eto H., Hanaka T., Lin G., Miyano E., Terabaru I.

    Theoretical Computer Science   866   123 - 144   2021年04月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(学術雑誌)

    In this paper we study the approximability of the MAXIMUM HAPPY SET problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph G=(V,E) and a subset S⊆V of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph G=(V,E) and an integer k, the goal of MaxHS is to find a subset S⊆V of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a (2Δ+1)-approximation algorithm for MaxHS on graphs with maximum degree Δ. Next, we show that the approximation ratio can be improved to Δ if the maximum degree Δ of the input graph is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to block graphs, or interval graphs. We prove nevertheless that MaxHS on bipartite graphs or on cubic graphs remains NP-hard.

    DOI: 10.1016/j.tcs.2021.03.023

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85103285503&origin=inward

  • Parameterized algorithms for the happy set problem 査読有り

    Asahiro Y., Eto H., Hanaka T., Lin G., Miyano E., Terabaru I.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   12049 LNCS   323 - 328   2020年01月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    In this paper we introduce the Maximum Happy Set problem (MaxHS) and study its parameterized complexity: For an undirected graph G = (V,E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S; and otherwise unhappy. Given an undirected graph G = (V,E) and an integer k, the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard when parameterized by k. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by the tree-width, the clique-width and k, the neighborhood diversity, or the twin-cover number.

    DOI: 10.1007/978-3-030-39881-1_27

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85080915754&origin=inward

  • Graph Classes and Approximability of the Happy Set Problem 査読有り

    Asahiro Y., Eto H., Hanaka T., Lin G., Miyano E., Terabaru I.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   12273 LNCS   335 - 346   2020年01月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    In this paper we study the approximability of the Maximum Happy Set problem (MaxHS) and the computational complexity of MaxHS on graph classes: For an undirected graph and a subset of vertices, a vertex v is happy if v and all its neighbors are in S; otherwise unhappy. Given an undirected graph and an integer k, the goal of MaxHS is to find a subset of k vertices such that the number of happy vertices is maximized. MaxHS is known to be NP-hard. In this paper, we design a-approximation algorithm for MaxHS on graphs with maximum degree. Next, we show that the approximation ratio can be improved to if the input is a connected graph and its maximum degree is a constant. Then, we show that MaxHS can be solved in polynomial time if the input graph is restricted to proper interval graphs, or block graphs. We prove nevertheless that MaxHS remains NP-hard even for bipartite graphs or for cubic graphs.

    DOI: 10.1007/978-3-030-58150-3_27

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85091112536&origin=inward

  • Parameterized algorithms for maximum cut with connectivity constraints 査読有り

    Eto H., Hanaka T., Kobayashi Y., Kobayashi Y.

    Leibniz International Proceedings in Informatics, LIPIcs   148   2019年12月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    We study two variants of Maximum Cut, which we call Connected Maximum Cut and Maximum Minimal Cut, in this paper. In these problems, given an unweighted graph, the goal is to compute a maximum cut satisfying some connectivity requirements. Both problems are known to be NP-complete even on planar graphs whereas Maximum Cut on planar graphs is solvable in polynomial time. We first show that these problems are NP-complete even on planar bipartite graphs and split graphs. Then we give parameterized algorithms using graph parameters such as clique-width, tree-width, and twin-cover number. Finally, we obtain FPT algorithms with respect to the solution size.

    DOI: 10.4230/LIPIcs.IPEC.2019.13

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85077468897&origin=inward

  • Complexity of the minimum single dominating cycle problem for graph classes 査読有り

    Eto H., Kawahara H., Miyano E., Nonoue N.

    IEICE Transactions on Information and Systems   E101D ( 3 )   574 - 581   2018年03月

     詳細を見る

    担当区分:筆頭著者, 最終著者   記述言語:英語   掲載種別:研究論文(学術雑誌)

    In this paper, we study a variant of the Minimum Dominating Set problem. Given an unweighted undirected graph G = (V, E) of n = |V| vertices, the goal of the Minimum Single Dominating Cycle problem (MinSDC) is to find a single shortest cycle which dominates all vertices, i.e., a cycle C such that for the set V(C) of vertices in C and the set N(V(C)) of neighbor vertices of C, V(G) = V(C) ∪ N(V(C)) and |V(C)| is minimum over all dominating cycles in G [6], [17], [24]. In this paper we consider the (in)approximability of MinSDC if input graphs are restricted to some special classes of graphs. We first show that MinSDC is still NP-hard to approximate even when restricted to planar, bipartite, chordal, or r-regular (r ≥ 3). Then, we show the (ln n + 1)-approximability and the (1 - ϵ) ln n-inapproximability of MinSDC on split graphs under P ≠ NP. Furthermore, we explicitly design a linear-time algorithm to solve MinSDC for graphs with bounded treewidth and estimate the hidden constant factor of its running time-bound.

    DOI: 10.1587/transinf.2017FCP0007

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85042631622&origin=inward

  • Approximation algorithm for the distance-3 independent set problem on cubic graphs 査読有り

    Eto H., Ito T., Liu Z., Miyano E.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10167 LNCS   228 - 240   2017年01月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V,E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of Maximum Distance-d Independent Set problem (MaxDdIS) is to find a maximum-cardinality distance-d independent set of G. In this paper we focus on MaxD3IS on cubic (3-regular) graphs. For every fixed integer d ≥ 3, MaxDdIS is NP-hard even for planar bipartite graphs of maximum degree three. Furthermore, when d = 3, it is known that there exists no σ-approximation algorithm for MaxD3IS oncubic graphs for constant σ < 1. 00105. On the other hand, the previously best approximation ratio known for MaxD3IS on cubic graphs is 2. In this paper, we improve the approximation ratio into 1.875 for MaxD3IS on cubic graphs.

    DOI: 10.1007/978-3-319-53925-6_18

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014231181&origin=inward

  • Approximability of the distance independent set problem on regular graphs and planar graphs 査読有り

    Eto H., Ito T., Liu Z., Miyano E.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10043 LNCS   270 - 284   2016年01月

     詳細を見る

    担当区分:最終著者, 責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    This paper studies generalized variants of the maximum independent set problem, called the Maximum Distance-d Independent Set problem (MaxDdIS for short). For an integer d ≥ 2, a distance-d independent set of an unweighted graph G = (V,E) is a subset S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r ≥ 3) and planar graphs, as follows: (1) For every fixed integers d ≥ 3 and r ≥ 3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd−1)-approximation and O(rd−2/d)- approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd−2/d)-approximation algorithms when restricted to d = r = 3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.

    DOI: 10.1007/978-3-319-48749-6_20

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85007188790&origin=inward

  • Complexity of finding maximum regular induced subgraphs with prescribed degree 査読有り

    Asahiro Y., Eto H., Ito T., Miyano E.

    Theoretical Computer Science   550 ( C )   21 - 35   2014年01月

     詳細を見る

    担当区分:筆頭著者, 最終著者, 責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)

    We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G[S] induced by S is r-regular for a prescribed degree r ≥ 0. We also consider a variant of the problem which requires G[. S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs.

    DOI: 10.1016/j.tcs.2014.07.008

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84926407099&origin=inward

  • Distance-d independent set problems for bipartite and chordal graphs 査読有り

    Eto H., Guo F., Miyano E.

    Journal of Combinatorial Optimization   27 ( 1 )   88 - 99   2014年01月

     詳細を見る

    担当区分:筆頭著者, 最終著者, 責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    The paper studies a generalization of the Independent Set problem (IS for short). A distance- d independent set for an integer d≥2 in an unweighted graph G = (V, E) is a subset S⊂ V of vertices such that for any pair of vertices u, v εS, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the Distance- d Independent Set problem (D d IS for short) is to decide whether G contains a distance- d independent set S such that |S| ≥k. D2IS is identical to the original IS. Thus D2IS is \mathcal{NP} -complete even for planar graphs, but it is in \mathcal{P} for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D d IS, its maximization version MaxD d IS, and its parameterized version ParaD d IS(k), where the parameter is the size of the distance- d independent set: (1) We first prove that for any ε >0 and any fixed integer d≥3, it is \mathcal{NP} -hard to approximate MaxD d IS to within a factor of n1/2- for bipartite graphs of n vertices, and for any fixed integer d≥3, ParaD d IS(k) is \mathcal{W}[1] -hard for bipartite graphs. Then, (2) we prove that for every fixed integer d≥3, D d IS remains NP -complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d≥2, whereas D d IS is NP -complete for any odd d≥3. Also, we show the hardness of approximation of MaxD d IS and the W[1] -hardness of ParaD d IS(k) on chordal graphs for any odd d≥3. © 2013 Springer Science+Business Media New York.

    DOI: 10.1007/s10878-012-9594-4

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84893764641&origin=inward

  • Complexity of finding maximum regular induced subgraphs with prescribed degree 査読有り

    Asahiro Y., Eto H., Ito T., Miyano E.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   8070 LNCS   28 - 39   2013年09月

     詳細を見る

    担当区分:筆頭著者, 最終著者, 責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G[S] induced by S is r-regular for a prescribed degree r ≥ 0. We also consider a variant of the problem which requires G[S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth; we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs. © 2013 Springer-Verlag.

    DOI: 10.1007/978-3-642-40164-0_6

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84883179628&origin=inward

  • Inapproximability of maximum r-regular induced connected subgraph problems 査読有り

    Asahiro Y., Eto H., Miyano E.

    IEICE Transactions on Information and Systems   E96-D ( 3 )   443 - 449   2013年03月

     詳細を見る

    担当区分:筆頭著者, 最終著者, 責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)

    Given a connected graph G = (V, E) on n vertices, the Maximum r-Regular Induced Connected Subgraph (r-MaxRICS) problem asks for a maximum sized subset of vertices S ⊆ V such that the induced subgraph G[S] on S is connected and r-regular. It is known that 2-MaxRICS and 3-MaxRICS are NP-hard. Moreover, 2-MaxRICS cannot be approximated within a factor of n1-ε in polynomial time for any ε > 0 unless P = NP. In this paper, we show that r-MaxRICS are NP-hard for any fixed integer r ≥ 4. Furthermore, we show that for any fixed integer r ≥ 3, r-MaxRICS cannot be approximated within a factor of n1/6-ε in polynomial time for any ε > 0 unless P = NP. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

    DOI: 10.1587/transinf.E96.D.443

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84878238046&origin=inward

  • Distance-d independent set problems for bipartite and chordal graphs 査読有り

    Eto H., Guo F., Miyano E.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   7402 LNCS   234 - 244   2012年08月

     詳細を見る

    担当区分:筆頭著者, 最終著者, 責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    The paper studies a generalization of the Independent Set (IS) problem. A distance-d independent set for a positive integer d ≥ 2 in an unweighted graph G = (V, E) is a set S ⊆ V of vertices such that for any pair of vertices u, v ∈ S, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the Distance- d Independent Set (D d IS) problem is to decide whether G contains a distance-d independent set S such that |S| ≥ k. D2IS is identical to the original IS and thus D2IS is in for bipartite graphs and chordal graphs. In this paper, we show that for every fixed integer d ≥ 3, D d IS is -complete even for planar bipartite graphs of maximum degree three, and also -complete even for chordal bipartite graphs. Furthermore, we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d ≥ 2, whereas D d IS is -complete for any odd d ≥ 3. © 2012 Springer-Verlag.

    DOI: 10.1007/978-3-642-31770-5_21

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84865023969&origin=inward

▼全件表示

学会・委員会等活動

  • 日本オペレーションズ・リサーチ学会   九州支部 事務局  

    2023年03月 - 2025年03月

  • 情報処理学会アルゴリズム研究会(SIGAL)   運営委員  

    2020年04月 - 現在