Parameterized Problems Related to Seidel's Switching

J 2011

Parameterized Problems Related to Seidel's Switching

HLINĚNÝ, Petr; Eva JELÍNKOVÁ; Jan KRATOCHVÍL a Ondřej SUCHÝ

Základní údaje

Originální název

Parameterized Problems Related to Seidel's Switching

Název česky

Parametrizované problémy vztažené k Seidlovu přepínání

Autoři

HLINĚNÝ, Petr ; Eva JELÍNKOVÁ; Jan KRATOCHVÍL a Ondřej SUCHÝ

Vydání

Discrete Mathematics & Theoretical Computer Science, France, DMTCS, 2011, 1365-8050

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Francie

Utajení

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

Odkazy

paper

Impakt faktor

Impact factor: 1.061 v roce 2005

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/11:00053105

Organizační jednotka

Fakulta informatiky

UT WoS

000290721600002

Klíčová slova anglicky

graph; Seidel switching

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 3. 4. 2013 14:57, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

ORIG CZ

V originále

Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter Complexity. Among other results we show that switching to a graph with at most $k$ edges, to a graph of maximum degree at most $k$, to a $k$-regular graph, or to a graph with minimum degree at least $k$ are fixed parameter tractable problems, where $k$ is the parameter. On the other hand, switching to a graph that contains a given fixed graph as an induced subgraph is $W[1]$-complete. We also show the NP-completeness of switching to a graph with a clique of linear size, and of switching to a graph with small number of edges. A consequence of the latter result is the NP-completeness of Maximum likelihood decoding of graph theoretic codes based on complete graphs.

Česky

Studujeme různé problémy vztažené k operaci (Seidel switching) přepínající sousedy vrcholu grafu.

Návaznosti

MSM0021622419, záměr

Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy

1M0545, projekt VaV

Název: Institut Teoretické Informatiky

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky

Citovat

HLINĚNÝ, Petr; Eva JELÍNKOVÁ; Jan KRATOCHVÍL a Ondřej SUCHÝ. Parameterized Problems Related to Seidel's Switching. Discrete Mathematics & Theoretical Computer Science. France: DMTCS, 2011, roč. 13, č. 2, s. 19-42. ISSN 1365-8050.

@article{950106,
   author = {Hliněný, Petr and Jelínková, Eva and Kratochvíl, Jan and Suchý, Ondřej},
   article_location = {France},
   article_number = {2},
   keywords = {graph; Seidel switching},
   language = {eng},
   issn = {1365-8050},
   journal = {Discrete Mathematics & Theoretical Computer Science},
   title = {Parameterized Problems Related to Seidel's Switching},
   url = {http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1531},
   volume = {13},
   year = {2011}
}

TY  - JOUR
ID  - 950106
AU  - Hliněný, Petr - Jelínková, Eva - Kratochvíl, Jan - Suchý, Ondřej
PY  - 2011
TI  - Parameterized Problems Related to Seidel's Switching
JF  - Discrete Mathematics & Theoretical Computer Science
VL  - 13
IS  - 2
SP  - 19-42
EP  - 19-42
PB  - DMTCS
SN  - 13658050
KW  - graph
KW  - Seidel switching
UR  - http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1531
N2  - Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non-adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching-equivalent if one can be made isomorphic to the other by a sequence of switches. In this paper, we continue the study of computational complexity aspects of Seidel's switching, concentrating on Fixed Parameter Complexity. Among other results we show that switching to a graph with at most $k$ edges, to a graph of maximum degree at most $k$, to a $k$-regular graph, or to a graph with minimum degree at least $k$ are fixed parameter tractable problems, where $k$ is the parameter. On the other hand, switching to a graph that contains a given fixed graph as an induced subgraph is $W[1]$-complete. We also show the NP-completeness of switching to a graph with a clique of linear size, and of switching to a graph with small number of edges. A consequence of the latter result is the NP-completeness of Maximum likelihood decoding of graph theoretic codes based on complete graphs.
ER  -

HLINĚNÝ, Petr; Eva JELÍNKOVÁ; Jan KRATOCHVÍL a Ondřej SUCHÝ. Parameterized Problems Related to Seidel's Switching. \textit{Discrete Mathematics \&{} Theoretical Computer Science}. France: DMTCS, 2011, roč.~13, č.~2, s.~19-42. ISSN~1365-8050.

Přehled o publikaci