Arrow Research search

Author name cluster

Gerhard J. Woeginger

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

30 papers
2 author rows

Possible papers

30

MFCS Conference 2018 Conference Paper

Graph Similarity and Approximate Isomorphism

  • Martin Grohe
  • Gaurav Rattan
  • Gerhard J. Woeginger

The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not received much attention in the algorithms community: Given two graphs G, H of the same order n with adjacency matrices A_G, A_H, a well-studied measure of similarity is the Frobenius distance dist(G, H): =min_{pi}|A_G^{pi}-A_H|_F, where pi ranges over all permutations of the vertex set of G, where A_G^pi denotes the matrix obtained from A_G by permuting rows and columns according to pi, and where |M |_F is the Frobenius norm of a matrix M. The (weighted) graph similarity problem, denoted by GSim (WSim), is the problem of computing this distance for two graphs of same order. This problem is closely related to the notoriously hard quadratic assignment problem (QAP), which is known to be NP-hard even for severely restricted cases. It is known that GSim (WSim) is NP-hard; we strengthen this hardness result by showing that the problem remains NP-hard even for the class of trees. Identifying the boundary of tractability for WSim is best done in the framework of linear algebra. We show that WSim is NP-hard as long as one of the matrices has unbounded rank or negative eigenvalues: hence, the realm of tractability is restricted to positive semi-definite matrices of bounded rank. Our main result is a polynomial time algorithm for the special case where the associated (weighted) adjacency graph for one of the matrices has a bounded number of twin equivalence classes. The key parameter underlying our algorithm is the clustering number of a graph; this parameter arises in context of the spectral graph drawing machinery.

Details

TCS Journal 2016 Journal Article

Finding large degree-anonymous subgraphs is hard

  • Cristina Bazgan
  • Robert Bredereck
  • Sepp Hartung
  • André Nichterlein
  • Gerhard J. Woeginger

A graph is said to be k-anonymous for an integer k, if for every vertex in the graph there are at least k − 1 other vertices with the same degree. We examine the computational complexity of making a given undirected graph k-anonymous either through at most s vertex deletions or through at most s edge deletions; the corresponding problem variants are denoted by Anonym V-Del and Anonym E-Del. We present a variety of hardness results, most of them hold for both problems. The two variants are intractable from the parameterized as well as from the approximation point of view. In particular, we show that both variants remain NP-hard on very restricted graph classes like trees even if k = 2. We further prove that both variants are W[1]-hard with respect to the combined parameter solutions size s and anonymity level k. With respect to approximability, we obtain hardness results showing that neither variant can be approximated in polynomial time within a factor better than n 1 2 (unless P = NP ). Furthermore, for the optimization variants where the solution size s is given and the task is to maximize the anonymity level k, this inapproximability result even holds if we allow a running time of f ( s ) ⋅ n O ( 1 ) for any computable function f. On the positive side, we classify both problem variants as fixed-parameter tractable with respect to the combined parameter solution size s and maximum degree Δ.

Details DOI

IJCAI Conference 2013 Conference Paper

Are There Any Nicely Structured Preference Profiles Nearby?

  • Robert Bredereck
  • Jiehua Chen
  • Gerhard J. Woeginger

We investigate the problem of deciding whether a given preference profile is close to a nicely structured preference profile of a certain type, as for instance single-peaked, single-caved, singlecrossing, value-restricted, best-restricted, worstrestricted, medium-restricted, or group-separable profiles. We measure this distance by the number of voters or alternatives that have to be deleted so as to reach a nicely structured profile. Our results classify all considered problem variants with respect to their computational complexity, and draw a clear line between computationally tractable (polynomial time solvable) and computationally intractable (NP-hard) questions.

PDF Details DOI

TCS Journal 2012 Journal Article

An algorithmic analysis of the Honey-Bee game

  • Rudolf Fleischer
  • Gerhard J. Woeginger

The Honey-Bee game is a two-player board game that is played on a connected hexagonal colored grid or (in a generalized setting) on a connected graph with colored nodes. In a single move, a player calls a color and thereby conquers all the nodes of that color that are adjacent to his own current territory. Both players want to conquer the majority of the nodes. We show that winning the game is PSPACE-hard in general, NP-hard on series-parallel graphs, but easy on outer-planar graphs. In the solitaire version, the goal of the single player is to conquer the entire graph with the minimum number of moves. The solitaire version is NP-hard on trees and split graphs, but can be solved in polynomial time on co-comparability graphs.

Details DOI

MFCS Conference 2012 Conference Paper

Transportation under Nasty Side Constraints

  • Gerhard J. Woeginger

