New conference paper by Ildikó Schlotter in WALCOM: Algorithms and Computation

WALCOM: Algorithms and Computation

17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22–24, 2023, Proceedings

Recognizing When a Preference System is Close to Admitting a Master List

Ildikó Schlotter

Part of the Lecture Notes in Computer Science book series (LNCS,volume 13973)

Abstract

A preference system I is an undirected graph where vertices have preferences over their neighbors, and I admits a master list if all preferences can be derived from a single ordering over all vertices. We study the problem of deciding whether a given preference system I is close to admitting a master list based on three different distance measures. We determine the computational complexity of the following questions: can I be modified by (i) k swaps in the preferences, (ii) k edge deletions, or (iii) k vertex deletions so that the resulting instance admits a master list? We investigate these problems in detail from the viewpoint of parameterized complexity and of approximation. We also present two applications related to stable and popular matchings.

 

 

2024

May

26

M

T

W

T

F

S

S

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

Next month >
a

2024

May

26

M

T

W

T

F

S

S

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

Next month >