TY - GEN

T1 - Computing L(p, 1)-Labeling with Combined Parameters

AU - Hanaka, Tesshu

AU - Kawai, Kazuma

AU - Ono, Hirotaka

N1 - Funding Information:
This work is partially supported by JSPS KAKENHI Grant Numbers JP17K19960, JP17H01698, JP19K21537 and JP20H05967. A full version is available in [21].
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - Given a graph, an L(p, 1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), | f(u) - f(v) | ≥ p if u and v are adjacent, and f(u) ≠ f(v) if u and v are at distance 2. The L(p, 1)-labeling problem is to minimize the span of f (i.e., maxu ∈ V(f(u) ) - minu ∈ V(f(u) ) + 1 ). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p, 1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.

AB - Given a graph, an L(p, 1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), | f(u) - f(v) | ≥ p if u and v are adjacent, and f(u) ≠ f(v) if u and v are at distance 2. The L(p, 1)-labeling problem is to minimize the span of f (i.e., maxu ∈ V(f(u) ) - minu ∈ V(f(u) ) + 1 ). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p, 1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.

UR - http://www.scopus.com/inward/record.url?scp=85102761126&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85102761126&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-68211-8_17

DO - 10.1007/978-3-030-68211-8_17

M3 - Conference contribution

AN - SCOPUS:85102761126

SN - 9783030682101

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 208

EP - 220

BT - WALCOM

A2 - Uehara, Ryuhei

A2 - Hong, Seok-Hee

A2 - Nandy, Subhas C.

PB - Springer Science and Business Media Deutschland GmbH

T2 - 15th International Conference on Algorithms and Computation, WALCOM 2021

Y2 - 28 February 2021 through 2 March 2021

ER -