A Simpler Self-reduction Algorithm for Matroid Path-width

J 2018

A Simpler Self-reduction Algorithm for Matroid Path-width

HLINĚNÝ, Petr

Základní údaje

Originální název

A Simpler Self-reduction Algorithm for Matroid Path-width

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant, domácí)

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2018, 0895-4801

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Impakt faktor

Impact factor: 0.843

Kód RIV

RIV/00216224:14330/18:00101457

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1137/17M1120129

UT WoS

000436975900037

Klíčová slova anglicky

matroid; path-width; trellis-width; fixed-parameter tractability; well-quasi-ordering

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 16. 4. 2020 09:52, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

ORIG CZ

V originále

The path-width of matroids naturally generalizes the better known parameter of path-width for graphs and is NP-hard by a reduction from the graph case. While the term matroid path-width was formally introduced in [J. Geelen, B. Gerards, and G. Whittle, J. Combin. Theory Ser. B, 96 (2006), pp. 405-425] in pure matroid theory, it was soon recognized in [N. Kashyap, SIAM J. Discrete Math., 22 (2008), pp. 256-272] that it is the same concept as the long-studied so-called trellis complexity in coding theory, later named trellis-width, and hence it is an interesting notion also from the algorithmic perspective. It follows from a result of Hlineny [P. Hlieny, J. Combin. Theory Ser. B, 96 (2006), pp. 325-351] that the decision problem-whether a given matroid over a finite field has path-width at most t-is fixed-parameter tractable (FPT) in t, but this result does not give any clue about constructing a path-decomposition. The first constructive and rather complicated FPT algorithm for path-width of matroids over a finite field was given in [J. Jeong, E. J. Kim, and S. Oum, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2016, pp. 1695-1704]. Here we propose a simpler "self-reduction" FPT algorithm for a path-decomposition. Precisely, we design an efficient routine that constructs an optimal pathdecomposition of a matroid by calling any subroutine for testing whether the path-width of a matroid is at most t (such as the aforementioned decision algorithm for matroid path-width).

Česky

Podáváme jednodušší self-redukční algoritmus pro výpočet optimální path-dekompozice daného matroidu nad konečným tělesem.

Návaznosti

GA17-00837S, projekt VaV

Název: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech

Investor: Grantová agentura ČR, Structural properties, parameterized tractability and hardness in combinatorial problems

Citovat

HLINĚNÝ, Petr. A Simpler Self-reduction Algorithm for Matroid Path-width. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2018, roč. 32, č. 2, s. 1425-1440. ISSN 0895-4801. Dostupné z: https://dx.doi.org/10.1137/17M1120129.

@article{1480301,
   author = {Hliněný, Petr},
   article_location = {Philadelphia},
   article_number = {2},
   doi = {http://dx.doi.org/10.1137/17M1120129},
   keywords = {matroid; path-width; trellis-width; fixed-parameter tractability; well-quasi-ordering},
   language = {eng},
   issn = {0895-4801},
   journal = {SIAM Journal on Discrete Mathematics},
   title = {A Simpler Self-reduction Algorithm for Matroid Path-width},
   url = {http://arxiv.org/abs/1605.09520},
   volume = {32},
   year = {2018}
}

TY  - JOUR
ID  - 1480301
AU  - Hliněný, Petr
PY  - 2018
TI  - A Simpler Self-reduction Algorithm for Matroid Path-width
JF  - SIAM Journal on Discrete Mathematics
VL  - 32
IS  - 2
SP  - 1425-1440
EP  - 1425-1440
PB  - SIAM
SN  - 08954801
KW  - matroid
KW  - path-width
KW  - trellis-width
KW  - fixed-parameter tractability
KW  - well-quasi-ordering
UR  - http://arxiv.org/abs/1605.09520
L2  - http://arxiv.org/abs/1605.09520
N2  - The path-width of matroids naturally generalizes the better known parameter of path-width for graphs and is NP-hard by a reduction from the graph case. While the term matroid path-width was formally introduced in [J. Geelen, B. Gerards, and G. Whittle, J. Combin. Theory Ser. B, 96 (2006), pp. 405-425] in pure matroid theory, it was soon recognized in [N. Kashyap, SIAM J. Discrete Math., 22 (2008), pp. 256-272] that it is the same concept as the long-studied so-called trellis complexity in coding theory, later named trellis-width, and hence it is an interesting notion also from the algorithmic perspective. It follows from a result of Hlineny [P. Hlieny, J. Combin. Theory Ser. B, 96 (2006), pp. 325-351] that the decision problem-whether a given matroid over a finite field has path-width at most t-is fixed-parameter tractable (FPT) in t, but this result does not give any clue about constructing a path-decomposition. The first constructive and rather complicated FPT algorithm for path-width of matroids over a finite field was given in [J. Jeong, E. J. Kim, and S. Oum, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2016, pp. 1695-1704]. Here we propose a simpler "self-reduction" FPT algorithm for a path-decomposition. Precisely, we design an efficient routine that constructs an optimal pathdecomposition of a matroid by calling any subroutine for testing whether the path-width of a matroid is at most t (such as the aforementioned decision algorithm for matroid path-width).
ER  -

HLINĚNÝ, Petr. A Simpler Self-reduction Algorithm for Matroid Path-width. \textit{SIAM Journal on Discrete Mathematics}. Philadelphia: SIAM, 2018, roč.~32, č.~2, s.~1425-1440. ISSN~0895-4801. Dostupné z: https://dx.doi.org/10.1137/17M1120129.

Podrobný výpis o publikaci