Abstract The talk discusses planning problems where a set of items has to be transported from location A to location B subject to certain collision and/or resource constraints. We analyze the behavior of these problems, discuss their history, and derive some of their combinatorial and algorithmic properties.

Details

IJCAI Conference 2011 Conference Paper

Unweighted Coalitional Manipulation under the Borda Rule Is NP-Hard

  • Nadja Betzler
  • Rolf Niedermeier
  • Gerhard J. Woeginger

The Borda voting rule is a positional scoring rule where, for m candidates, for every vote the first candidate receives m-1 points, the second m-2 points and so on. A Borda winner is a candidate with highest total score. It has been a prominent open problem to determine the computational complexity of Unweighted Coalitional Manipulation under Borda: Can one add a certain number of additional votes (called manipulators) to an election such that a distinguished candidate becomes a winner? We settle this open problem by showing NP-hardness even for two manipulators and three input votes. Moreover, we discuss extensions and limitations of this hardness result.

PDF Details DOI

SODA Conference 2010 Conference Paper

The Focus of Attention Problem

  • Dries R. Goossens
  • Sergey Polyakovskiy
  • Frits C. R. Spieksma
  • Gerhard J. Woeginger

We consider the problem of assigning sensors to track targets so as to minimize the expected error in the resulting estimation for target locations. The so-called Focus of Attention problem deals with the special case where every target is tracked by one pair of range sensors. We provide a complete complexity and approximability analysis of the Focus Of Attention problem: We establish its strong NP-hardness, and we construct a polynomial time approximation scheme for it.

Details

TCS Journal 2009 Journal Article

How hard is it to find extreme Nash equilibria in network congestion games?

  • Elisabeth Gassner
  • Johannes Hatzl
  • Sven O. Krumke
  • Heike Sperber
  • Gerhard J. Woeginger

We study the complexity of finding extreme pure Nash equilibria in symmetric (unweighted) network congestion games. In our context best and worst equilibria are those with minimum respectively maximum makespan. On series–parallel graphs a worst Nash equilibrium can be found by a Greedy approach while finding a best equilibrium is NP-hard. For a fixed number of users we give a pseudo-polynomial algorithm to find the best equilibrium in series–parallel networks. For general network topologies also finding a worst equilibrium is NP-hard.

Details DOI

TCS Journal 2009 Journal Article

Partitioning graphs into connected parts

  • Pim van ’t Hof
  • Daniël Paulusma
  • Gerhard J. Woeginger

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing prespecified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Path Contractibility problem asks for the largest integer ℓ for which an input graph can be contracted to the path P ℓ on ℓ vertices. We show that the computational complexity of the Longest Path Contractibility problem restricted to P ℓ -free graphs jumps from being polynomially solvable to being NP-hard at ℓ = 6, while this jump occurs at ℓ = 5 for the 2-Disjoint Connected Subgraphs problem. We also present an exact algorithm that solves the 2-Disjoint Connected Subgraphs problem faster than O ∗ ( 2 n ) for any n -vertex P ℓ -free graph. For ℓ = 6, its running time is O ∗ ( 1. 579 0 n ). We modify this algorithm to solve the Longest Path Contractibility problem for P 6 -free graphs in O ∗ ( 1. 579 0 n ) time.

Details DOI

TCS Journal 2007 Journal Article

Approximation schemes for a class of subset selection problems

  • Kirk Pruhs
  • Gerhard J. Woeginger

In this paper we develop an easily applicable algorithmic technique/tool for developing approximation schemes for certain types of combinatorial optimization problems. Special cases that are covered by our result show up in many places in the literature. For every such special case, a particular rounding trick has been implemented in a slightly different way, with slightly different arguments, and with slightly different worst case estimations. Usually, the rounding procedure depended on certain upper or lower bounds on the optimal objective value that have to be justified in a separate argument. Our easily applied result unifies many of these results, and sometimes it even leads to a simpler proof. We demonstrate how our result can be easily applied to a broad family of combinatorial optimization problems. As a special case, we derive the existence of an FPTAS for the scheduling problem of minimizing the weighted number of late jobs under release dates and preemption on a single machine. The approximability status of this problem has been open for some time.

Details DOI

TCS Journal 2007 Journal Article

Preface

  • Jos C.M. Baeten
  • Jan Karel Lenstra
  • Gerhard J. Woeginger
Details DOI

MFCS Conference 2004 Conference Paper

Parallel Knock-Out Schemes in Networks

  • Hajo Broersma
  • Fedor V. Fomin
  • Gerhard J. Woeginger

