A Simpler Self-reduction Algorithm for Matroid Path-width

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00101457" target="_blank" >RIV/00216224:14330/18:00101457 - isvavai.cz</a>

Výsledek na webu

<a href="http://arxiv.org/abs/1605.09520" target="_blank" >http://arxiv.org/abs/1605.09520</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/17M1120129" target="_blank" >10.1137/17M1120129</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Simpler Self-reduction Algorithm for Matroid Path-width

Popis výsledku v původním jazyce

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).

Název v anglickém jazyce

A Simpler Self-reduction Algorithm for Matroid Path-width

Popis výsledku anglicky

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).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-00837S" target="_blank" >GA17-00837S: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

—

Svazek periodika

32

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

16

Strana od-do

1425-1440

Kód UT WoS článku

000436975900037

EID výsledku v databázi Scopus

2-s2.0-85049597399