Abstract We consider parallel knock-out schemes, a procedure on graphs introduced by Lampert and Slater in 1997 in which each vertex eliminates exactly one of its neighbors in each round. We are considering cases in which after a finite number of rounds, where the minimimum number is called the parallel knock-out number, no vertices of the graph are left. We derive a number of combinatorial and algorithmical results on parallel knock-out numbers. We observe that for families of sparse graphs (like planar graphs, or graphs with bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices, which is basically tight for trees. Furthermore, we construct a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach, whereas the general problem is known to be NP-hard. Finally we show that claw-free graphs with minimum degree at least 2 have parallel knock-out number at most 2, and that the lower bound on the minimum degree is best possible.

Details

MFCS Conference 2003 Conference Paper

A Faster FPT Algorithm for Finding Spanning Trees with Many Leaves

  • Paul S. Bonsma
  • Tobias Brüggemann
  • Gerhard J. Woeginger

Abstract We describe a new, fast, and fairly simple FPT algorithm for the problem of deciding whether a given input graph G has a spanning tree with at least k leaves. The time complexity of our algorithm is polynomially bounded in the size of G, and its dependence on k is roughly O (9. 49 k ). This is the fastest currently known algorithm for this problem.

Details

TCS Journal 2002 Journal Article

Off-line temporary tasks assignment

  • Yossi Azar
  • Oded Regev
  • Jiřı́ Sgall
  • Gerhard J. Woeginger

In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and some weight. Each job should be assigned to one machine. The load on a machine at a certain time is the sum of the weights of jobs assigned to it at that time. The objective is to find an assignment that minimizes the maximum load over machines and time. We present a polynomial time approximation scheme for the case in which the number of machines is fixed. We also show that for the case in which the number of machines is given as part of the input (i. e. , not fixed), no polynomial algorithm can achieve a better approximation ratio than 3 2 unless P=NP.

Details DOI

TCS Journal 2002 Journal Article

Solution of a problem in DNA computing

  • Eric Anderson
  • Marek Chrobak
  • John Noga
  • Jiřı́ Sgall
  • Gerhard J. Woeginger

We answer a question of Rozenberg and Salomaa arising from a problem in DNA computing. This problem was posed at the ICALP conference in July 1999 in Prague.

Details DOI

TCS Journal 2000 Journal Article

A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem

  • Petra Schuurman
  • Gerhard J. Woeginger

In this paper we investigate the two-stage multiprocessor flow shop scheduling problem F2(P)|·|C max, where the numbers m1 and m2 of machines available in the two stages are part of the input. We demonstrate the existence of a polynomial time approximation scheme for this problem. This result solves the simplest case of an open problem that has been posed by Leslie Hall in a recent paper (Hall, 1995). An extension of our algorithm yields an approximation scheme for the closely related two-stage multiprocessor job shop problem.

Details DOI

FOCS Conference 2000 Conference Paper

Approximability and in-approximability results for no-wait shop scheduling

  • Maxim Sviridenko
  • Gerhard J. Woeginger

We investigate the approximability of no-wait shop scheduling problems under the makespan criterion. In a flow shop, all jobs pass through the machines in the same ordering. In the more general job shop, the routes of the jobs are job-dependent. We present a polynomial time approximation scheme (PTAS) for the no-wait flow shop problem on any fixed number of machines. Unless P=NP, this result cannot be extended to the job shop problem on a fixed number of machines: We show that the no-wait job shop problem is APX-hard on (i) two machines with at most five operations per job, and on (ii) three machines with at most three operations per job.

Details

TCS Journal 1994 Journal Article

On-line scheduling of jobs with fixed start and end times

  • Gerhard J. Woeginger

We investigate an on-line scheduling problem on a single machine where jobs have fixed start and end times. If a job is not processed immediately after its arrival or if its processing is aborted, the job is lost. The goal is to maximize the total value of all processed jobs. In general, this problem does not allow on-line approximations with finite worst case guarantee. We give an approximation algorithm with worst case ratio four for large classes of special instances, and we also prove that the factor four is best possible. One of our classes contains the instances where the job values are proportional to the job lengths.

Details DOI

FOCS Conference 1990 Conference Paper

Drawing Graphs in the Plane with High Resolution

  • Michael Formann
  • Torben Hagerup
  • James Haralambides
  • Michael Kaufmann 0001
  • Frank Thomson Leighton
  • Antonios Symvonis
  • Emo Welzl
  • Gerhard J. Woeginger

The problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized is studied. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph is defined to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that Omega (1/d/sup 2/) >

Details
v2026.09.13